✏ Link do problema para dispositivos da Apple.
Problema
(Indicado a partir do 9º ano do E. F.)
Alice escolheu um número do conjunto [tex]A=\{1, 2, 3, \dots, 19, 20\}[/tex].
Bob vai tentar determiná-lo fazendo perguntas sobre propriedades matemáticas desse número e Alice deverá responder apenas Sim ou Não.
Por exemplo, Bob pode perguntar se é um número par e Alice responderá Sim ou Não.
É possível Bob ter certeza que irá determinar o número que Alice escolheu fazendo apenas [tex]4[/tex] perguntas?
💡 Ajuda 💡
Princípio das casas de pombos: Se tivermos [tex]n+1[/tex] pombos para serem colocados em [tex]n[/tex] casas, então pelo menos uma casa deverá conter mais de um pombo.
(Se você não conhece esse Princípio, clique AQUI.)
Solução
- Observe que uma pergunta envolvendo uma propriedade matemática [tex]P_1[/tex] reparte o conjunto [tex]A[/tex] em dois subconjuntos: o subconjunto [tex]A_1[/tex] contendo elementos que possuem a propriedade e o subconjunto [tex]A_0[/tex] contendo elementos que não possuem a propriedade. Pode ocorrer de um desses subconjuntos ser vazio.
- Uma nova pergunta envolvendo outra propriedade matemática [tex]P_2[/tex] irá, de forma análoga, repartir o subconjunto [tex]A_1[/tex] em dois subconjuntos: [tex]A_{11}[/tex] contendo elementos que satisfazem [tex]P_2[/tex] e [tex]A_{10}[/tex] contendo elementos que não satisfazem [tex]P_2[/tex]. De forma semelhante, o subconjunto [tex]A_0[/tex] será divido nos subconjuntos [tex]A_{01}[/tex] e [tex]A_{00}[/tex].
- Ao final das quatro perguntas, Bob terá dividido o conjunto [tex]A[/tex] em no máximo [tex]2^4=16[/tex] subconjuntos.
Como o conjunto [tex]A[/tex] possui [tex]20[/tex] elementos, segue, pelo Princípio da Casa dos Pombos, que pelo menos um desses [tex]16[/tex] subconjuntos terá mais de um elemento. Assim, dependendo das perguntas formuladas por Bob, o número escolhido por Alice pode estar em um conjunto com mais de um elemento. Nesse caso, haverá pelo menos dois números que se enquadram em todas as respostas “sim” de Alice e Bob não poderá determinar qual deles foi escolhido, sem que faça mais uma pergunta.
Portanto, Bob não poderá ter certeza que irá determinar o número que Alice escolheu fazendo apenas [tex]4[/tex] perguntas.
Solução elaborada pelos Moderadores do Blog.