Prisoners problems

There are a lot of logic/probabiliy/information theory puzzles involving very intelligent prisoners being executed in creative ways.

Here is a collection of some, hopefully it will grow.

Green eyed prisoners on an island

100 prisonrs are on an island. They have either green or brown eyes.

Everynights they can ask to be freed. If they have green eyes, they are freed, if they have beown eyes, they are executed. Of course there are no mirrors or any reflective material that would allow one to see its own eyes, and communication is strictly forbidden.

One day an external visitor is shown the island by it's owner. The visitor asks if he can give them a hint. The owner agrees that he can only tell them something they already know. So the visitor tells everyone on the island : "at least one of you have green eyes".

100 days later, evey prisoners left the island. How did they do that ?

Prisoners queue

original version

10 prisoners are discussing a strategy for an upcoming execution scheme.

They are about to be put in a queue. From their position each one can see all other people in front of them, but not behind.

An executioner randomly choose a black or white hat and put it on the head of each prisoner in such a way that no one knows what they are wearing. Thus they can see what other prisoners in front of them are wearing (but not behind).

The process goes like this : starting from the prisoner that is last in queue (the one who can see everyone else) each prisoner says outloud "white" or "black". If the color matches the worn hat, he is freed. If not, he is killed. Everyone can hear what other have said before (they however can't tell if one was executed or not).

What is the best strategy to guarantee to save a maximum of prisoners ?

pseudo-hint : there is no information on how many of each hat there is (they could be all white).

pseudo-hint : they don't know in what order they are going to be executed

infinite version

The problem is exactly the same but there are now a countable infinite amount of prisoners. The queue still has a starting point though (the tail only is prolonged)

etc...

more infinite version

Now there is a continuous amount of prisoners. Previously we had a prisoner for each element or $ℕ$, now we have a prisoner for each element or $ℝ$. Let's reformulate the execution pattern so that it makes sens.

Now the hat assignment is a function $f:ℝ→\{\text{white},\text{black}\}$.

The answer of the prisoner $x∈ℝ$ is given knowing the function $g:[0,x)→\{\text{white},\text{black}\}$ of previous annoucements until we get to ask $x$.

hilarious version

Now we get back to the infinite version, but everyone is deaf. The situation is the same but they have no clue what happened before them. Still, there is a way to save 100% of them.

Once you found the solution for the infinite one, you kind of know the solution for this one. But here is my intuition of why this can happen : since an infinite number of people agreed on the strategy, the situation differs from a pure random situation. They get to decide "which random instance" they are running on. That agreement is key, that shared information.

more hats

What about if there are more hat colors ?

even more hats

What about if the hat color is an element of $S^1$ ? ie. the color is picked from the colorwheel. And you have to tell the exact color with no rounding error whatsoever.

2 doors, 2 guardians

original version

A prisoner is in front of two doors. On of them leads to paradise, the other to hell.

There are 2 guardians at the doors. You are allowed to ask them a single question to which the answer is either yes or no. But there is a problem : one of them always tells the truth, the other is always lies. But you don't know which is which.

Can you figure the question that would let you tell which door goes to paradise for sure ?

random version

Same 2 doors, but there is only one guardian. He will answer randomly but in a consistent manner.