How did you get on with the puzzle last Sunday? It is usually framed in terms of bloodthirsty pirates and treasure, but we liked this way better. I will give the solution at the bottom of this post, but first, this week’s puzzle, Harry’s Hat Game.
The elves have been invited to Harry’s Christmas party and are looking forward to their favourite game, Santa’s Hat. They are blindfolded and place in a line, single file with Jodie at the back. Harry places a paper hat on each of their heads. Some of the hats are red, others are green. They are not told how many hats of each colour there are, but the game is explained before it starts and the elves and Jodie have time to formulate a plan. They will be asked to remove their blindfolds and then to call out, one at a time, either red or green. If the colour they call out is the colour of their own hat (which they cannot see, as there are no reflective surfaces in the room) then they may choose a parcel from under the tree. How many elves get to take a parcel and what is the best strategy to ensure it?
Those of you looking for a classroom activity related to this, could take a look at a lovely set of slides prepared by thephilosophyman which emphasises the combination of logic and empathy needed to solve it. Seems suitable for Christmas.
Now for the solution to last week’s puzzle. You have to assume that not only are the gamers all highly logical, but that they all know that they are all highly logical, otherwise they can’t model how the other players will react to a proposal, but with that assumption, Player 1 proposes that the coins are split as follows:
- Player 1 receives 9951 coins
- The 49 odd ranked players receive 1 coin each
- The others receive no coins
If the proposal is to be rejected then it must be rejected by one of the 49 lowest ranked pirates. The result of doing that, as that pirate could predict, would be that Player 1 loses all rights to any coins and Player 2 gets to propose a solution. But there is no guarantee that Player 2 will improve on the offer, and there is a chance that they might end up with nothing, so the odd ranked players should all vote in favour, and together with the vote of Player 1, the distribution would be accepted.
Of course an odd ranked player might think further ahead and consider that there might be a logical path to an elimination of players leaving a large booty to be shared among a smaller number of players including them. The trick to understanding why that is not better is to use induction.
Suppose at the final stage before an agreed split there are just two players left vying for the prize money. The highest ranked player remaining will propose that they alone should take the entire pot, and since they will vote in favour of this distribution, it will carry and the other player will take nothing, so it is clearly in the interest of any players left to avoid this situation. Therefore if there are three players left vying for the money, then the highest ranked player can offer one of them, the lowest ranked player, one coin to buy their vote, so even if our original odd ranked player is still in the game they will be no better off.
Knowing this, if there are four players left the highest ranked among them can propose to keep all the money except two coins which they distribute to the player ranked in the middle of the other three. They will accept to avoid a situation in which they are the middle ranked player of a remaining three, losing out entirely.
If there are five players left, knowing what will happen if there are three or fewer players left, the top ranked remaining player offers coins to the players 2 and 4 below them in the ranking. They know that if this proposal is rejected then the result will be a proposal cutting them out entirely.
This reasoning process repeats all the way up the chain until the odd ranked players have worked out that they had better vote in favour of the proposal. Player 1 is the clear winner!