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 que há
alunos e o professor fará
jantares (dias) convidando
alunos em cada jantar, com a restrição de que nenhum par de alunos pode aparecer junto em mais de um jantar. O conteúdo é de teoria de blocos: trata-se de escolher
subconjuntos de tamanho
(blocos) sobre um conjunto de
pontos, sem repetir pares, e depois ordená-los nos
dias.
Passo 2
Cada bloco (jantar) de
alunos contém
pares. Como há
blocos, o total de pares contados é
. Mas
, o número total de pares distintos de
alunos. Para não repetir nenhum par, cada par deve aparecer exatamente uma vez. Esse arranjo de blocos é exatamente um sistema de Steiner de ordem
, chamado STS
.
Passo 3
Em um conjunto fixo de
pontos, o número de sistemas de Steiner STS
(ou seja, de coleções não ordenadas de
blocos de tamanho
que cobrem cada par exatamente uma vez) é
Aqui
é o tamanho do grupo de automorfismos do plano de Fano.
Passo 4
Os jantares são ordenados em
dias distintos, então para cada STS
há
maneiras de atribuir os
blocos aos
dias. Logo, o total de modos de convidar é