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 = n1, 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?
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 k1. 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 k1 red hats, they know they themselves are wearing a red hat. So they all walk in round k. This establishes the induction.
Ah crap, I forgot that the whole thing is divided into rounds. That solves it. Thanks
From: (Anonymous) 20060329 05:29 pm (UTC)
 (Link)

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!
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. 