PRÁTICA COM QUESTÕES OFICIAIS
Questão 4 (Nível 3) da 2ª fase da OBMEP 2025
Uma prova com 5 questões será aplicada a um grupo de alunos. Cada aluno receberá o resultado por meio de uma sequência de zeros e uns, indicando as questões que errou ou acertou. Por exemplo, a sequência [0 1 0 0 0] indica que o aluno acertou a segunda questão e errou as demais.
a) Liste todas as possíveis sequências de zeros e uns que indicam exatamente duas questões corretas.
b) Explique por que, se a prova for aplicada a 33 alunos, pelo menos dois deles vão receber a mesma sequência de zeros e uns como resultado.
c) Suponha que a prova seja aplicada a um grupo de alunos e que o total de questões respondidas corretamente seja 81. Explique por que podemos garantir que pelo menos dois alunos receberão a mesma sequência de zeros e uns como resultado.
Reportar erro na questão
Resolução comentada
Resolução comentada
a) Cada sequência tem 5 posições, e duas delas devem ser 1 (acertos) e as outras três 0. Basta escolher as duas posições dos uns, o que dá \binom{5}{2}=10 sequências. Listando pela posição do primeiro 1:
- [1\ 1\ 0\ 0\ 0], [1\ 0\ 1\ 0\ 0], [1\ 0\ 0\ 1\ 0], [1\ 0\ 0\ 0\ 1]
- [0\ 1\ 1\ 0\ 0], [0\ 1\ 0\ 1\ 0], [0\ 1\ 0\ 0\ 1]
- [0\ 0\ 1\ 1\ 0], [0\ 0\ 1\ 0\ 1]
- [0\ 0\ 0\ 1\ 1]
São 10 sequências.
b) Cada uma das 5 posições pode ser 0 ou 1, independentemente. O total de sequências possíveis é 2^5=32.
Com 33 alunos e apenas 32 sequências diferentes, o princípio da casa dos pombos garante que duas sequências coincidem. Ou seja, 33 alunos são "pombos" e 32 sequências são "casas".
Com 33 alunos e só 32 sequências possíveis, pelo menos dois recebem a mesma sequência.
c) Vamos supor que todos os alunos tenham sequências diferentes e mostrar que isso é impossível.
Se todas fossem diferentes, haveria no máximo 32 alunos (pelo item b), e o total de acertos seria no máximo a soma dos acertos das 32 sequências possíveis.
Calculamos essa soma por questão. Fixada uma questão, metade das sequências tem 1 nessa posição: as outras 4 posições são livres, o que dá 2^4=16 sequências. Como são 5 questões, o total de uns nas 32 sequências é
(Conferindo por quantidade de acertos: 0\cdot1+1\cdot5+2\cdot10+3\cdot10+4\cdot5+5\cdot1=80.)
Assim, qualquer grupo de alunos com sequências todas distintas tem no máximo 80 acertos no total. Como o total é 81>80, isso é impossível, então há sequências repetidas.
Com 81 acertos no total, as sequências não podem ser todas distintas (o máximo seria 80), logo pelo menos dois alunos recebem a mesma sequência.
Assunto: Princípio fundamental da contagem.
Reportar erro na resolução
Ver como caiu na prova
Fonte: OBMEP 2ª fase 2025 · Nível 3. Prova oficial ↗