Re: [obm-l] Re: [obm-l] Combinatória - times

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Tue, Jun 28, 2005 at 02:18:41PM -0300, kleinad2@globo.com wrote:
> Oi,
> Eu tenho lá as minhas dúvidas quanto à veracidade do enunciado... Alguém
> aqui na lista saberia provar que é possível esta situação: Para todos os
> quintetos possíveis dentre 12 pessoas, associar um time de 6 jogadores de
> maneira que dois times diferentes tenham no máximo 4 jogadores em comum?

Esta é uma boa pergunta.

O que se está pedindo é um sistema de Steiner S(5,6,12).
Há uma descrição de como construir um aqui:

http://web.usna.navy.mil/~wdj/hexad/node2.html

O resumo é o seguinte: chame os 12 jogadores de
0, 1, 2, ..., 9, A=10, Z=infinito, os elementos da projetivização
do corpo finito Z/(11). Um time é formado pelos quadrados:
Q={0,1,3,4,5,9}.
Os outros times são obtidos aplicando funções
de Möbius f(x) = (ax+b)/(cx+d) com ad-bc = 1 (a,b,c,d em Z/(11)).
Assim, por exemplo,
Q+1={1,2,4,5,6,A},
-1/Q={Z,A,7,6,2,6}
também são times.

[]s, N.

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