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