Uma idéia é usar teoria (elementar) dos grafos e demonstrar a proposição por indução no número de vértices. Essa é uma técnica muito utilizada (em teoria dos grafos) e, portanto, vale a pena tê-la em mente na hora de uma prova (especialmente de olimpíada). Além disso, a linguagem de grafos é muito útil na hora de visualizar o problema (afinal, o que pode ser mais básico do que vértices e arestas, ou seja, pontos e linhas?)
Se existem n jogadores, você pode representar o torneio por um grafo orientado com n vértices (numerados de 1 a n) e tal que, dados quaisquer i <> j, se o jogador i venceu o jogador j então existe uma seta (aresta orientada) indo do vértice i ao vértice j. A condição do enunciado implica que o grafo não possui ciclos orientados, ou seja, vértices distintos i_1, i_2, ..., i_k (k>=3) com setas indo de i_1 para i_2, i_2 para i_3, ..., i_(k-1) para i_k e i_k para i_1. O problema é provar que existe um vértice de onde partem n-1 setas (uma fonte) e um vértice onde chegam n-1 setas (um dreno). Tomemos inicialmente n = 3. Se não existir uma fonte, então cada vértice tem pelo menos uma seta chegando. Se algum vértice tiver duas setas chegando, este será um dreno. Mas, nesse caso, a terceira seta do grafo, que liga os outros dois vértices, irá (obviamente) partir de um deles. Este será a fonte. Por outro lado, se cada vértice tiver uma seta partindo e uma chegando, então teremos um ciclo, o que é proibido pelo enunciado. Logo, o caso n = 3 está provado. Tomemos agora n >= 3 e suponhamos (hipótese de indução) que o resultado seja verdadeiro para grafos com até n vértices. Considere um grafo com n+1 vértices. Suponhamos que nenhum vértice seja uma fonte ou um dreno. Retire temporariamente um vértice qualquer e as n setas que chegam a ele ou partem dele, e considere o sub-grafo de n vértices resultante. Pela hipótese de indução, este grafo possui uma fonte F e um dreno D. Recoloque agora o vértice V que você retirou. Se ele recebe uma seta de F e manda uma seta para D, acabou: F e D são a fonte e o dreno do grafo maior (com os n+1 vértices). Caso contrário, temos três alternativas a considerar: 1) V manda uma seta para F e recebe uma seta de D: Nesse caso, como F manda uma seta para D, FDVF é um ciclo. Mas isso contraria o enunciado. Logo, esse caso não ocorre; 2) V manda setas para F e para D: Nesse caso, D é o dreno do grafo maior. Se V receber alguma seta de algum vértice W, então WVFW é um ciclo, pois F é a fonte do subgrafo e, portanto, manda uma seta para W. Esta contradição mostra que este caso também não ocorre. 3) V recebe setas de F e de D: Esse caso é análogo ao anterior. Basta inverter o sentido das setas. Assim, vemos que a única possibilidade é que a fonte e o dreno do subgrafo sejam a fonte e o dreno do grafo maior. Logo, pelo princípio da indução, o resultado vale para qualquer grafo. Ou seja, num torneio onde todo mundo joga com todo mundo, se vale a "lógica" (ou seja, se não existem ciclos - situações onde A vence B, que vence C, que vence A), então tem um jogador que vence todo mundo e outro que perde pra todo mundo. []s, Claudio. De:[EMAIL PROTECTED] Para:[email protected] Cópia: Data:Fri, 11 May 2007 08:08:26 -0400 Assunto:[obm-l] Olímpiada. Nível 2. Fase 3. 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.
