Re: [obm-l] Torneio de tenis

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Torneio de tenis

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.