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