Question

100 pessoas são postas em uma fila e cada uma delas recebe um chapéu preto ou branco. Cada pessoa só consegue ver os chapéus das pessoas que estão a sua frente. É pedido que cada uma delas tente adivinhar a cor do seu chapéu. Qual o máximo número de acertos que se pode garantir, dado que as pessoas podem combinar uma estratégia antes de recebê-los.

Answer 1

Resposta:

99

Explicação passo-a-passo:

Primeiro observe que não é possível garantir 100 acertos, pois ninguém da fila tem como saber a cor do chapéu do último da fila. Vou explicar a estratégia para garantir 99 acertos. Primeiro uma observação:

(OBS)

Somando ou subtraindo dois números pares obtemos um número par

Somando ou subtraindo dois impares obtemos um número par

Somando  ou subtraindo um par e um impar obtemos um número impar.

Suponha que as pessoas da fila são P₁, P₂, ..., P₁₀₀, onde P₁ é o primeiro e P₁₀₀ o último. Vamos atribuir números para os chapeus. O Preto vale 1 e o branco vale 0. x₁₀₀ é o valor do chapéu na pessoa P₁₀₀, x₉₉ o da pessoa P₉₉ e assim sucessivamente. Ou seja, cada um dos números x₁, x₂, ..., x₁₀₀ pode ser 0 ou 1.

P₁₀₀ falará primeiro. Ele irá somar o valor dos chapéus que está vendo (ou seja, ele calcula o valor de (x₁ + x₂ + ... + x₉₉) e responderá branco se a soma for par e preto caso contrário.

P₉₉ é o próximo. Ele precisa descobrir a cor do seu próprio chapéu. Note que:

x₉₉ = (x₁ + x₂ + ... + x₉₉) - (x₁ + x₂ + ... + x₉₈)

Mas ele sabe se (x₁ + x₂ + ... + x₉₉) é par ou impar  pela resposta de P₁₀₀ e sabe se (x₁ + x₂ + ... + x₉₈) é par ou impar (porque ele sabe cada um dos valores x₁,  x₂, ..., x₉₈. Então usando a observação (OBS) ele descobre se x₉₉ é par ou impar. Como x₉₉ só pode ser 0 ou 1, ele descobriu qual a cor do seu chapéu.

P₉₈ é o próximo. Ele sabe a paridade de (x₁ + x₂ + ... + x₉₉)  pela resposta de P₁₀₀, sabe o valor de x₉₉ pela resposta de P₉₉ e sabe os valores de x₁, x₂, ..., x₉₇ porque pode ver os chapeus. Como

x₉₈ = (x₁ + x₂ + ... + x₉₉) - (x₁ + x₂ + ... + x₉₇) - x₉₉

usando a observação (OBS) ela pode descobrir se x₉₈ é par ou impar. Assim P₉₈ descobre se x₉₈ é 0 ou 1 e descobre a cor do seu chapéu

P₉₇ é o seguinte. Ele sabe a paridade de (x₁ + x₂ + ... + x₉₉)  pela resposta de P₁₀₀, sabe o valor de x₉₉ e x₉₈ pelas respostas de P₉₉ e P₉₈ e sabe os valores de x₁, x₂, ..., x₉₆ porque pode ver os chapeus. Como

x₉₇ = (x₁ + x₂ + ... + x₉₉) - (x₁ + x₂ + ... + x₉₆) - x₉₉ - x₉₈

usando a observação (OBS) ela pode descobrir se x₉₇ é par ou impar. Assim P₉₇ descobre se x₉₇ é 0 ou 1 e descobre a cor do seu chapéu.

E assim sucessivamente

Obs.: Não estava no enunciado, mas estou assumindo que podem responder em qualquer ordem, e que os demais podem escutar as respostas.

Edit

Esqueci de falar, mas isso é o mesmo de cada pessoa falar "branco" se a soma dos chapeus brancos que viu com a quantidade de "branco" que as outras pessoas falaram for par e preto caso contrário.