[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] Torneio de tenis



Valeu por maios essa Claudio!!!
Ass.:Johann

Claudio Buffara <claudio.buffara@terra.com.br> wrote:
on 22.09.03 13:49, Johann Peter Gustav Lejeune Dirichlet at peterdirichlet2002@yahoo.com.br wrote:

Oi turma, estou tentando resolver esse problema pra fechar a soluçao de um problema da IMO:
"Considere n inteiro positivo, e um torneio de tenis no qual todos os n jogadores jogam contra todos.
Sabe-se que e possivel distribuir as partidas em n-1 dias de modo que cada jogador jogue exatamente uma vez por dia.
Ache todos os possiveis valores de n."


Se cada jogador joga exatamente 1 vez ao dia e todas as n(n-1)/2 partidas podem ser distribuidas em n-1 dias, entao, a cada dia, sao jogadas n/2 partidas ==> n eh par.

Por inspecao vemos que n = 2 e n = 4 servem:
{1,2}
e
{1,2}  {3,4}
{1,3}  {2,4}
{1,4}  {2,3}.

Agora eh soh usar o metodo tradicional de se organizar um campeonato de "round-robin" (todo mundo joga contra todo mundo):

Consideremos um campeonato com 2m jogadores (m >= 3).

Removendo um dos jogadores, podemos associar cada um dos 2m-1 jogadores restantes a um dos vertices de um (2m-1)-gono regular.

Cada aresta desse (2m-1)-gono possui (2m-1 - 3)/2 = m-2 diagonais paralelas a ela.

Para cada aresta, as extremidades dela e de cada uma das m-2 diagonais paralelas a ela determina uma partida. Sub-total = m-1 partidas (envolvendo 2m-2 jogadores = vertices).

O jogador (vertice) restante  joga com aquele que ficou de fora, completando a tabela do dia (Total = m partidas).

Como existem 2m-1 arestas, obtemos as tabelas dos 2m-1 dias. Eh facil verificar que cada jogador joga exatamente uma vez com cada um dos outros.

Essa construcao independe do valor de m. Logo, vale para todo m >= 3.

Como verificamos por inspecao que m = 1 e m = 2 tambem servem, concluimos que qualquer valor par de n serve.


Um abraco,
Claudio.