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