Save the Prisoners

Posted: February 13, 2011 in Algorithms, Microsoft, Puzzles

Q. There are 10 prisoners and jailer said he will play a game with them next morning. He will make all of them stand in a row and put either of black or white hat on their head. Since, they are standing in a row, they can see the hats in front of them but not the one their head or heads behind them.

Starting from the last, jailer will ask each prisoner what is the color of his own hat. If prisoner gives wrong answer, he will shoot him right at that moment.

Prisoners have to come up with a strategy such that maximum of them can be saved.

A.

The last prisoner will say black if there are odd number of black hats in front of him. For simplicity, lets assume they are in odd number.

  • Second last prisoner can count the black hats in front of him. If he gets odd number, he can conclude the hat on his head is white and black otherwise.
  • Third last prisoner, will keep his ear open on the previous answer and then he’ll calculate of total black hats in front of him and behind him. That way he can decide if total is a odd number and can predict his hat’s color.
  • Using this technique, n-1 prisoners can be guaranteed to be saved.

 

Advertisements
Comments
  1. Anonymous says:

    the question does not specify the total no. of hats. And answer assumes even no. of black hats.

  2. Harsh says:

    Total number of hats will be same as number of prisoner. So, they know it.
    The answer does not assume that there are even number of hats, its just for taking an example. This works even with odd number

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s