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

["claudio\.buffara" <claudio.buffara@xxxxxxxxxxxx>]

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.