Problem #11 - the salvation of the monks

< change language

Today's problem is a riddle of the same style as problems #09 and #10.

Problem statement: the island depicted above used to be home to $2018$ monks that led a simple life, far from the bad, vain and consumerist habits of today's societies. Between many other deprivations, the monks never saw themselves on the mirror nor on any other reflecting surface. One day the volcano in the centre of the island - slowly but steadily - started hinting at an incoming eruption and the monks grew worried as the days passed. Some days later, at exactly 23h59, a divine being showed itself to the monks in their dreams and offered them a painless death - thus avoiding the wrath of the volcano - as long as every monk found out the colour of his eyes. The divine being also told them that every monk in the island had either blue or green eyes and that there was at least one monk with blue eyes. The divine being left with its final condition: every day, at 23h59, all monks who knew the colour of their eyes would be taken in peace.
Depending on the number $k$ of monks with blue eyes ($k > 0$) will the monks save themselves? In how many days?

Solution: the easiest way to arrive at the solution is by starting with a small number of monks with blue eyes and keep extending the train of thought to increasing values of $k$. Let us start with $k = 1$.

Set $k = 1$ and let us say that the day when the divine being appeared in the monks' dreams at 23h59 was day $0$, making the next morning the morning of day $1$, making the day after that day, day $2$, and so on and so forth.
Suppose now that we are the only monk with blue eyes. Day $1$ I wake up and notice that none of the other $2017$ monks has blue eyes. Because the divine being told me that $k$ was strictly greater than $0$ - i.e. there is at least one monk with blue eyes - I must be the only monk with blue eyes and at 23h59 of day $1$ I am taken in peace. Suppose now we are one of the $2017$ monks with green eyes. Day $1$ we wake up and see: one monk with blue eyes and $2016$ monks with green eyes. The divine being only said that $k > 0$ and thus we are uncertain of whether $k = 1$ or $k = 2$, this depending on the colour of my own eyes. Either way, by the end of day $1$ I am not sure of the colour of my eyes... Nonetheless, I do know that if it is the case that $k = 1$, then the monk I saw with blue eyes would have been taken. If I wake up the next morning and that monk is still alive then $k = 2$ and I must have blue eyes as well. Because (we are assuming) there is only one monk with blue eyes, I wake up in the morning of day $2$ and conclude I have green eyes. But all other monks can complete this train of thought and thus everyone realizes they have green eyes. At 23h59 of day $2$ all monks with green eyes are taken in peace. If $k = 1$, we need $2$ days for all monks to save themselves.

We can, and we should, try to repeat this train of thought for $k = 2$ unless we are pretty sure of how this process should generalize.

Let $k = 2$. Say we are one of the two monks with blue eyes. Day $1$ I wake up and notice there is $1$ monk with blue eyes and $2016$ monks with green eyes. I am not sure if $k = 1$ or $k = 2$. Either way, I know that if it is the case that $k = 1$, day $2$ I will wake up and one of the monks will be gone. Therefore, when I wake up in the morning of day $2$ and notice the monk with blue eyes is still alive, I conclude that I have blue eyes. Because of that, at 23h59 of day $2$ me and the other monk with blue eyes are taken in peace. Now let us say I am one of the monks with green eyes. Day $1$ I wake up and see two monks with blue eyes and $2015$ monks with green eyes, making me wonder whether $k = 2$ or $k = 3$. If it is the case that $k = 2$, in the morning of day $3$ the other two monks will be gone and I will be able to conclude that I have green eyes, much like the other $2015$ monks. This means that at 23h59 of day $3$ the $2016$ monks with green eyes are taken in peace, i.e. if $k = 2$ the monks need $3$ days to earn their salvation.

We start to notice a recursive pattern in our train of thought. For the reader that is yet to be convinced, try repeating the same train of thought for $k = 3$ and conclude that we need $4$ days for salvation. We now present the generic proof:

We will proceed to prove that, under the conditions of the problem statement and assuming that the number $n$ of monks on the island is finite, with $0 < k < n$ monks with blue eyes, the monks need $k+1$ days to earn their salvation. For that, we will use induction on the number $t$ of monks with blue eyes. Define the statement $P(t)$: "with $t$ blue eyed monks, they take $t$ days to find out the colour of their eyes" and $P'(t)$: "with $t$ blue eyed monks, the monks with green eyes need $t+1$ days to find out the colour of their eyes".

