Prezados Paulo Santa Rita e Cláudio Buffara:
Agradeço a ambos pelas respostas.
Gostaria, se possível, de saber qual parte é que não foi compreendida, pois, necessito saber se fui pouco claro ou se estou enganando a mim mesmo.
ATT. João
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
=========================================================================