Skip to content

Solution to the Prisoner Question (Updated)

June 20, 2008

Khor’s Solution: (Rather complicated and less elegant)

Assign the following : Red = +120 degree , Blue = -120 degree, Green = 0

The last person will calculate the sum of the degree of everyone in front of him/her, then give the following reply if:

Red – The sum of degree is 120.

Blue – The sum of degree is 240.

Green – the sum of degree is 0.

Eg. If the sum is 480 degree, then minus the sum with n*360degree until the sum is less than 360. In this case, the final result is 480-360=120, so the last person will reply “Red”.

The subsequent person can calculate his/her hat color base on the last person’s reply.

Chew’s solution: (More elegant)

1st rule : Red + Blue = Green, Blue + Green = Red, Red + Green = Blue

(The sum of the two color is the third color)

2nd rule : Blue + Blue = Blue etc

(The sum of two same color is the color itself)

Add up all the color using the above rules. Then the last person will tell the sum of the color.

The subsequent person can calculate his/her hat color base on the last person’s reply.

Wen Cin’s solution: (More mathematical but sounds interesting)

“As there are 20 people in front of the last one, exactly two colours must have total whose difference is a multiple of 3. Eg. Red 5, Blue 8, Green 7, then it is the red-blue pair. What the last person does is to announce the odd colour, in this case green. The rest of the gang, knowing this info will calculate accordingly. That way, one can save the 20 and God willing, the last one!

Explanation: Think of the remainders for number of each colour group. Now, there are 20 people in front of the last person and 20=2(mod 3) or it leaves a remainder of 2 when divided by 3. Thus, no matter how many are there for each colour, they must belong to the remainders of these sets (0,0,2), (1,1,0) or (2,2,1) since the total must also leave a remainder of 2 when divided by 3. By choosing the pair with the same remainders, you get a difference which is a multiple of 3. You can always find exactly 2 groups with this property provided the number of people in front is not a multiple of 3.”

Advertisements
5 Comments leave one →
  1. Wencin permalink
    June 25, 2008 10:45 pm

    Sorry, having problem with Internet connection lately. Here’s my side of solution: As there are 20 people in front of the last one, exactly two colours must have total whose difference is a multiple of 3. Eg. Red 5, Blue 8, Green 7, then it is the red-blue pair. What the last person does is to announce the odd colour, in this case green. The rest of the gang, knowing this info will calculate accordingly. That way, one can save the 20 and God willing, the last one!

  2. June 27, 2008 6:35 pm

    Sounds correct to me. But how do you prove that there must be exactly two colours must have total whose difference is a multiple of 3?

  3. Wencin permalink
    June 29, 2008 11:19 am

    Think of the remainders for number of each colour group. Now, there are 20 people in front of the last person and 20=2(mod 3) or it leaves a remainder of 2 when divided by 3. Thus, no matter how many are there for each colour, they must belong to the remainders of these sets (0,0,2), (1,1,0) or (2,2,1) since the total must also leave a remainder of 2 when divided by 3. By choosing the pair with the same remainders, you get a difference which is a multiple of 3. You can always find exactly 2 groups with this property provided the number of people in front is not a multiple of 3.

  4. June 29, 2008 1:37 pm

    I have updated the post with your answer 🙂 Thanks for providing the solution.

  5. Ng Xin Zhao permalink
    July 5, 2008 10:30 am

    I am amazed.

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

%d bloggers like this: