- 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: há
alunos e
jantares em dias distintos. Em cada jantar são convidados
alunos. A condição é que “um mesmo par de alunos” não compareça a mais de um jantar. A pergunta é: de quantos modos o professor pode fazer os convites (ou seja, de quantas maneiras escolher, para cada um dos
dias, um subconjunto de
alunos) respeitando essa condição?
Informações relevantes dadas:
- Número de alunos:
. - Número de jantares (dias):
(os dias são consecutivos, portanto numerados/ordenados). - Em cada jantar é um grupo de
alunos. - Restrição: cada par de alunos (um par qualquer dentre os
) pode aparecer junto em no máximo um jantar.
O problema pede o número total de sequências (uma escolha para cada dia) de subconjuntos de tamanho
que satisfazem a restrição.
Passo 2
Primeiro observe uma consequência simples da contagem de pares: cada jantar com
alunos contém
pares de alunos. Então, o total de “ocorrências de pares” contabilizadas em todos os jantares é
Calculemos:
logo
Agora olhe para o conjunto de todos os pares de alunos possíveis entre
alunos: existem
pares distintos.
Como o número total de pares contabilizados pelos jantares é
e o número de pares possíveis também é
, e como a restrição proíbe repetições de pares, concluímos que cada par de alunos deve aparecer exatamente uma vez em algum jantar. Não pode faltar nenhum par (caso faltasse, o total seria <21) e não pode haver repetição (pela condição). Portanto o conjunto de
jantares forma uma família de
subconjuntos de tamanho
que cobre cada par exatamente uma vez.
Esse objeto combinatório tem nome: é um sistema de blocos em que cada par aparece exatamente em um bloco; para
pontos e blocos de tamanho
trata-se de um sistema do tipo “Steiner triple system” de ordem
(conhecido como plano de Fano). Mas não precisamos usar teoria avançada: vamos usar contagens elementares a seguir.
Passo 3
Vamos contar quantas vezes cada aluno aparece nos jantares. Fixe um aluno
. Ele forma pares com os outros
alunos, e cada um desses pares deve aparecer exatamente uma vez em algum jantar. Em cada jantar onde
participa ele aparece emparelhado com
alunos (pois o jantar tem
pessoas). Se
for o número de jantares que
frequenta, então
contribui com
pares. Como
precisa cobrir exatamente os
pares com os outros alunos,
Portanto cada aluno participa exatamente de
jantares. Bom para visualizar: cada vértice tem grau
no sistema de blocos.
Passo 4
Agora vamos contar quantas famílias possíveis de
blocos (subconjuntos de tamanho
) existem que satisfazem a condição. Estratagema: fixar um aluno e contar como completar o resto.
Fixe o aluno
. Nos
jantares em que
participa, ele aparece em três blocos distintos, e em cada um desses blocos ele se junta a dois alunos formando um par. Esses
pares envolvendo
devem ser uma partição dos
outros alunos em
pares. Ou seja, os
alunos restantes são emparelhados entre si em três pares disjuntos, e cada par com
forma um dos três blocos que contêm
.
Quantas maneiras existem de particionar
objetos em
pares? Esse número é o chamado número de emparelhamentos perfeitos de
elementos, que é
(Explicação curta: você escolhe o par do primeiro elemento de entre 5 opções, depois para os 4 restantes escolhe par entre 3 opções, e para os últimos 2 sobra 1; dividindo por
se necessário dá o mesmo resultado, resultado final
.)
Então existem
maneiras de escolher os três blocos que contêm
(cada maneira corresponde a uma partição dos
restantes em pares). Para cada uma dessas
escolhas, ainda precisamos completar os
blocos que não contêm
de modo que cada par dos
restantes apareça exatamente uma vez (lembrando que três dos pares já foram usados junto com
, restando
pares entre os
que ainda precisam ser cobertos por
blocos, e
é exatamente o número de pares que os
blocos cobrem).
Vou mostrar uma construção explícita que, dada a partição em pares, fornece exatamente duas possíveis ampliações para os
blocos restantes — ou seja, cada uma das
partições dá origem a exatamente
sistemas completos de
blocos.
Seja a partição escrita como três pares
e os três blocos contendo
são
.
Uma forma de completar os outros blocos que cobre todos os pares restantes é escolher os quatro blocos:
Uma forma de completar os outros
Verifique mentalmente (ou com pequenas checagens) que cada par entre os
elementos aparece em exatamente um desses quatro blocos — combinado com os três blocos que contêm
, isso cobre todos os pares uma única vez. Essa é uma construção válida.
A segunda ampliação possível é obtida trocando, em todos os três pares simultaneamente, os papéis de
e
; ou seja, tomar
Esses dois conjuntos de
blocos são distintos (não coincidem) e ambos completam a partição dada. Pode-se checar que não existe outra forma diferente de completar mantendo os três blocos com
. Assim, para cada uma das
partições há exatamente
ampliações possíveis.
Portanto o número total de famílias (conjuntos não ordenados) de
blocos que satisfazem a condição é
(Esse é o fato conhecido de que existem exatamente
sistemas de blocos do tipo pedido sobre um conjunto de
elementos rotulados; eles são todas isomorfismos do plano de Fano.)
Passo 5
Finalmente, os
jantares acontecem em dias distintos, isto é, a família de
blocos está ordenada pelo dia. Para cada uma das
famílias de blocos, podemos permutar os
blocos entre os
dias de
maneiras. Logo o número total de sequências diárias de convites (modo de designar um bloco a cada dia) é
Calculemos numericamente:
então