The beginning of the proof shows that both $P(1)$ and $P'(1)$ are true. Now we show $P(t) \implies P(t+1)$ and $P(t) \implies P'(t)$.
Suppose $P(t)$ is true and that $k = t+1$. Any of the $t+1$ monks with blue eyes will wake up day $1$ and see $t$ monks with blue eyes, as well as $n-t-1$ monks with green eyes, making that monk wonder if $k = t$ or $k = t+1$, given that he does not know the colour of his own eyes. Nonetheless, the monk knows that $P(t)$ is true and, if it is really the case that $k = t$, at 23h59 of day $t$ all the $t$ monks with blue eyes will be gone and the monk will wake up in the morning of day $t+1$ only to find his friends were released. If it is not the case that $k = t$, the other $t$ blue eyed monks won't be gone by the morning of day $t+1$ leading to the obvious conclusion that $k = t+1$. In addition, that day at 23h59 the $t+1$ blue eyed monks are taken in peace. We conclude that $P(t+1)$ is true. By induction, this proves that $P(t)$ is true for all values of $t$ that make sense, i.e. $t < n$.

Now we show that $P(t) \implies P'(t)$, which concludes the proof. If $k = t$, day $1$ every green eyed monk will see $t$ monks with blue eyes and $n-t-1$ monks with green eyes, wondering if $k = t$ or $k = t+1$. Either way, the monk knows that $P(t)$ is true and if he wakes up in the morning of day $t+1$ and the other $t$ blue eyed monks are gone he concludes that his eyes must be green, i.e. he took $t+1$ days to find out he had green eyes. This train of thought can be carried out by any of the $n-t$ monks with green eyes and at 23h59 of day $t+1$ they are all taken in peace. This concludes our proof.

Summing up, if an island has $n$ monks and $0 < k < n$ monks with blue eyes, $k+1$ days are needed for all the monks to earn their salvation.

Did this make sense? What did you think of this problem? Leave your thoughts in the comments section!

O problema de hoje é um desafio de lógica, ao estilo dos problemas #09 e #10.

Enunciado: na ilha da imagem acima vivem $2018$ monges que levam uma vida de simplicidade, longe dos vícios das sociedades consumistas e vaidosas dos dias de hoje. Entre muitas outras privações, os monges nunca se viam ao espelho, nem em nenhuma outra superfície refletora. Certo dia o enorme vulcão no centro da ilha começou a dar sinais de atividade e os monges ficaram preocupados. Nessa noite, às 23h59, uma divindade apareceu-lhes nos sonhos e ofereceu-lhes uma morte indolor - evitando assim a fúria do vulcão - que seria dada a todos os monges que descobrissem a cor dos seus olhos. Para tal, a divindade disse-lhes ainda que na ilha todos os monges tinham olhos azuis ou verdes e que havia pelo menos um monge com olhos azuis. A divindade partiu então, mas não sem antes dizer que todos os dias, às 23h59, seriam levados em paz todos os monges que já soubessem a cor dos seus olhos.
Dependendo do número $k$ de monges com olhos azuis ($k > 0$) será que todos os monges se conseguem salvar? Em quantos dias?

Solução: para construir a solução, uma pessoa tem de começar por imaginar o que acontece quando o número de pessoas com olhos azuis é pequeno, e ir raciocinando para os casos com mais pessoas de olhos azuis. Façamos então o raciocínio completo para o caso $k = 1$.

Tome-se $k = 1$. O dia em que a divindade apareceu às 23h59 é o dia $0$, o dia da manhã seguinte será o dia $1$, o dia depois desse o dia $2$, por aí fora.
Suponhamos que somos o único monge com olhos azuis. Dia $1$ acordo e reparo que nenhum monge dos $2017$ restantes tem olhos azuis. Como a divindade me disse que $k$ era estritamente maior que $0$, então é o caso em que sou o único monge de olhos azuis e nesse dia às 23h59 sou levado em paz. Assim o monge de olhos azuis precisa apenas de $1$ dia para descobrir a cor dos seus olhos. Suponhamos agora que somos um dos monges com olhos verdes. Dia $1$ acordo de manhã e vejo um monge de olhos azuis e $2016$ monges de olhos verdes. Sei apenas que $k > 0$ pela divindade, e ter visto os restantes monges permite-me concluir que $k = 1$ ou $k = 2$, consoante eu tenha olhos verdes ou azuis, respetivamente. De qualquer das maneiras, ao fim do dia $1$ não posso ter a certeza... No entanto, sei que se $k = 1$ então o monge de olhos azuis que vi terá sido levado em paz às 23h59 do dia $1$. Assim, se dia $2$ o monge de olhos azuis ainda estiver vivo, é porque $k = 2$ e eu também tenho olhos azuis. Se dia $2$ o monge de olhos azuis tiver sido levado, é porque eu tenho olhos verdes. Ou seja, se $k = 1$ todos os $2017$ monges de olhos verdes concluem que têm os olhos verdes, e portanto às 23h59 do dia $2$ são todos levados em paz. Concluindo, se $k = 1$ então são precisos $2$ dias para que todos os monges se salvem.

