Problema
(Indicado a partir do 6º ano do E. F.)
Quando 100 prisioneiros foram levados a uma prisão, o carcereiro lhes avisou:
- – Eu darei a vocês uma noite para conversarem entre si. Então cada um de vocês será colocado em uma cela individual e não poderá mais se comunicar com os demais. A partir de então, a cada dia levarei um de vocês a uma sala com uma lâmpada que, no primeiro dia da sequência de visitas, estará apagada. Ao sair da sala, vocês podem deixar a lâmpada acesa ou apagada. Se algum dia um de vocês me disser que todos já visitaram a sala e isto for verdade, eu libertarei todos. Mas se a informação não for verdadeira, eu jogarei todos vocês aos crocodilos! Eu lhes garanto que todos irão, eventualmente, visitar a sala e que nenhum de vocês deixará de visitar a sala enquanto alguém não decidir falar.
Determine uma estratégia que os presos podem elaborar para terem certeza de que algum dia todos serão libertados.
Adaptado de Combo session – OBM.
Solução
Na noite na qual os prisioneiros passarão juntos, eles poderão combinar a seguinte estratégia:
– Definir um Líder entre eles.
– Este Líder será a única pessoa que poderá alterar o estado da lâmpada mais de uma vez.
– Os outros prisioneiros poderão apenas apagar (ou acender, será o oposto do que o Líder fizer) uma única vez.
– O Líder salvará a todos.
O plano funcionará da seguinte forma:
- O Líder é o único que poderá acender (ou apagar, decisão opcional) a lâmpada.
- Os outros 99 prisioneiros devem apagar a lâmpada (ou acender, o contrário do Líder ) uma ÚNICA vez.
- Toda vez que o Líder entrar na sala, ele acende a lâmpada (ou apaga, dependendo da decisão inicial); se ela já estiver acesa, ele a mantem assim.
- O Líder contará as vezes que ele acender a lâmpada (ou apagar, dependendo da decisão inicial).
- Quando cada um dos outros 99 prisioneiros for para a sala, ele apagará a lâmpada na primeira vez que a encontrar acessa, e deixará a lâmpada do jeito que ela está nas outras vezes que ele voltar à sala.
- Conclusão: Quando o Líder acender a lâmpada pela 99ª vez, ele imediatamente concluirá que todos os prisioneiros já alteraram o estado da lâmpada uma vez cada um, ou seja, todos já passaram pela sala. Assim, ele comunicará o fato ao carcereiro e todos os 100 prisioneiros serão libertados!
Observação: A parte sobre a decisão inicial se o Líder apaga ou acende a lâmpada é só para mostrar que a estratégia não é alterada, se combinarem de os prisioneiros só acenderem uma vez a lâmpada ou só apagarem uma vez, respectivamente. O importante é que a ação dos 99 seja contrária à ação do Líder e que eles só a façam uma ÚNICA vez.
Solução enviada pelo Clube As Incógnitas da Matemática
Participaram da discussão do problema os seguintes Clubes:
Águias da Matemática; Amigos da Matemática; Clube Filhos de Gauss; Clube dos Pensadores; Eu amo matemática; Fênix da Matemática; FOX; Gênios Naturais; Incógnitas da Matemática; Math Error; Mentes Geométricas; OMXM; Os equacionistas; Os Geométricos; Os Modulares; Os Pitagoricos do CEMMA; Paladinos da Matemática; Vim te calculei.