1. 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á 7 alunos e 7 jantares em dias distintos. Em cada jantar são convidados 3 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 7 dias, um subconjunto de 3 alunos) respeitando essa condição?
Informações relevantes dadas:
  • Número de alunos: 7.
  • Número de jantares (dias): 7 (os dias são consecutivos, portanto numerados/ordenados).
  • Em cada jantar é um grupo de 3 alunos.
  • Restrição: cada par de alunos (um par qualquer dentre os 7) 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 3 que satisfazem a restrição.

Passo 2

Primeiro observe uma consequência simples da contagem de pares: cada jantar com 3 alunos contém \binom{3}{2} pares de alunos. Então, o total de “ocorrências de pares” contabilizadas em todos os jantares é
7\cdot \binom{3}{2}.
Calculemos:
\binom{3}{2}=\frac{3\cdot 2}{2}=3,
logo
7\cdot \binom{3}{2}=7\cdot 3=21.
Agora olhe para o conjunto de todos os pares de alunos possíveis entre 7 alunos: existem
\binom{7}{2}=\frac{7\cdot 6}{2}=21
pares distintos.
Como o número total de pares contabilizados pelos jantares é 21 e o número de pares possíveis também é 21, 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 7 jantares forma uma família de 7 subconjuntos de tamanho 3 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 v=7 pontos e blocos de tamanho 3 trata-se de um sistema do tipo “Steiner triple system” de ordem 7 (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 x. Ele forma pares com os outros 6 alunos, e cada um desses pares deve aparecer exatamente uma vez em algum jantar. Em cada jantar onde x participa ele aparece emparelhado com 2 alunos (pois o jantar tem 3 pessoas). Se r for o número de jantares que x frequenta, então x contribui com 2r pares. Como x precisa cobrir exatamente os 6 pares com os outros alunos,
2r=6 \quad\Longrightarrow\quad r=3.
Portanto cada aluno participa exatamente de 3 jantares. Bom para visualizar: cada vértice tem grau 3 no sistema de blocos.

Passo 4

Agora vamos contar quantas famílias possíveis de 7 blocos (subconjuntos de tamanho 3) existem que satisfazem a condição. Estratagema: fixar um aluno e contar como completar o resto.
Fixe o aluno 1. Nos 3 jantares em que 1 participa, ele aparece em três blocos distintos, e em cada um desses blocos ele se junta a dois alunos formando um par. Esses 3 pares envolvendo 1 devem ser uma partição dos 6 outros alunos em 3 pares. Ou seja, os 6 alunos restantes são emparelhados entre si em três pares disjuntos, e cada par com 1 forma um dos três blocos que contêm 1.
Quantas maneiras existem de particionar 6 objetos em 3 pares? Esse número é o chamado número de emparelhamentos perfeitos de 6 elementos, que é
(6-1)!!=5\cdot 3\cdot 1=15.
(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 3! se necessário dá o mesmo resultado, resultado final 15.)
Então existem 15 maneiras de escolher os três blocos que contêm 1 (cada maneira corresponde a uma partição dos 6 restantes em pares). Para cada uma dessas 15 escolhas, ainda precisamos completar os 4 blocos que não contêm 1 de modo que cada par dos 6 restantes apareça exatamente uma vez (lembrando que três dos pares já foram usados junto com 1, restando 12 pares entre os 6 que ainda precisam ser cobertos por 4 blocos, e 4\cdot 3=12 é exatamente o número de pares que os 4 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 4 blocos restantes — ou seja, cada uma das 15 partições dá origem a exatamente 2 sistemas completos de 7 blocos.
Seja a partição escrita como três pares
(a_1,b_1),\\ (a_2,b_2),\\ (a_3,b_3),
e os três blocos contendo 1 são (1,a_1,b_1),(1,a_2,b_2),(1,a_3,b_3).
Uma forma de completar os outros 4 blocos que cobre todos os pares restantes é escolher os quatro blocos:
(a_1,a_2,a_3),\quad (a_1,b_2,b_3),\quad (b_1,a_2,b_3),\quad (b_1,b_2,a_3).
Verifique mentalmente (ou com pequenas checagens) que cada par entre os 6 elementos aparece em exatamente um desses quatro blocos — combinado com os três blocos que contêm 1, 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 a_i e b_i; ou seja, tomar
(b_1,b_2,b_3),\quad (b_1,a_2,a_3),\quad (a_1,b_2,a_3),\quad (a_1,a_2,b_3).
Esses dois conjuntos de 4 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 1. Assim, para cada uma das 15 partições há exatamente 2 ampliações possíveis.
Portanto o número total de famílias (conjuntos não ordenados) de 7 blocos que satisfazem a condição é
15\cdot 2=30.
(Esse é o fato conhecido de que existem exatamente 30 sistemas de blocos do tipo pedido sobre um conjunto de 7 elementos rotulados; eles são todas isomorfismos do plano de Fano.)

Passo 5

Finalmente, os 7 jantares acontecem em dias distintos, isto é, a família de 7 blocos está ordenada pelo dia. Para cada uma das 30 famílias de blocos, podemos permutar os 7 blocos entre os 7 dias de 7! maneiras. Logo o número total de sequências diárias de convites (modo de designar um bloco a cada dia) é
30\cdot 7!.
Calculemos numericamente:
7! = 5040,
então
30\cdot 5040 = 151200.

Resposta

151200

Exercícios relacionados