great-puzzles
great-puzzles copied to clipboard
sharkdp
wizards and dwarves
another possible solution to minimize the number of dwarves killed is as follows: each dwarf has to say 'black' or 'white'. Each dwarf speaks the color of the hat being worn by the dwarf in front of him/her. This way, only the first dwarf shall be killed in the worst case. All other dwarves shall know the color of their hat, for certainty.
Am I missing something ? it feels lot more simpler solution as compared with computing parity
That doesn't seem to work.
From the puzzle description:
If the dwarf answers incorrectly, the wizards kill him
If he speaks out the color of the dwarf in front of him, how would that work? The one in front of him will now know his color, but the current dwarf dies. And it doesn't scale. Because each dwarf can either communicate information (to the one in front of him) or use the tip that he got from the dwarf behind him.
Ahh, you are right ! :( dwarf can only say one color. About his own hat, or for someone in front.
Of course the Wizards can always engineer it so [the first dwarf] dies, because they know this is the optimal strategy
Unless I misunderstood something, there is a second "optimal" strategy: The first (tallest) dwarf announces the color which does not correspond to the parity he calculated. All dwarves know that the first one chose the opposite colour (because they know the strategy), so all dwarves smaller than the first one select the right hat and survive analogously to how they do it in the first strategy. Before the wizards arrive, the dwarves could throw a dice and select the second strategy instead of the first one with 50% chance. The wizards don't know which strategy was chosen, so the first dwarf survives with 50% chance.
The wizards don't know which strategy was chosen, so the first dwarf survives with 50% chance
Okay, but the first dwarf also survives with 50% in the described strategy, right? So this is an alternative strategy, but not better in some sense.
Edit: this 50% survival chance should probably be included in the solution.
The wizards don't know if the dwarves always select the first strategy (the one currently described in the solution), so when they visit the dwarves village the first time, the first dwarf has 50% survival chance. However, in practice the wizards may assume or learn that the dwarves know only this strategy and then always kill the first dwarf. This is not possible when the dwarves throw a dice to decide on the strategy.
However, in practice the wizards may assume or learn that the dwarves know only this strategy and then always kill the first dwarf. This is not possible when the dwarves throw a dice to decide on the strategy.
I'm not sure if such assumptions about backstory/background knowledge etc. are a tad bit out of scope for such puzzles.
However, in practice the wizards may assume or learn that the dwarves know only this strategy and then always kill the first dwarf. This is not possible when the dwarves throw a dice to decide on the strategy.
Ok. That would be an interesting optimization in the "repeated wizards and dwarves" puzzle. But we are talking about one instance here only.
But we are talking about one instance here only.
According to the description, it happens every year: Once a year, the wizards go over to […]
I'm not sure if such assumptions about backstory/background knowledge etc. are a tad bit out of scope for such puzzles.
Maybe it is possible to change the puzzle so that the described solution is optimal, e.g. The wizards can read the thoughts of the dwarves and thus know their strategy.
Sorry, I should have re-read the actual puzzle and the solution. Too long ago...
I think you are right. Your strategy is better for the once-a-year long-term "game". We could either edit the solution to add your reasoning or modify the puzzle description to phrase it as a one-time event.
I would actually vote for the latter (the puzzle is hard enough already), but I'm open for suggestions.