(A) Desafio: Jantando com os alunos

Clique no botão abaixo para visualizar o problema.

Problema
(Indicado a partir do 2º ano do E. M.)

Após um semestre de aulas no Clube de Matemática, uma professora resolve se despedir de seus [tex]7[/tex] alunos oferecendo, durante [tex]7[/tex] dias consecutivos de uma semana, [tex]7[/tex] jantares, sendo que em cada um ela convida apenas [tex]3[/tex] alunos.
De quantos modos ela pode fazer os convites, se ela não deseja que um mesmo par de alunos compareça a mais de um jantar?

(Extraído de Análise Combinatória e Probabilidade– Morgado, A. C.; Carvalho. J. B. P.; Carvalho, P. C. P.; Fernandez, P.)

AJUDA

✏ Princípio Fundamental da Contagem, ou Princípio Multiplicativo, para [tex]k [/tex] eventos: Se

um evento E1 puder ocorrer de [tex] m_1 [/tex] maneiras,
um evento E2 puder ocorrer de [tex]m_2 [/tex] maneiras,
[tex]\cdots[/tex]
um evento Ek puder ocorrer de [tex]m_k [/tex] maneiras

e todos esses eventos forem independentes entre si (isto é, a ocorrência de um não muda a quantidade de possibilidades para a ocorrência de outro), então a quantidade de maneiras em que os [tex]k[/tex] eventos ocorrem ao mesmo tempo é:
[tex]\qquad \qquad \boxed{m_1\times m_2 \times \cdots \times m_k} \, .[/tex]
(Se você não se lembra desse Princípio, seria interessante dar uma passadinha nesta Sala de Estudo.)

✏ Combinação simples: Uma das maneiras de agruparmos elementos de um dado conjunto é escolhê-los levando-se em consideração apenas a sua natureza, sem se importar em que ordem eles foram escolhidos ou apresentados. Esse tipo de agrupamento de elementos é denominado uma Combinação simples. Particularmente, quando escolhemos [tex]r[/tex] dentre [tex]n[/tex] elementos de um conjunto dessa forma, dizemos que estamos definindo uma Combinação simples de [tex]n[/tex] elementos tomados [tex]r[/tex] a [tex]r[/tex]. A quantidade desse tipo de agrupamentos é denotada por [tex]C_{n,r}[/tex] ou [tex]C_n^r\,[/tex] e assim definida:

[tex]C_{n,r}=C_n^r=\dfrac{n!}{(n-r)!\,r!} \text{ , com } n,r\in\mathbb{N} \text{ e } r\leqslant n[/tex].

Solução

Vamos representar os [tex]7[/tex] alunos pelas letras [tex]A, B, C, D, E, F[/tex] e [tex]G[/tex].

Note que se, por exemplo, o aluno [tex]A[/tex] vai a um jantar com [tex]B[/tex] e [tex]C[/tex], ele só poderá ir a outro jantar com outros dois estudantes, digamos [tex]D[/tex] e [tex]E[/tex] e, caso haja um terceiro, com os estudantes [tex]F[/tex] e [tex]G[/tex]. Assim, não terá companhia para um quarto jantar.
Logo, cada aluno vai a no máximo [tex]3[/tex] jantares.
Serão [tex]7[/tex] jantares com [tex]3[/tex] estudantes por dia, assim, teremos [tex]21[/tex] convites.
Como são [tex]7[/tex] estudantes e cada um vai a no máximo [tex]3[/tex] jantares, todos vão comparecer a exatamente [tex]3[/tex] jantares.
Bom, se [tex]A[/tex] vai a [tex]3[/tex] jantares, podemos escolher os seus acompanhantes dividindo os outros [tex]6[/tex] alunos em três grupos de [tex]2[/tex].
A primeira dupla pode ser definida de [tex]C_{6}^{2}=15[/tex] maneiras; a segunda de [tex]C_{4}^{2}=6[/tex] maneiras e a terceira de [tex]C_{2}^{2}=1[/tex] maneira.
Repare que não há distinção entre as duplas, logo devemos desconsiderar as permutações entre elas. Assim, pelo Princípio Multiplicativo, temos [tex]\dfrac{15\cdot 6\cdot1}{3!}=15[/tex] modos de escolhermos as companhias para [tex]A[/tex].
Suponha que os estudantes convidados para os [tex]3[/tex] jantares com a participação de [tex]A[/tex] sejam:
[tex]\qquad A\;B\;C[/tex];
[tex]\qquad A\;D\;E[/tex];
[tex]\qquad A\;F\;G[/tex].
E os outros quatro jantares?
- Note que [tex]B[/tex] deverá ir a mais [tex]2[/tex] jantares, nenhum deles na companhia de [tex]A[/tex] e [tex]C[/tex]; e [tex]C[/tex] também deverá ir a mais [tex]2[/tex] jantares, sem [tex]A[/tex] e [tex]B[/tex]. Logo, os [tex]4[/tex] jantares que faltam são:
  [tex]\qquad B\; \Box\; \Box[/tex];
  [tex]\qquad B\; \Box\; \Box[/tex];
  [tex]\qquad C\; \Box\; \Box[/tex];
  [tex]\qquad C\; \Box\; \Box[/tex].
- Como [tex]D[/tex] deve ir a mais [tex]2[/tex] jantares (não pode comparecer a ambos em companhia de [tex]B[/tex] nem a ambos em companhia de [tex]C[/tex]), esses jantares são:
  [tex]\qquad B\; D\; \Box[/tex];
  [tex]\qquad B\; \Box\; \Box[/tex];
  [tex]\qquad C\; D\; \Box[/tex];
  [tex]\qquad C\; \Box\; \Box[/tex].
- De modo análogo, [tex]E[/tex] tem que comparecer a dois jantares, nenhum em companhia de [tex]D[/tex].
  [tex]\qquad B\; D\; \Box[/tex];
  [tex]\qquad B\; E\; \Box[/tex];
  [tex]\qquad C\; D\; \Box[/tex];
  [tex]\qquad C\; E\; \Box[/tex].
  Assim, temos duas possibilidades:
  [tex]\qquad B\; D\; F[/tex];
  [tex]\qquad B\; E\; G[/tex];
  [tex]\qquad C\; D\; G[/tex];
  [tex]\qquad C\; E\; F[/tex].
  ou
  [tex]\qquad B\; D\; G[/tex];
  [tex]\qquad B\; E\; F[/tex];
  [tex]\qquad C\; D\; F[/tex];
  [tex]\qquad C\; E\; G[/tex].
Assim, temos [tex]\boxed{15\cdot 2=30}[/tex] maneiras de montarmos os trios de convidados.
Mas ainda temos que distribuir os trios nos [tex]7[/tex] jantares, o que pode ser feito de [tex]\boxed{7!}[/tex] modos.

Logo, há [tex]\,\fcolorbox{black}{#eee0e5}{$7!\cdot30=151\,200$}\,[/tex] maneiras de a professora do Clube fazer os convites.

Solução elaborada pelos Moderadores do Blog.