Problemas de Lógica

Hoje, por acaso, vi um tweet do Lucas Radaelli com um desafio de lógica e terminei lembrando de um outro sobre penachos de ouro que postei anos atrás e deixei sem resposta. Então resolvi compilar aqui algumas coisas relacionadas... E a resposta do problema lá em baixo, no finalzinho.

O mesmo desafio pode ser encontrado no item 14 de um site esquisito enunciado assim:

As galinhas de penacho dourado 

Era uma vez um galinheiro muito curioso. Todas as galinhas possuíam um lindo penacho dourado, o que era motivo de muito orgulho para elas. Tanto que, se alguma galinha descobre que perdeu seu maravilhoso penacho, no mesmo dia que ela descobre ela se mata. Mas só se mata à meia-noite, em um horário em que geralmente as galinhas estão dormindo. 

Porém, descobrir que perdeu o penacho pode levar muito tempo. Elas não conseguem olhar para o próprio penacho e não se comunicam de forma alguma uma com a outra. Mas são inteligentíssimas. O brilhante raciocínio lógico que elas têm é a única maneira delas descobrirem que perderam o penacho (pobres galinhas, se não fossem tão inteligentes viveriam mais). 

Certo dia, Tio Patinhas descobre esse galinheiro. Ganancioso como ele é, já pensa em ganhar dinheiro com esses penachos. é, já pensa em ganhar dinheiro com esses penachos. Chama seu sobrinho, o Pato Donald, e o manda roubar alguns penachos. Assim ele faz. Enquanto todas as galinhas dormiam, sem que ninguém percebesse, o malvado roubou os penachos de sete galinhas. Mas na fuga, com medo que alguém acordasse, deixou cair um penacho, que ficou no meio do galinheiro. 

Passados alguns dias, todas as galinhas que perderam o penacho se matam, numa mesma noite. Pergunta: quantos dias se passaram e como elas descobriram?

E também um desafio muito similar um amigo meu encontrou numa entrevista do google (e duvido que esse amigo sequer lembre que foi ele quem me mandou o link - até por que tive que atualizar o link que já não existia mais e encontrei um novo), no item 9, traduzido com o google translator e corrigido manualmente:

Todo homem em uma aldeia de 100 casais traíu sua esposa. Toda mulher na aldeia sabe instantaneamente quando um outro homem que não seu marido traiu sua respectiva esposa, mas não sabe sobre seu próprio marido. A vila tem uma lei que não permite adultério. Qualquer mulher que pode evidenciar que seu marido é infiel deve matá-lo naquele mesmo dia. As mulheres da aldeia nunca desobedeceriam a esta lei. Um dia, a rainha da aldeia visita e anuncia que pelo menos um marido foi infiel. O que acontece?

Resposta para os Penachos de Ouro

No fundo é a mesma resposta para todos esses desafios. Neste caso: 2 dias. No caso das galinhas (que, aliás, é um enunciado mil veze melhor do que o que eu fiz além de ser mais correto com o que eu hoje lembro do que escutei originalmente), 7 dias.

O difícil é entender por que. Vou lidar primeiro com o caso mais simples que enunciei.

Começemos imaginando a situação com somente 1 penacho roubado que caiu no chão. Todas aves verão 5 aves com penacho e 1 sem, exceto 1, que verá 6 aves com penacho e saberá que ela está sem, com certeza. As outras estarão na dúvida mas sabem que se for somente 1 ave que perdeu o penacho, ela se matará no mesmo dia seguinte pois ela tera certeza. Então aguardam o dia seguinte para tomarem ação e em somente 1 dia somente 1 ave já se matou.

Como no caso foram dois penachos, são 5 aves vendo "2 sem e 4 com" e 2 aves vendo "1 sem e 5 com". Todas estão em dúvida, mas todas sabem a situação anterior, então todas esperam o primeiro dia. No segundo dia todas estarão vivas, então as 2 aves que viram somente 1 sem já sabem que elas também estão sem penacho, afinal estava uma esperando a outra se matar e não aconteceu por que uma viu que a outra estava sem. No dia 2, as 2 se matam.

Daí a lógica só se repete. O mesmo vale pra 3, 4, 5... No caso das galinhas a resposta é 7 dias.

No caso do desafio do google todos homens morrem em 100 dias, seguindo a mesma lógica acima. Mas li uma outra interpretação que não entendi direito de que "nenhuma esposa mata o marido". Algum comentário? :-P