Quantos alunos deve haver em uma sala para podermos afirmar que pelo menos dois estudantes tenham a mesma nota em uma determinada prova, se a nota é graduada em um número inteiro de 0 a 10 ?
Passo 1
O enunciado pergunta: quantos alunos devem haver em uma sala para podermos afirmar que pelo menos dois estudantes tenham a mesma nota em uma prova, sabendo que a nota é graduada em um número inteiro de
a
?\n
Informações relevantes dadas pelo enunciado:\n
Informações relevantes dadas pelo enunciado:\n
- As notas possíveis formam o conjunto
.\n - Cada aluno recebe exatamente uma nota desse conjunto.\n
- O que queremos é um número mínimo de alunos que garanta, em qualquer distribuição de notas, que existam pelo menos dois alunos com a mesma nota.\n
Passo 2
Primeiro vamos entender o que significa “garantir” no contexto de problemas assim. Garantir significa: não importa como as notas são distribuídas entre os alunos, a condição (aqui: ter pelo menos dois com a mesma nota) sempre ocorre. Ou seja, consideramos o pior caso possível para tentar evitar repetições; se mesmo nesse pior caso a repetição ocorre, então está garantido.\n
Um jeito prático de pensar no pior caso é tentar colocar os alunos de modo que todos tenham notas diferentes. Se for possível que todos tenham notas diferentes com um certo número de alunos, então esse número ainda não garante repetição. Se com um certo número de alunos já for impossível atribuir notas todas diferentes, então aí a repetição é obrigatória.\n
Um jeito prático de pensar no pior caso é tentar colocar os alunos de modo que todos tenham notas diferentes. Se for possível que todos tenham notas diferentes com um certo número de alunos, então esse número ainda não garante repetição. Se com um certo número de alunos já for impossível atribuir notas todas diferentes, então aí a repetição é obrigatória.\n
Passo 3
Agora uma ferramenta clara para esse tipo de raciocínio: o Princípio da Casa dos Pombos (pigeonhole principle). Vou explicar de forma simples e dar a ideia por trás dele:\n
- Imagine que temos
“caixas” (chamaremos de “caixas” ou “categorias”) e colocamos objetos nessas caixas. Se , então alguma caixa receberá pelo menos dois objetos. Essa é a afirmação do princípio.\n - Intuição: se cada caixa comportasse no máximo um objeto, então o número máximo de objetos que cabem sem repetir caixa é
. Logo, para colocar mais que objetos tem de ocorrer repetição em alguma caixa.\n - Forma formal curta: se assumíssemos que nenhuma caixa tem mais de um objeto, então o total de objetos seria no máximo
; então se essa suposição é falsa, logo existe caixa com pelo menos dois objetos.\n
Esse princípio é extremamente útil quando temos um conjunto finito de categorias (aqui, as notas) e queremos garantir coincidências.\n
Passo 4
Aplicando ao nosso problema:\n
- As “caixas” são as notas possíveis: o conjunto
. O número de caixas é .\n - Os “objetos” são os alunos, cada um colocando-se numa caixa correspondente à sua nota.\n
Pelo Princípio da Casa dos Pombos, se o número de alunosfor maior que , isto é, se , então haverá pelo menos uma nota que aparece em pelo menos dois alunos — exatamente o que queremos garantir.\n
Passo 5
Agora precisamos saber o menor número
que satisfaz isso. Pelo raciocínio anterior qualquer
com
serve. O menor inteiro maior que
é
.\n
Para verificar que é realmente mínimo, veja que com
alunos é possível evitar repetições: basta dar aos
alunos as
notas distintas
. Nesse caso não há dois alunos com a mesma nota. Portanto
alunos não garantem repetição, mas
já garantem.\n
Para verificar que
Passo 6
Resumo didático e memória para a prova (truque prático): quando você tem
possibilidades distintas e quer garantir que duas coisas caiam na mesma possibilidade, precisa de
objetos. Aqui
(as notas), então resposta
. Guarda esse padrão — é muito usado em combinatória básica.\n
Força aí — a conclusão é curtinha, mas vale um pouco de atenção em provas: sempre verifique quantas categorias existem e aplique .\n
Força aí — a conclusão é curtinha, mas vale um pouco de atenção em provas: sempre verifique quantas categorias existem e aplique