Problem #10 - Alice and the Maths Hatter

O problema de hoje é um enigma de lógica, tal como o problema #09!

Enunciado: A Alice e mais três amigos estavam a passear descontraídamente no País das Matemáticas quando foram apanhados a passear em propriedade privada. No País das Matemáticas todos os crimes são punidos com a máxima severidade, já que todos os que cometem um crime têm uma última oportunidade, na forma de um enigma: se o criminoso resolver o enigma, é absolvido; caso contrário é executado. Quando a Alice e os três amigos foram apanhados a cometer uma ilegalidade, coube ao chapeleiro matemático criar o enigma deles. O chapeleiro matemático fez o seguinte: fechou a Alice numa sala isolada e colocou os outros três amigos, o Bernardo, o Carlos e a Diana, numa escada, todos virados para o degrau seguinte. O chapeleiro pôs ainda um chapéu na cabeça de cada um dos quatro e disse-lhes: peguei em dois chapéus brancos e em dois chapéus pretos e pu-los nas vossas cabeças, um chapéu por cada um de vocês. Não se podem mexer nem podem falar uns com os outros; se um de vocês conseguir descobrir a cor do chapéu na sua cabeça, serão os quatro libertados.
(Os amigos são dispostos como na imagem, e o Bernardo só vê os chapéus do Carlos e da Diana; o Carlos só vê o chapéu da Diana; a Diana e a Alice não conseguem ver um único chapéu).
Será que os amigos se conseguem libertar? Como?

Solução: das duas, uma: ou o Carlos e a Diana têm chapéus da mesma cor ou de cores diferentes. Se tiverem chapéus da mesma cor (por exemplo se forem os dois pretos), então o Bernardo consegue ver dois chapéus pretos e portanto conclui que tanto ele como a Alice têm de ter os chapéus brancos que faltam.

Se o Carlos e a Diana tiverem chapéus de cores diferentes (por exemplo a Diana chapéu branco e o Carlos chapéu preto), então o Bernardo não tem como saber qual é a cor do seu próprio chapéu, portanto não diz nada. Mas passado algum tempo, o Carlos percebe que o Bernardo ainda não adivinhou e pensa: "se o Bernardo não adivinhou, é porque eu e a Diana temos chapéus de cores diferentes, porque se tivéssemos chapéus de cores iguais ele saberia o que fazer". Assim, o Carlos pode concluir que tem um chapéu preto porque a Diana tem um chapéu branco.

Pergunta bónus: se tivermos uma fila infinita de matemáticos, todos com um chapéu branco ou preto E se todos os matemáticos conseguirem ver todos os chapéus exceto o próprio E se eles conseguirem comunicar uns com os outros, será que há alguma estratégia que eles podem seguir para que apenas um número finito de matemáticos morra?

Solução da pergunta bónus: (assumindo o Axioma da Escolha) quando damos os chapéus aos matemáticos, criamos uma sequência de preto/branco que podemos ver como uma sequência de $0$s e $1$s. Por exemplo se os primeiros três matemáticos tiverem chapéus pretos e todos os outros tiverem chapéus brancos, temos a sequência $(1,1,1,0,0,\cdots)$. Vamos dizer que duas sequências são parecidas se forem iguais em todos os valores exceto num número finito de posições. Por exemplo, a sequência em que todos os matemáticos têm chapéus brancos é parecida com a sequência anterior porque apenas os três primeiros valores são diferentes: $(\underline{0}, \underline{0}, \underline{0}, 0, 0, \cdots)$.

Para qualquer sequência $S$, podemos pensar em todas as sequências que são parecidas com essa sequência. Vamos chamar a esse grupo de sequências parecidas $[S]$. O que os matemáticos devem fazer é: dentro de cada grupo $[S]$ possível, devem escolher uma sequência de que gostem e devem memorizá-la. Apenas uma sequência por grupo. Quando lhes derem os chapéus, cada matemático deve olhar à volta para ver os chapéus dos seus colegas e perceber a que grupo $[S]$ é que a sequência dos chapéus deles pertence. Assim que perceber o grupo em que está, ele vai lembrar-se da sequência que tinha memorizado e vai assumir que a cor do chapéu dele é a que corresponde à cor da sequência. Assim, apenas um número finito de matemáticos vai falhar, já que a sequência que eles memorizaram e vão reproduzir vai ser parecida com a sequência verdadeira dos chapéus, i.e. só vai ser diferente num número finito de posições.

This post's problem is a riddle much like that of problem #09!

Statement: Alice and three other friends were casually strolling in the Mathsland when they were caught trespassing private property. In the Mathsland all crimes are severely punished because all offenders are given a chance to win their freedom: they are given a riddle and if they solve it they are absolved; otherwise they are executed. When Alice and Bob, Charles and Diana where caught trespassing, the Maths Hatter was the one who was to create their riddle. He did as follows: Alice was locked in an isolated room and Bob, Charles and Diana were taken to a staircase, which one of them put on a step and facing forward. He also took two black hats and two white hats and put one on each of the friends. He told them: each one of you has a hat from a set of two black and two white hats; you are not allowed to move nor talk with eachother; if any of you is able to tell the colour of its hat then you are all freed.
(The friends are placed as in the above picture, with Bob being only able to see Charles and Diana's hats; Charles only being able to see Diana's and with both Diana and Alice not being able to see a single hat).
Will the friends be able to free themselves? How?

Solution: either Charles and Diana have hats of the same colour, or not. If their hats are of the same colour (say they are both black), then Bob can see two black hats and will be able to deduce his own hat has to be white (just like Alice's).

If Charles and Diana have hats of different colours (say Diana has a white hat and Charles a black hat) then Bob won't be able to tell the colour of his hat, meaning he won't say a thing. After a while, Charles will understand Bob is still silent and thinks: "if Bob hasn't guessed his own hat it means Diana and me have hats of different colours, because if our hats had the same colour he would know what to do". Therefore, Charles concludes his hat is black because he sees Diana with a white hat.

Bonus question: if we have an infinite queue of mathematicians, each one of them with a black or white hat AND if all mathematicians can see every other mathematician's hat AND if they can all communicate with each other, is there a strategy to be followed by them in order to ensure only a finite number of mathematicians guesses wrong?

Solution for the bonus question: (assuming the Axiom of Choice) when we look at each matematician's hat we can create a sequence of $0$s and $1$s. For example, if everyone has a white hat except for the first three mathematicians, then we would have the sequence $(1,1,1,0,0,\cdots)$. Let us say two sequences are alike if they are the same except for a finite number of positions. As an example, the sequence we get when all mathematicians have a white hat and the previous sequence are alike because they differ only in the first three positions: $(\underline{0}, \underline{0}, \underline{0}, 0, 0,\cdots)$.

For any sequence $S$ we can think of all the other sequences with which $S$ is alike. Let us call that group of alike sequences $[S]$. What the mathematicians must do is: for every single group $[S]$ they must pick a sequence they like and memorize it. When they are given the hats, they must look at their colleagues and recognize in which group $[S]$ their hat sequence belongs. Then they will remember the sequence they all memorized from that group and each mathematician will say his hat is of the colour corresponding to his position on the memorized sequence. Only a finite number of mathematicians guesses wrong because the sequence they will recreate and the real sequence are alike, i.e. they differ only in a finite number of positions.

  - RGS