Problema com prisioneiros e bonés, cuja cor precisa ser determinada
Recreação / / December 31, 2020
O sistema de fechamento vê todas as tampas, mas só pode dizer "preto" ou "branco", ao mesmo tempo em que informa a todos sobre as informações ocultas. Os presos não sabem o número total de bonés pretos e brancos, há mais de duas opções possíveis. Mas eles estão limitados a apenas duas versões quando se trata do conceito de paridade: o número pode ser par ou ímpar.
A chave para resolver o problema é esta: os presos concordam que o primeiro a responder dirá, por exemplo, "preto", se ele vir um número ímpar de letras pretas na frente, e "branco" se ele vir um número par de letras pretas cápsulas.
Vejamos o exemplo da imagem acima. O prisioneiro mais alto # 1 vê três bonés pretos à frente. Ele fala "preto" em voz alta. Isso fornece a todas as outras pessoas a informação de que existe um número ímpar de letras maiúsculas à frente. O primeiro preso errou com a cor do boné, mas tudo bem: uma vez que é permitido responder incorretamente.
A prisioneira # 2 vê um número ímpar de bonés pretos na frente dela. Ela percebe que é branca e responde corretamente. O prisioneiro # 3 vê um número par de bonés pretos e adivinha que está usando um boné preto que os dois primeiros prisioneiros viram.
Cativa nº 4 ouve a resposta e percebe que deveria procurar um número par de bonés pretos, pois havia um preto atrás dela, mas ela vê apenas um à frente e conclui que seu boné é preto. Os prisioneiros nº 5-9 procuram um número ímpar de bonés pretos, que acabam de ver, enquanto percebem que estão usando bonés brancos. A vez é o décimo prisioneiro. Se o prisioneiro # 9 viu um número ímpar de letras pretas, isso significa apenas uma coisa - o prisioneiro # 10 tem uma tampa preta.
É assim que esse algoritmo funcionaria para qualquer conjunto de hubcaps. Para o primeiro participante, a probabilidade de uma resposta incorreta é de 50%, mas a informação sobre paridade par-ímpar, que ele dará, permitirá ao restante dos cativos adivinhar a cor de seu boné.
Cada entrevistado começará a avaliar o número de limites pares e ímpares à frente. Se o número calculado em sua mente não coincide com o que ele vê, então seu boné é da mesma cor. Cada vez neste caso, o próximo respondente leva em consideração que a imparidade dos limites restantes agora mudou.
Este quebra-cabeça é a tradução de um vídeo TED-Ed.