The only way I could think that could work is if the dwarves followed the pattern (starting with the first):
[1] identifiy the next dwarfs hat color (and die)
[2] identify own hat color (and live)
...thus saving n/2 dwarves...
Printable View
The only way I could think that could work is if the dwarves followed the pattern (starting with the first):
[1] identifiy the next dwarfs hat color (and die)
[2] identify own hat color (and live)
...thus saving n/2 dwarves...
I assume this is not allowed:
The one in the back guesses his own color. And they say "I think I have ***" if the one in front of them has a white hat and, "***, I think", if the one in front of them has a black hat.
If that's not allowed, then they could change some slight way they speak the word that is only audible if you know they're doing it.
Not allowed, I guess? ;)
But,so, they start at the back of the line? And there are no limitations to the number of hats? Eg. they may all be black?
The tallest dwarf exchanges hats with the next tallest and says the color of his original hat. The second dwarf says this color, lives, and switches hats again with a shorter dwarf. This always saves at least n-1 dwarfs since they all, at one point, wore the same color hat.
Very clever! But wouldn't that be cheating?
Okay, Perspective's riddle reminded me of a riddle I heard a while ago. A riddle I liked a lot ;).
Three people are lined up. They may not look back or touch each other. They can only see the people in front of them.
So let's say we have person A, B and C. A can see B and C. B can see C. C can't see anyone.
Then, someone comes with 5 stickers: 3 black and 2 white, and puts one on the back of each. So, again, A can see B's and C's dots, B can see C's dot.
They are not allowed to speak unless they want to say which color they think the dot they have on their back is. If one gets it wrong, they all die. If one gets it right, they all live.
They're smart, and all always survive. How?
I already had, but it's good to see you join. :)
There are a few questions remaining:
Do the dwarves know in advance the value of n, i.e. the total number of dwarves?
Do the dwarves know in advance the number of black hats?
Do the dwarves know whether a guess was right or wrong?
And just to be sure: the dwarf that can see all other dwarves will start making a guess, right?
Greets,
Philip
>Do the dwarves know in advance the value of n, i.e. the total number of dwarves?
Yes, or they could count at the time of the game.
>Do the dwarves know in advance the number of black hats?
No. There could be anywhere from 0 to n black hats.
>Do the dwarves know whether a guess was right or wrong?
nope!
>And just to be sure: the dwarf that can see all other dwarves will start making a guess, right?
Yes.
Here's a clue: The information any dwarf has is the colour of the hats in front of him and the answers of all dwarves behind him.
I doubt that. If all get a black sticker, there's no way to tell.
But I can think of at least some ways that will make them survive:
If A sees two white stickers, he can immediately answer "black". He must remain silent in all other cases. If A doesn't say anything, then B and C know that their respective stickers are not both white. Hence if B sees a white sticker, he can immediately answer "black". If he doesn't, then C knows that his hat is not white, so he can answer "black".
Greets,
Philip
Exactly ;).
So why, if you provide the right answer, would there be no way to tell if all were black? ;)
Because the situations WBB and BBB are indistinguishable for all dwarves.Quote:
So why, if you provide the right answer, would there be no way to tell if all were black?
Greets,
Philip
Unless they know which two stickers are not used.
Okay, let's say we have BBB.
The one on the back remains silent. So the two on front know they are not WW.
The one in the middle remains silent, because he doesn't see W in front of him.
The one in the front now knows he has B.
Exactly your method ;). Same for WBB.
I have a solution, but I think it involves cheating:
The first dwarf simply says the color of the hat directly in front of him. The 2nd dwarf thus knows its own hat color. If the third dwarf has a white hat, the 2nd one says his own hat color immediately, otherwise he waits a minute until he says his hat color. This way, the next dwarf knows is own hat color and the dwarves continue this way, saving at least n-1 dwarves.
I can't stop thinking of the hats as a bitstring, but I don't see how this will help.
Greets,
Philip
It does help. The bitstring can be anything. And if we're not "cheating", everyone can either say 1 or 0. The one in the back can say only 1 or 0, being able to help only ONE person in the bitstring, as a range of bits can never be compressed as a single bit, assuming the string is entirely random.
So, we need some way to say more than 1 or 0. But I would consider this cheating. Sure, we can communicate in other ways, but I don't think it's fair here...