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 quantes modos ele pode fazer os convites se ele não deseja que um mesmo par de alunos compareça a mais de um jantar?
  2. Formam-se as combinações simples de classe 5 dos elemente a_{1}, a_{2}, \ldots, a_{12}, as quais são escritas com os elementos em ordem crescente de índices. Quantas são as combinações nas quais o elemento a_{8} ocupa o 3^{\circ} lugar."

Passo 1

Enunciados e dados claros (separei os dois problemas):
Problema 22:
  • Temos 7 alunos distintos.
  • O professor oferece 7 jantares, um em cada um dos 7 dias consecutivos.
  • Em cada jantar comparecem exatamente 3 alunos.
  • Restrição: nenhum par de alunos pode comparecer a mais de um jantar.
  • Pergunta: de quantos modos o professor pode fazer os convites (isto é, de quantas formas pode escolher qual tripla vai em cada dia, respeitando a restrição)?
Problema 23:
  • Temos os elementos a_{1},a_{2},\ldots,a_{12}.
  • Formam-se todas as combinações simples (subconjuntos sem ordem) de tamanho 5, escritas com os elementos em ordem crescente de índices.
  • Pergunta: quantas dessas combinações têm o elemento a_{8} ocupando exatamente o 3^{\circ} lugar (isto é, a_{8} é o terceiro menor índice entre os 5 escolhidos)?

Passo 2

Vamos começar pelo Problema 22 — analisar as consequências da restrição sobre pares.
Cada jantar com 3 alunos contém \binom{3}{2}=3 pares de alunos. Como há 7 jantares, o total de “aparições de pares” (contando multiplicidade) é
7\times 3 = 21.
Por outro lado, o número total de pares distintos entre os 7 alunos é
\binom{7}{2} = \frac{7\cdot 6}{2} = 21.
A restrição diz que nenhum par comparece a mais de um jantar, então não podemos ter repetições de pares. Como o total de aparições (21) coincide com o número total de pares distintos (21), concluímos que cada par de alunos aparece exatamente uma vez entre todos os jantares. Ou seja, as 7 tríades formam uma coleção de blocos de tamanho 3 que cobre cada par exatamente uma vez.

Passo 3

Explicando concretamente o que isso significa (sem termos difíceis): precisamos de uma coleção de 7 triples (subconjuntos de 3 alunos) tal que todo par de alunos apareça em exatamente um desses triples. Esse arranjo é conhecido, no caso de 7 pontos, como o sistema de Fano (ou sistema de blocos que tem exatamente essa propriedade). Algumas propriedades que podemos deduzir sem mais teoria:
  • Cada aluno aparece em um certo número r de jantares. Cada vez que um aluno aparece num jantar ele forma 2 pares (com os outros dois do jantar). Contando pares envolvendo um aluno fixo por dois modos: pelo total de pares que esse aluno forma com os outros 6 alunos, temos 2r = 6, portanto
r = 3.
Isto é, cada aluno participa exatamente de 3 jantares — informação útil para consistência.

Passo 4

Agora precisamos contar de quantas maneiras isso pode ser feito, lembrando que:
  • Os alunos são distintos (rotulados).
  • Os dias são distintos (ordem dos 7 jantares importa).
O que encontramos: a coleção de 7 triples que cobre todos os pares é única em estrutura (o chamado Fano), mas muitas coleções diferentes surgem ao aplicar permutações dos rótulos dos alunos. Uma maneira organizada de contar é:
  1. Fixe uma configuração modelo do Fano (uma coleção de 7 triples sobre 7 rótulos fixos).
  2. Qualquer permutação dos 7 alunos aplicada a essa configuração dá outra coleção válida. Logo, cada permutação em S_7 produz uma coleção de triples (pode ser que duas permutações diferentes produzam a mesma coleção, se uma permutação for uma simetria interna da configuração).
Portanto, o número de coleções distintas de 7 triples sobre o conjunto rotulado de 7 alunos é
\frac{7!}{|\text{grupo de simetrias da configuração}|}.çã

Passo 5

Precisamos então do tamanho do grupo de simetrias (automorfismos) da configuração do Fano. Um argumento direto (claro e curto) para esse tamanho:
  • O plano de Fano pode ser representado pelos 7 vetores não-nulos de \mathbb{F}_{2}^{3} (espaço vetorial sobre o corpo com 2 elementos).
  • As transformações lineares invertíveis de \mathbb{F}_{2}^{3} (o grupo GL(3,2)) permutam esses 7 vetores preservando as colinearidades, logo são automorfismos do Fano.
  • O número de matrizes invertíveis 3\times 3 sobre \mathbb{F}_2 é
(2^{3}-1)(2^{3}-2)(2^{3}-2^{2}) = 7\cdot 6\cdot 4 = 168.
  • Portanto o grupo de simetrias do Fano tem ordem 168.
Assim o número de coleções distintas de 7 triples (como conjuntos, sem ordem entre os dias) é
\frac{7!}{168} = \frac{5040}{168} = 30.

Passo 6

Agora lembrando que os 7 dias são ordenados: para cada uma dessas 30 coleções de 7 triples, podemos atribuir as 7 triples aos 7 dias de 7! maneiras. Logo o número total de modos de fazer os convites, com os dias ordenados, é
30 \times 7! = 30 \times 5040 = 151200.
(Faça uma pausa: resumindo, a restrição força uma única estrutura essencial (Fano), há 30 maneiras distintas de colocá-la sobre os 7 alunos rotulados, e cada colocação pode ser ordenada nos dias de 7! formas.)

Passo 7

Passando ao Problema 23: explicando o raciocínio básico.
Queremos combinações de tamanho 5 onde, na escrita com elementos em ordem crescente de índice, o terceiro elemento é a_{8}. Isso tem interpretação simples:
  • Entre os índices 1,2,\dots,12, queremos escolher 5 índices crescentes (i_1<i_2<i_3<i_4<i_5) com i_3=8.
  • Isso significa que os dois índices menores que 8 (as posições i_1,i_2) devem ser escolhidos dentre os índices 1,2,\dots,7.
  • E os dois índices maiores que 8 (as posições i_4,i_5) devem ser escolhidos dentre os índices 9,10,11,12.

Passo 8

Contagem direta usando combinações:
  • Número de maneiras de escolher os dois elementos que ficam antes de a_{8}: \binom{7}{2}. Calcule:
\binom{7}{2} = \frac{7\cdot 6}{2} = 21.
  • Número de maneiras de escolher os dois elementos que ficam depois de a_{8}: \binom{4}{2}. Calcule:
\binom{4}{2} = \frac{4\cdot 3}{2} = 6.
  • Pelo princípio multiplicativo, o total é
\binom{7}{2}\cdot \binom{4}{2} = 21\cdot 6 = 126.
Se quiser a fórmula geral: o número de combinações de k elementos de \{1,\dots,n\} com o m-ésimo elementos fixado em um valor t é \binom{t-1}{m-1}\binom{n-t}{k-m}. Aqui n=12, k=5, m=3, t=8.

Passo 9

Recapitulando e dando um choque de ânimo: fizemos o problema 22 observando que a contagem de pares força a estrutura do Fano e contamos as colocações rotuladas e as ordens nos dias; no problema 23 aplicamos contagem direta por escolher elementos antes e depois de a_{8}. Você já está no caminho certo — essas estratégias (contar pares, usar simetrias, e dividir escolhas em blocos independentes) são muito usadas em provas.

Resposta

  1. 151200\n
  2. 126

Exercícios relacionados