- 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?
- Formam-se as combinações simples de classe 5 dos elemente
, as quais são escritas com os elementos em ordem crescente de índices. Quantas são as combinações nas quais o elemento
ocupa o
lugar."
Passo 1
Enunciados e dados claros (separei os dois problemas):
Problema 22:
- Temos
alunos distintos. - O professor oferece
jantares, um em cada um dos dias consecutivos. - Em cada jantar comparecem exatamente
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
. - Formam-se todas as combinações simples (subconjuntos sem ordem) de tamanho
, escritas com os elementos em ordem crescente de índices. - Pergunta: quantas dessas combinações têm o elemento
ocupando exatamente o lugar (isto é, é 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
alunos contém
pares de alunos. Como há
jantares, o total de “aparições de pares” (contando multiplicidade) é
Por outro lado, o número total de pares distintos entre os
alunos é
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
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
triples (subconjuntos de 3 alunos) tal que todo par de alunos apareça em exatamente um desses triples. Esse arranjo é conhecido, no caso de
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
de jantares. Cada vez que um aluno aparece num jantar ele forma 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 alunos, temos , portanto
Isto é, cada aluno participa exatamente de
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
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 é:
- Fixe uma configuração modelo do Fano (uma coleção de 7 triples sobre 7 rótulos fixos).
- Qualquer permutação dos
alunos aplicada a essa configuração dá outra coleção válida. Logo, cada permutação em 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
triples sobre o conjunto rotulado de
alunos é
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
vetores não-nulos de (espaço vetorial sobre o corpo com elementos). - As transformações lineares invertíveis de
(o grupo ) permutam esses vetores preservando as colinearidades, logo são automorfismos do Fano. - O número de matrizes invertíveis
sobre é
- Portanto o grupo de simetrias do Fano tem ordem
.
Assim o número de coleções distintas de
triples (como conjuntos, sem ordem entre os dias) é
Passo 6
Agora lembrando que os
dias são ordenados: para cada uma dessas
coleções de
triples, podemos atribuir as
triples aos
dias de
maneiras. Logo o número total de modos de fazer os convites, com os dias ordenados, é
(Faça uma pausa: resumindo, a restrição força uma única estrutura essencial (Fano), há
maneiras distintas de colocá-la sobre os 7 alunos rotulados, e cada colocação pode ser ordenada nos dias de
formas.)
Passo 7
Passando ao Problema 23: explicando o raciocínio básico.
Queremos combinações de tamanho
onde, na escrita com elementos em ordem crescente de índice, o terceiro elemento é
. Isso tem interpretação simples:
- Entre os índices
, queremos escolher índices crescentes com . - Isso significa que os dois índices menores que
(as posições ) devem ser escolhidos dentre os índices . - E os dois índices maiores que
(as posições ) devem ser escolhidos dentre os índices .
Passo 8
Contagem direta usando combinações:
- Número de maneiras de escolher os dois elementos que ficam antes de
: . Calcule:
- Número de maneiras de escolher os dois elementos que ficam depois de
: . Calcule:
- Pelo princípio multiplicativo, o total é
Se quiser a fórmula geral: o número de combinações de
elementos de
com o
-ésimo elementos fixado em um valor
é
. Aqui
,
,
,
.
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
. 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
-
\n -