That's basically the same answer as solarflare's with the neighbours.
But you can save more people ;)
Printable View
That's basically the same answer as solarflare's with the neighbours.
But you can save more people ;)
I know it's the same. You just said it didn't work. It does work, even if it is not the best answer.
Ok, this is getting confusing ^^ galathea's answer is not the same as yours, since he says "the next person" and "the previous person", which I take to mean the next person to be asked and the previous person to be asked. This strategy is impossible, since you don't know who will be asked next.
Your answer is relying on "the person next to another person on the left". That means this strategy is viable.
[rambling aimlessly]
Obviously you can describe the group more efficiently than 100 individuals. The number of possible combinations or R/B/W hats is 5151, which can be described in 8 3-bits. (i.e. 3^8>5151)
The problem with this is, how can people who don't know their hats describe the group? Just as there are 3 possible hats for a person, there are 3 possible sets for each person (a set being the percentage of R, B, and W hats in the 100).
[/rambling aimlessly]
[actual solution]
Okay how about this. The first person asked counts the number of red hats he sees. He says "red" if there is an even number and "blue" if there is an odd number. Now everyone knows exactly how many red hats there are!
The second person does the same for blue hats.
98 people are saved!! Yay!! (with 2 people having a 1/3 chance of living as well)
[/actual solution]
[edit: I probably wasn't really clear on this so I'll say it again]
The first person asked counts the number of red hats he sees. He says "red" if there is an even number and "blue" if there is an odd number.
The second person does the same for blue hats.
Then the next person asked, whomever that may be, counts red hats disregarding the hat color of the first person. If his count disagrees (first person said odd and he sees even, or vice versa), then he must be wearing a red hat. The same thing is done using blue hats and the second person's count. Finally, if both of these counts agree, then the person must be wearing a white hat. And that's how the other
98 people are saved!! Yay!! (with 2 people having a 1/3 chance of living as well)
You are getting VERY close to the best possible solution solar :) Just a little bit more effort ;)
The hint is that an answer is a tri-state, but you are only exploiting a two-state for the moment.
You are suggesting that there is a way for the first person to save everybody... I will have to think about this ;).Quote:
Originally posted by Yves M
You are getting VERY close to the best possible solution solar :) Just a little bit more effort ;)
The hint is that an answer is a tri-state, but you are only exploiting a two-state for the moment.
I suppose it seems instinctively theoretically possible.
How about taking [abs(red-blue)%3]? I think that would do it.
No, abs() wouldn't work if red or blue doesn't have the clear numerical majority. So calculate red-blue, then add or subtract 3 enough times to get to 0, 1, or 2. (="R", "W", "B")
You are so close, it's steaming ;)Quote:
Originally posted by solarflare No, abs() wouldn't work if red or blue doesn't have the clear numerical majority. So calculate red-blue, then add or subtract 3 enough times to get to 0, 1, or 2. (="R", "W", "B")
I give up, there is no solution :p.
That would probably bother you more than me ;)!
But I think my latest idea would work, I just didn't describe it well enough. The first person is able to say whether the difference between the number of red hats and blue hats is a multiple of three or one more or one less.
Assuming it's a multiple of three, then the second person seeing the same difference among the 98 people (excluding himself and the first person) has a white hat. If it's one more then he has a blue hat, and if it's one less he has a red hat. The same argument works for when the original number is one more or one less than a multiple of three, but with a shift.
solarflare... think about the first guy and continue your idea... if its even say one color, but if its odd, you still have two choices that can signal the others... so use those two colors to do what the second person would do...
But that doesn't work, because if the number is even, you lose the opportunity to transmit that extra bit of information.
Does that mean you know the answer, galathaea ? If you don't want to put it on the thread, you can PM me ;)Quote:
Originally posted by galathaea
solarflare... think about the first guy and continue your idea... if its even say one color, but if its odd, you still have two choices that can signal the others... so use those two colors to do what the second person would do...
I thought I saw the answer with my post, but wanted solarflare to make the final connections (since he had done all the hard work of moving it to that case of 98 saved minimum -- which was pure brilliance if you ask me). However, solarflare seemed to capture the problem that I had overlooked. The only option to overcome that issue is if the first person is really able to make a true sacrifice and say a non-existant color (say yellow) which is an immediate death but allows for the extra bit of communication needed to save at least 99.
Since an odd number of hats are seen, there are four possibilities of parity to transmit that sum to an odd number.
odd + even + even (and the two other permutations)
odd + odd + odd
label the first three with the color that is odd, and the fourth with the alternate color...
but I don't know if that is what is being asked for...
Continuing on what Gal said ..
Let
Red B W
...................................................
(odd + 1 ) + even + even = 100
(even + 1) + even + odd = 100
(even + 1) + odd + even = 100
(odd + 1 ) + odd + odd = 100
say he falls into case row 1:
He saw odd number of reds, even number of blue and even number of white ... then he needs to say Red.
Is there a problem with this approach?
Yes, if he sees 33 each red, blue, and white hats.Quote:
Originally posted by voidspace
Continuing on what Gal said ..
Let
Red B W
...................................................
(odd + 1 ) + even + even = 100
(even + 1) + even + odd = 100
(even + 1) + odd + even = 100
(odd + 1 ) + odd + odd = 100
say he falls into case row 1:
He saw odd number of reds, even number of blue and even number of white ... then he needs to say Red.
Is there a problem with this approach?
Yves, can you tell me what's wrong with my answer?
There is nothing wrong with it, but you can save one more person.Quote:
Originally posted by solarflare
Yves, can you tell me what's wrong with my answer?
The best possible solution saves 99.33 people. It is fairly close to what you have proposed.
If he says anything else than "red", "blue" or "white", they all die, so "yellow" is not an option.Quote:
say a non-existant color (say yellow) which is an immediate death but allows for the extra bit of communication needed to save at least 99.
As a hint, don't think about parity, but about a tri-state, since both the answer and the number of hat colors have three possible values.