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, [EMAIL PROTECTED]<[EMAIL PROTECTED]> 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 =========================================================================