Algumas pessoas estão sossegadinhas e em fila, cada uma com um chapéu na cabeça. Os chapéus só podem ter uma de duas cores, mas quantas pessoas é que vão conseguir adivinhar a sua?

Enunciado do problema

Algumas pessoas, vamos dizer que são \(n\) pessoas, estão em fila. (Claro que estão a mais de 2m umas das outras, o distanciamento social deve ser cumprido por todos nós.)

Cada pessoa tem um chapéu na cabeça, tal como a imagem em cima mostra. Cada chapéu é, ou claro, ou escuro, mas ninguém sabe qual é o chapéu que tem na cabeça e as pessoas só podem olhar em frente sem se mexerem. (Exceto para respirarem e piscarem os olhos.)

Assumindo que podem fazer uma reunião de equipa antes de serem alinhados e receberem os seus chapéus, que plano engenhoso é que têm todos de combinar para que o maior número de pessoas consiga acertar na cor do seu próprio chapéu? Podemos supor que as pessoas que falharem vão para a prisão, e obviamente queremos manter o maior número possível de pessoas fora da prisão. A única coisa que se sabe é que há duas cores de chapéus, não sabemos quantos chapéus de cada cor vão ser distribuídos ou quem vai receber o quê.

Resumindo, o teu objetivo é engendrar o melhor plano possível para salvar tantas pessoas quantas possível, e determinar quantas pessoas é que o teu plano salva, em média.

Também é importante tomares nota do seguinte:

• as pessoas não podem comunicar depois de serem postas em fila;
• os palpites podem ser feitos pela ordem que quiseres;
• cada pessoa tem apenas uma tentativa;
• todos ouvem os palpites de toda a gente, mas só quem está atrás de quem faz o palpite é que tem maneira de ver se essa pessoa acertou ou erro. Os outros ficam sem saber se o palpite estava certo ou errado.

Se precisares de clarificar alguma coisa, não hesites em perguntar na secção de comentários em baixo.

Solução

A minha proposta de solução vai ser publicada [aqui][sol] quando tiverem passado duas semanas desde a publicação deste problema. Também podes usar o link para partilhar a tua própria solução nos comentários. Por favor, não escrevas a tua solução nos comentários aqui em baixo.

Este problema foi-me colocado pelo meu amigo LeafarCoder.

Se gostaste deste problema e se gostavas de receber novos problemas diretamente na tua caixa de correio, então subscreve a newsletter dos Problemas.

[sol]: ../../solutions/hats-in-a-line