Again,

Manoj and Saket brought this interesting puzzle but with their role reversed this time. Saket posed the puzzle and Manoj solved it. I was very close to the solution but Manoj did it before me.

**Problem : **

A prison has six prisoners. One day, the jailer tells them that, he will write a (integer) number from [0,5] on each of the prisoners forehead, a number may be repeated any times and the assignment is completely arbitrary. After that everyone will be able to see all the numbers written except the one on his own forehead. Immediately after that, he will ask each of them to guess his own number, and write it on a piece of paper which the jailer will collect. The prisoners are not allowed to communicate in any manner after the numbering has been done, they obviously cannot see their fellow prisoner’s answers. But they are allowed to communicate with each other before the numbering. If ANY ONE out of the six prisoners makes a correct guess, then all of them will be set free, but if all of them make an incorrect guess then all of them will be executed.

Suggest a strategy for the prisoners that will ensure their freedom.

**Solution :**

Let the prisoners number themselves from [0,5] so that each prisoner

has a distinct number assigned to himself.

Now let the the jailer number them in any arbitrary way.

Let S be the sum of the number written by the jailer.

Claim: S mod 6 = x such that 0 <= x <= 5

That is to say (S mod 6) lies between 0 to 5. Nothing too much. This

is trivial. Any “number mod n” lies between “0 to n-1”.

Now let the guy labelled 0 assume that

S mod 6 = 0

So what he does is that he add up the number he see on other prisoners

forehead, let this number be S_0. Then he add an appropriate number

x_0 such that (S_0 + x_0) mod 6 Â = 0. And he claims that x_0 is

written on his forehead.

Claim: Atleast one prisoner will correctly identify the number on his forehead.

Proof: Let S mod 6 = k. We claim that the kth prisoner will correctly

answer the number on his forehead.

This is because first he will add up the number he sees on other

prisoners forehead, say S_k. Then he will add an appropriate number

x_k such that (S_k + x_k) mod 6 = k. Clearly x_k is written by the

jailer on the forehead of kth prisoner. Thats why S mod n = k.

PS : Manoj states that solution is not his, so I acknowledge whosoever unnamed, intelligent soul out there who came up with this ðŸ™‚

### Like this:

Like Loading...

*Related*

Tags: math, puzzle

This entry was posted on September 26, 2009 at 1:29 pm and is filed under math, puzzle. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

September 26, 2009 at 1:56 pm |

Good puzzle….

ðŸ™‚

Keep it up…

Similar puzzle ðŸ™‚

http://pratikpoddarcse.blogspot.com/2009/08/puzzle-whats-number-on-my-hat.html