Depois de ter dado um curso, um professor resolve se despedir de seus 7 alunos oferecendo, durante 7 dias consecutivos, 7 jantares para 3 alunos, cada. De quantos modos ele pode fazer os convites se ele não deseja que um mesmo par de alunos compareça a mais de um jantar?
Passo 1
O enunciado diz: o professor tem
alunos e, durante
dias consecutivos, em cada dia ele convida
desses alunos para jantar. A restrição é que um mesmo par de alunos não pode comparecer junto a mais de um jantar.
Informações relevantes listadas:
Informações relevantes listadas:
- Há
alunos distintos (vamos tratá‑los como rotulados 1,2,\dots,7). - Em cada dia é escolhido um subconjunto de
alunos (um triplete, sem ordem). - São
dias — portanto serão tripletes escolhidos (um por dia). - Condição: nenhum par de alunos aparece junto em dois dias distintos (ou seja, cada par pode aparecer no máximo uma vez).
- Pergunta implícita: de quantos modos (distintas escolhas de convidados dia a dia) isso pode ser feito, assumindo que os dias são distintos (a ordem dos dias importa)?
Passo 2
Primeiro vamos traduzir a condição dos pares em uma igualdade simples de contagem de pares. Cada jantar (um triplete) contém
pares de alunos. Com
jantares teremos, contando pares por jantar, um total de
pares “ocorridos” ao longo da semana. Mas o total de pares possíveis distintos entre
alunos é
Como a condição proíbe repetição de um mesmo par em dois jantares, esses
pares “ocorridos” devem ser todos pares distintos. Logo os
tripletes cobrem exatamente todos os
pares, cada par aparece exatamente uma vez.
Passo 3
A configuração que tem conjuntos de
elementos (blocos) cobrindo todas as
pares exatamente uma vez é um objeto bem‑conhecido: um sistema de Steiner de parâmetros
, geralmente chamado de sistema de Steiner para
pontos ou de plano de Fano. Propriedades úteis que extraímos:
- Deve haver exatamente
blocos (cada bloco possui pontos e incidências cobre incidências que correspondem aos pares). - Tal sistema existe e, até isomorfismo, é único: é o plano de Fano (os
blocos são fixos estruturalmente, embora possamos renomear os alunos).
Passo 4
Agora vamos contar de quantas maneiras diferentes (com os alunos rotulados) se pode escolher esses
blocos. Como existe apenas uma estrutura (o plano de Fano) até renomeação dos
pontos, o número de maneiras de obter um conjunto de
tripletes satisfazendo a condição é igual ao número de maneiras de etiquetar os
vértices do Fano com os
alunos. Cada etiquetagem bijetiva corresponde a uma cópia etiquetada do plano de Fano, porém duas etiquetagens que diferem por uma automorfismo do plano produzem o mesmo conjunto de blocos em termos de conjuntos de vértices. Portanto o número de sistemas rotulados é
onde
é o número de automorfismos (permutacoes dos 7 vértices que preservam os blocos).
Passo 5
Precisamos agora o tamanho do grupo de automorfismos do plano de Fano. O plano de Fano é o plano projetivo sobre o corpo finito com
elementos; seu grupo linear geral tem ordem
Sobre o corpo
os escalares invertíveis são apenas
, então esse grupo linear coincide com o grupo projetivo que é exatamente o grupo de automorfismos do Fano. Assim
Logo o número de sistemas rotulados (conjuntos de
tripletes sobre a base rotulada
) é
Calculando
, temos
. Assim existem
conjuntos distintos de
tripletes que satisfazem a condição, quando os alunos são rotulados.
Passo 6
Até agora contamos apenas conjuntos de
tripletes (isto é, que jantares acontecem), mas os
dias são distintos e a ordem em que esses
blocos são atribuídos aos dias importa. Para cada conjunto de
blocos podemos permutar esses blocos entre os
dias de
maneiras. Portanto o número total de modos de fazer os convites dia a dia é
Substituindo
obtemos