Podemos, e devemos, experimentar repetir o raciocínio para $k = 2$, a não ser que já tenhamos a certeza de como é que este processo se generaliza.

Tome-se $k = 2$. Suponhamos que somos um dos dois monges com olhos azuis. Dia $1$ acordo e noto que há $1$ monge de olhos azuis e $2016$ monges de olhos verdes. Fico na dúvida entre $k = 1$ e $k = 2$. No entanto sei que se $k = 1$, dia $2$ de manhã o monge que vi ter olhos azuis foi levado. Assim, quando acordo dia $2$ e vejo que o monge de olhos azuis ainda está vivo, concluo que tenho olhos azuis. Desta feita, às 23h59 do dia $2$ eu e o outro monge de olhos azuis somos levados em paz. Suponhamos agora que somos um dos $2016$ monges de olhos verdes. Dia $1$ acordo e noto que há $2$ monges de olhos azuis e $2015$ monges de olhos verdes. Fico na dúvida entre $k = 2$ e $k = 3$, consoante eu tenha olhos verdes ou azuis, respetivamente. Ainda assim consigo concluir que se for o caso que $k = 2$, dia $2$ às 23h59 os dois monges de olhos azuis são levados em paz e portanto basta-me esperar pela manhã do dia $3$. Se os dois monges de olhos azuis tiverem sido levados, concluo que também tenho olhos verdes. Assim, se $k = 2$ os $2016$ monges de olhos verdes concluem que têm olhos verdes na manhã do dia $3$ e são levados em paz às 23h59 do dia $3$, i.e. se $k = 2$ são precisos $3$ dias para que todos os monges se salvem.

Começamos a notar um padrão recursivo no raciocínio dos monges. Para o leitor que ainda não esteja convencido, aconselha-se que se repita o raciocínio para $k = 3$ e para verificar que são necessários $4$ dias. Passamos de seguida para a prova genérica:

Vamos provar que nas condições do enunciado, e assumindo apenas que o número $n$ de monges na ilha é finito e que o número de monges de olhos azuis é $0 < k < n$, são precisos $k+1$ dias para que todos os monges se salvem. Para tal, procedemos por indução no número $t$ de monges com olhos azuis. Considerem-se as afirmações $P(t)$: "havendo $t$ monges de olhos azuis, estes precisam de $t$ dias para descobrirem a cor dos seus olhos" e $P'(t)$: "havendo $t$ monges de olhos azuis, os monges de olhos verdes precisam de $t+1$ dias para descobrirem a cor dos seus olhos".

Por um parágrafo anterior temos que tanto $P(1)$ como $P'(1)$ são verdade. Mostramos agora que $P(t) \implies P(t+1)$ e que $P(t) \implies P'(t)$.
Suponhamos que $P(t)$ é verdade e que $k = t+1$. Qualquer um dos $t+1$ monges de olhos azuis vai acordar dia $1$ e ver que há $t$ monges de olhos azuis à sua frente e $n-t-1$ monges de olhos verdes, ficando obviamente na dúvida se $k = t$ ou $k = t+1$, já que não sabe a cor dos seus próprios olhos. No entanto, o monge sabe que $P(t)$ é verdade, e portanto se for o caso em que $k = t$, às 23h59 do dia $t$ os monges de olhos azuis serão levados em paz e quando o monge acordar dia $t+1$ basta procurar esses $t$ monges. Assim, se de facto $k = t+1$, na manhã do dia $t+1$ os outros $t$ monges de olhos azuis ainda estão vivos e conclui-se que $k = t+1$. Isto implica que às 23h59 desse dia, o dia $t+1$, esses $t+1$ monges de olhos azuis serão levados em paz. Concluímos assim que $P(t+1)$ é verdade. Por indução, isto prova que $P(t)$ é verdade para qualquer $t$ que faça sentido, i.e. $t < n$.

Mostramos agora que $P(t) \implies P'(t)$, o que concluirá a prova. Se $k = t$, dia $1$ de manhã um monge verde vê $t$ monges de olhos azuis e $n-t-1$ monges de olhos verdes, ficando na dúvida se $k = t$ ou $k = t+1$. No entanto, ele sabe que $P(t)$ é verdade e se dia $t+1$ ele acordar e os $t$ monges tiverem sido levados, ele conclui que tinha olhos verdes, i.e. precisou de $t+1$ dias para perceber que tinha olhos verdes. Este raciocínio pode ser feito por qualquer um dos $n-t$ monges de olhos verdes e portanto às 23h59 do dia $t+1$, todos os monges de olhos verdes são levados em paz, o que conclui a nossa prova.

Assim, se uma ilha tiver $n$ monges com $n > k > 0$ monges de olhos azuis, são precisos $k+1$ dias para que todos os monges possam ser salvos.

Então, que tal? Deixa o teu feedback na secção dos comentários!

  - RGS