There are n people in a room, who each wear a hat of a specific color. They are able to see other people's hats but not their own.
One of them shouted, "If you can see at least 5 red hats and at least 5 white hats, raise your hand!"
Exactly 10 people raised their hands.
What is the minimum value of n that fits this scenario?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
You have a couple of inequalities that should be equalities (case 2, case 4) because "exactly 10 people raised their hands".
Log in to reply
Ah thanks for pointing that out, I've updated my solution (case 4 is now case 3 by the way).
This proof is a good place to use the beloved phrase "without loss of generality" to combine Case 2 and Case 3.
Log in to reply
I've got you covered. :)
I avoided it at Facebook by referring to the majority and minority color with no need to identify any color at all. I use it, but it is not beloved by me. I also made a point that the additional persons beyond the initial 5-6 split can have the majority color hat, or a third neutral color hat with the same result since they will see the initial 5-6.
If 5 people have red hats and 5 have white hats, why can't 1 person have a blue hat making the answer 11?
Log in to reply
Then, only the blue person would raise their hand, but exactly 10 people raised their hands. See case 3 of the solution.
We know that there are five people with red hats and five people with white hats. But they cannot see their own hats, so there must be more people.
If there are 6 + people with a red hat and 6 + people with a white hat, then there are 1 2 + people who would raise their hands-- more than the actual 10.
Therefore there must be five people with a hat of one color (say, red), and more than five with a hat of the other color (white). The people with a red hat can see only four other red hats, so they don't raise their hands. But all people with a white hat will raise their hands. Therefore there are 10 people with white hats. Add the five with a red hat, and we get a total of 1 5 .
You can't conclude that there are exactly 10 people with white hats, in fact, as long as there are 5 people with red hats and at least 6 people with white hats, the colors of the remaining people's hats are completely arbitrary.
For example, let's suppose there are 5 people with red hats and 7 people with white hats, since 10 people are raising hands and they can't be wearing a red hat, we know there must be 3 more people, but their hats can be of any color (say purple, cyan etc.), they don't have to be white.
You are right-- I read this problem as allowing only two colors of hats, but it does not say so. The reasoning does not have to change much, though.
The analysis must start at 11 since there must be at least five red and white hats plus one person (person 11) who can see them all.
If person 11 wears a neutral color (not red nor white) hat that person will be the only hand raised since the others will still only be able to see 4 hats matching their own while seeing 5 of the other color.
If person 11 wears either red or white (the majority color) 6 hands will be raised as all 6 wearing the majority color hat can mutually see 5 hats of the majority hat color and the five of the minority hat color. This, maximizing the number of raised hands, must be the choice so far to achieve a minimum.
If a person 12 is added with the minority color hat the result will 12 raised hands, exceeding the given value of 10. Therefore, no additional hats of the minority color can be added under the given condition of 10 hands raised.
Additional persons wearing either the majority color hat or any neutral color hat will add one hand to the total as each can see the original 5 red and 5 white hats.
Starting from 11 people with 6 hands, 4 more will be required to get the count to 10.
11 + 4 = 15 is the minimum number of people required to have exactly 10 hands raised.
Lets take 5 people with red hat and 10 with white. As people with red hat are will see 4 red hats - : they will not raise their hands. And as people with white hats are seeing 5 red and at least 5 white, they all will raise hands.
Doesn't your solution only shows that n=15 is possible? How do you know that the answer cannot be less than 15?
Problem Loading...
Note Loading...
Set Loading...
First of all, we know there must be at least 5 people with red hats and at least 5 people with white hats (or else no one would be raising their hands).
Hence, denoting R as the number of red hats and W as the number of white hats, there are only 3 cases:
Case 1: If R > 5 and W > 5 , then everyone will be able to see at least 5 red hats and at least 5 white hats and n ⩾ 1 2 , but then that would lead to at least 12 people raising their hands, which is a contradiction.
Case 2: One of R and W equals 5 while the other greater than 5 , without loss of generality, let's suppose that R = 5 and W > 5 , then everyone except those wearing red hats will raise their hands. Since there are 10 people raising hands and none of them are the 5 people wearing red hats, this makes n = 1 0 + 5 = 1 5 .
Case 3: If R = W = 5 , then only those who are not wearing red or white hats will raise their hands, making n = 2 0 .
Thus, the minimum value of n is 1 5 .