Re: [obm-l] Olímpiada. Nível 2. Fase 3.

["Paulo Santa Rita" <paulo.santarita@xxxxxxxxx>]

Ola Joao Carlos e demais
colegas desta lista ... OBM-L,

Nao entendi a sua tentativa... outras pessoas ja apresentaram
solucoes, mas nao tem problemas voce ver outras. Segue abaixo os
esbocos de duas outras solucoes :


1) PRIMEIRA SOLUCAO

Vou usar a notacao que voce sugere, isto e, X < Y significando que X
perdeu para Y. Sejam A e B dois jogadores. Podemos supor, sem perda de
generalidade, que A < B. Facamos J1=A e J2=B. Assim : J1 < J2.

EXPANSAO PARA A DIREITA
( Suposicao : NENHUM JOGADOR VENCEU TODOS OS CONFRONTOS  )

Como nenhum jogador venceu todos os confrontos, J2 perdeu para alguem.
Seja J3 tal que J2 < J3. Logo : J1 < J2 < J3.  J3 perdeu para alguem.
Não foi para J1 porque isto implicaria na existencia do ciclo  J1 < J2
< J3 < J1 que, por hipotese, não pode existir. Seja portanto J4 tal
que J3 < J4. Assim : J1 < J2 < J3 < J4.

E claro que podemos aplicar o mesmo raciocinio anterior a J4, vale
dizer, como nenhum jogador venceu todos os confrontos entao J4 perdeu
para alguem e este alguem não pode ser J1 ou J2 porque isto implicaria
na existencia de ciclos. Assim, deve existir J5 tal que J4 < J5 e
assim sucessivamente, o que e um absurdo, pois temos um numero finito
de jogadores e este processo obviamente se estende infinitamente ...
Logo, somos obrigados a admitir que algum jogador venceu todos os
confrontos

EXPANSAO PARA A ESQUERDA
(suposicao : NENHUM JOGADOR PERDEU TODOS OS CONFRONTOS )

Como nenhum jogador perdeu  todos os confrontos, J1 venceu alguem.
Seja J3 tal que  J3 < J1. Logo : J3 < J1 < J2 .  J3 venceu alguem. Não
foi  J2 porque isto implicaria na existencia do ciclo  J2 < J3 < J1 <
J2 que, por hipotese, não pode existir. Seja portanto J4 tal que J4 <
J3. Assim : J4 < J3 < J1 < J2.


E claro que podemos aplicar o mesmo raciocinio anterior a  J4, vale
dizer, como nenhum jogador perdeu todos os confrontos entao J4 venceu
alguem e este alguem não pode ser J1 ou J2 porque isto implicaria na
existencia de ciclos. Assim, deve existir J5 tal que J5 < J4 e assim
sucessivamente, o que e um absurdo, pois temos um numero finito de
jogadores e este processo obviamente se estende infinitamente ...
Logo, somos obrigados a admitir que algum jogador perdeu todos os
confrontos

2) SEGUNDA SOLUCAO

IMAGINE os jogadores representados por vertices de um poligono
convexo. O total de confrontos sera representado pelos lados e
diagonais deste poligono. Adotaremos a seguinte convencao : Se A
venceu B a diagonal ( ou lado ) que liga A e B sera ORIENTADA ( um
vetor ) e tera origem em A e ponta em B se A venceu B ou orientacao
contraria se B venceu ª

Suponhamos, por absurdo, que nenhum jogador perdeu todos os
confrontos. No nosso diagrama isto significa que  todo vertice e
origem de uma seta. Tomando um vertice qualquer, seguimos pela ( por
uma das ) seta de saida. Isso nos conduzira a um segundo vertice que,
por sua vez, conduzira a um terceiro vertice e assim sucessivamente.
Como não pode haver ciclos, isto e, chegarmos a um vertice por onde já
passamos, este processo se estendera ao infinito, o que e absurdo pois
temos um numero finito de vertices.

Logo, algum jogador perdeu todos os confrontos
Um raciocinio analogo pode ser aplicado para mostrar que a suposicao
de que nenhum jogador venceu todos os confrontos e igualmente falsa.

Um Abraco a Todos
Paulo Santa Rita
2,0D20,140707




Em 11/05/07, JoaoCarlos_Junior@net.ms.gov.br<JoaoCarlos_Junior@net.ms.gov.br>
escreveu:

> Solicito, por gentileza, correção da resolução (ou tentativa de resolução)
> da questão que segue.
>
>
>
> PROBLEMA 6
>
> Em um torneio de tênis de mesa (no qual nenhum jogo termina empatado), cada
> um dos n participantes jogou uma única vez contra cada um dos outros.
> Sabe-se que, para todo k > 2, não existem k jogadores J1, J2, ?, Jk tais que
> J1 ganhou de J2, J2 ganhou de J3, J3 ganhou de J4, ?, Jk ? 1 ganhou de Jk,
> Jk ganhou de J1. Prove que existe um jogador que ganhou de todos os outros e
> existe um jogador que perdeu de todos os outros.
>
>
> TENTATIVA DE RESOLUÇÃO
>
>
>
>             As hipóteses:
>
> 1)     Não há empate.
>
> 2)     Cada jogador joga uma e só uma vez com cada um dos outros.
>
> 3)     Sabe-se que, para todo k > 2, não existem k jogadores J1, J2, ?, Jk
> tais que J1 ganhou de J2, J2 ganhou de J3, J3 ganhou de J4, ?, Jk ? 1 ganhou
> de Jk, Jk ganhou de J1.
>
> A tese: Existe um jogador que ganhou de todos e um que perdeu de todos.
>
>             Bem, com três jogadores: J1, J2, J3. É sabido que a única
> hipótese que não existe é: J1>J2, J2>J3 e J3> J1. Logo, só pode existir, sem
> perda de generalidade: J1>J2, J2>J3 e J3< J1, ou seja, J1>J2>J3. Cabe
> explicar que o símbolo ?>? utilizado significa, por exemplo: ?Jogador 1
> ganhou do Jogador 2?.
>
>             Com quatro jogadores, não temos: J1>J2, J2>J3, J3> J4 e J4>J1.
> Assim, podemos trocar um ou dois desses sinais de > para <.  Então, temos:
> (>, >, >, <) ou (>, >, <, <). Assim, no primeiro caso, J4 será o que perdeu
> de todos; no segundo, será J3; e em ambos, J1 ganhou de todos.
>
> Com n jogadores: É sabido que não temos: (>,>,>, ... , >). Entre esses
> parêntesis, há n ?>?. Com n par, podemos trocar ?>? para ?<? k vezes, k de n
> a n/2, se n é par (ordem decrescente). Assim, em todos esses casos J1 será o
> que ganhou de todos e Jk será o que perdeu de todos. Se n é ímpar, k varia
> (ordem decrescente também) de n até o primeiro inteiro maior que n/2.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================