[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.