[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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:dopikas@uol.com.br]
Sent: Monday, September 22, 2003 5:44 PM
To: obm-l@mat.puc-rio.br
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:peterdirichlet2002@yahoo.com.br>
Dirichlet
To: obm-l@mat.puc-rio.br <mailto:obm-l@mat.puc-rio.br>
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
=========================================================================