Log in

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

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

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.

[User Picture]From: haran
2005-10-15 08:03 pm (UTC)
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?
(Reply) (Thread)
[User Picture]From: arvindn
2005-10-16 11:46 am (UTC)
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.
(Reply) (Parent) (Thread)
[User Picture]From: haran
2005-10-16 06:40 pm (UTC)
Ah crap, I forgot that the whole thing is divided into rounds.
That solves it.
(Reply) (Parent) (Thread)
From: (Anonymous)
2006-03-29 05:29 pm (UTC)
Although induction is a natural way to go about it, here's something I thought about: Since everyone is equally intelligent, and everyone has the same amount of info at the beginning, all the people who wear red should realize at the same time what their colour is; and hence leave at the same time!
(Reply) (Parent) (Thread)
[User Picture]From: arvindn
2006-03-29 06:16 pm (UTC)
That's true, but it doesn't tell you when they will leave. It doesn't even rule out the possibility that they won't leave at all.
(Reply) (Parent) (Thread)