No account? Create an account
 Nice puzzle - Arvind Narayanan's journal [entries|archive|friends|userinfo]

## Arvind Narayanan's journal

Research Blog | Web page

Nice puzzle [Oct. 15th, 2005|06:37 pm]
Arvind Narayanan
 [ Tags | puzzle ]

There are n people in a room and each is wearing a hat, either red or blue. Each person can see everyone else's hat but not their own. Everyone is perfectly intelligent and this is known to everyone. There are k people with red hats (k>0). The parties behave as follows: in each instant (or minute or round), if a person can determine with certainty that they are wearing a red hat, they leave the room. There is no communication among parties: their entire behavior consists of either leaving or not leaving the room at each time instant.

Determine the behavior of each person.

Update: forgot to mention that the parties don't know what k is, except that k>0.

 From: 2005-10-15 08:03 pm (UTC) (Link)
If a person in the room sees that nobody has a red hat, then he can determine that k=1 and leave the room, and then everyone else can conclude that k=1 and they all stay.
If a restriction was imposed that k<n, then you can determine everyone's behaviour similiarly for k = n-1, but that restriction is not there in the puzzle.

For any other k, is it even possible for a person to fully determine the color of his hat? Espcially since k is unknown to both parties?
 From: 2005-10-16 11:46 am (UTC) (Link)
OK here's the solution. I'll prove by induction that: "all the people with red hats walk out in round k". Clearly true for k=1. For k>1, consider what happens at the end of round k-1. Since nobody as walked, the people with red hats know what there are at least k red hats (if there were fewer it would contradict the induction hypothesis). Since each red hatter sees only k-1 red hats, they know they themselves are wearing a red hat. So they all walk in round k. This establishes the induction.