Prezado Cláudio:
Obrigado pela dica, e, em realidade, pela aula.
Por gentileza, se possível, aquela solução que eu dei é então particular e de pouca possibilidade de generalização para problemas desse tipo? É isso?
Fraternalmente, João.
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: | owner-obm-l@mat.puc-rio.br |
| Para: | obm-l@mat.puc-rio.br |
| 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.