Re: [obm-l] Torneio de tenis
Valeu por maios essa Claudio!!!
Ass.:JohannClaudio Buffara [EMAIL PROTECTED] wrote:
on 22.09.03 13:49, Johann Peter Gustav Lejeune Dirichlet at [EMAIL PROTECTED] 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.
Re: [obm-l] Torneio de tenis
Estou com um palpite: n = 2^k
A idéia é simples:
Sejam A e B conjuntos de tenistas com |A| = |B| =
k, então são necessários no mínimo k dias para que todos os tenistas de A
enfrentem todos de B sendo que todo jogador joga uma vez por dia nessesk
dias, por exemplo:
A = {x1, x2, ..., xk}, B = {y1, y2, ...,
yk}
dia 1: (x1, y1), (x2, y2), , (xk,
yk)
dia 2: (x1, y2), (x2, y3), , (x[k-1], yk), (xk,
y1)
dia 3: (x1, y3), (x2, y4), , (x[k-2], yk),
(x[k-1], y1), (xk, y2)
...
dia k: (x1, yk), (x2, y1), ..., (xk,
y[k-1])
Agora note que no caso|T| = n=
2^kpodemos fazer todos se enfrentarem em n - 1 dias:
divida T em T1 e T2 (|T1| = n/2= |T2|) e faça
todos de T1 enfrentarem todos de T2 em n2 = 2^(k-1) dias.
agora todos os tenistas em T1 precisam se enfrentar
entre si, e todos de T2 precisam se enfrentar entre si também, como os conjuntos
são disjuntos, os processos (jogos dentro de cada partição)podem ocorrer
em paralelo, logo temos que o total de dias necessários (mínimos)
é:
2^(k-1) + 2^(k-2) + + 2 + 1 = 2^k - 1 = n - 1
dias!
não estou tendo idéias de como provar essa minha
conjectura, não dá pra ser simplista e assumir que a maneira ótima de organizar
os jogos é particionando os tenistas em dois conjuntos iguais!
vou pensar melhor!
[ ]'s
- Original Message -
From:
Johann Peter Gustav Lejeune
Dirichlet
To: [EMAIL PROTECTED]
Sent: Monday, September 22, 2003 1:49
PM
Subject: [obm-l] Torneio de tenis
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 exatamenteuma vez por dia.
Ache todos os possiveis valores den."
Desafio
AntiZona: participe do jogo de perguntas e respostas que vai dar1
Renault Clio, computadores, câmeras digitais, videogames e muito
mais!
RE: [obm-l] Torneio de tenis
Acho que 2^k não abrange todas as possibilidades de conjunto. Consegui uma
configuração válida para n=12.
Vamos imaginar uma matriz nxn, onde DIA(A,B) é o dia do jogo do jogador A
versus o jogador B. Consideremos DIA(A,A) = 0, pois não faz sentido o
jogador A jogar contra si mesmo. Por definição, DIA(A,B) = DIA(B,A).
Um resultado possível para o problema com 12 jogadores seria:
0 1 2 3 4 5 6 7 8 9 10 11
1 0 3 4 5 6 7 8 9 10 11 2
2 3 0 5 6 7 8 9 10 11 4 1
3 4 5 0 7 8 9 10 11 2 1 6
4 5 6 7 0 9 10 11 2 1 8 3
5 6 7 8 9 0 11 2 1 4 3 10
6 7 8 9 10 11 0 1 4 3 2 5
7 8 9 10 11 2 1 0 3 6 5 4
8 9 10 11 2 1 4 3 0 5 6 7
9 10 11 2 1 4 3 6 5 0 7 8
10 11 4 1 8 3 2 5 6 7 0 9
11 2 1 6 3 10 5 4 7 8 9 0
Note que a soma de cada linha e cada coluna deve ter o mesmo valor, que é
igual a n * (n-1)/2.
Meu palpite é que a soma (n*(n-1)/2) deve ser par, ou seja, n = 4*k, além da
configuração n=2. Acho que dá para provar que é possível construir esta
matriz:
1 - a primeira linha / coluna com os valores de 0 a n
2 - a diagonal obviamente terá zeros
3 - os dias devem ser intercalados em par/impar. Por exemplo, se DIA(A,B) é
par, DIA(A,B+1) deve ser obrigatoriamente impar
4 - a matriz é preenchida sempre com o menor número, desde que se satisfaçam
as condições anteriores.
Mas aí eu lhe pergunto: E para provar isso tudo, hein??
-Original Message-
From: Domingos Jr. [mailto:[EMAIL PROTECTED]
Sent: Monday, September 22, 2003 5:44 PM
To: [EMAIL PROTECTED]
Subject: Re: [obm-l] Torneio de tenis
Estou com um palpite: n = 2^k
A idéia é simples:
Sejam A e B conjuntos de tenistas com |A| = |B| = k, então são necessários
no mínimo k dias para que todos os tenistas de A enfrentem todos de B sendo
que todo jogador joga uma vez por dia nesses k dias, por exemplo:
A = {x1, x2, ..., xk}, B = {y1, y2, ..., yk}
dia 1: (x1, y1), (x2, y2), , (xk, yk)
dia 2: (x1, y2), (x2, y3), , (x[k-1], yk), (xk, y1)
dia 3: (x1, y3), (x2, y4), , (x[k-2], yk), (x[k-1], y1), (xk, y2)
...
dia k: (x1, yk), (x2, y1), ..., (xk, y[k-1])
Agora note que no caso |T| = n = 2^k podemos fazer todos se enfrentarem em n
- 1 dias:
divida T em T1 e T2 (|T1| = n/2 = |T2|) e faça todos de T1 enfrentarem todos
de T2 em n2 = 2^(k-1) dias.
agora todos os tenistas em T1 precisam se enfrentar entre si, e todos de T2
precisam se enfrentar entre si também, como os conjuntos são disjuntos, os
processos (jogos dentro de cada partição) podem ocorrer em paralelo, logo
temos que o total de dias necessários (mínimos) é:
2^(k-1) + 2^(k-2) + + 2 + 1 = 2^k - 1 = n - 1 dias!
não estou tendo idéias de como provar essa minha conjectura, não dá pra ser
simplista e assumir que a maneira ótima de organizar os jogos é
particionando os tenistas em dois conjuntos iguais!
vou pensar melhor!
[ ]'s
- Original Message -
From: Johann Peter Gustav Lejeune mailto:[EMAIL PROTECTED]
Dirichlet
To: [EMAIL PROTECTED] mailto:[EMAIL PROTECTED]
Sent: Monday, September 22, 2003 1:49 PM
Subject: [obm-l] Torneio de tenis
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.
_
Desafio http://br.rd.yahoo.com/s/c/m/?http://cade.com.br/antizona
AntiZona: participe do jogo de perguntas e respostas que vai dar
1 Renault Clio, computadores, câmeras digitais, videogames e muito mais!
=
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=
Re: [obm-l] Torneio de tenis
Title: Re: [obm-l] Torneio de tenis
on 22.09.03 13:49, Johann Peter Gustav Lejeune Dirichlet at [EMAIL PROTECTED] 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.
