Source

I got this problem from Rustan Leino, who got it from Sophia Drossopoulou.

I solved it and wrote up my solution.

Problem

100 coins are to be distributed among some number of persons, referred to by
the labels A, B, C, D, .... The distribution works as follows. The person
with the alphabetically highest label (for example, among 5 people, E) is
called the *chief*. The chief gets to propose a distribution of the
coins among the persons (for example, chief E may propose that everyone get
20 coins, or he may propose that he get 100 coins and the others get 0
coins). Everyone (including the chief) gets to vote yes/no on the proposed
distribution. If the majority vote is yes, then that's the final
distribution. If there's a tie (which there could be if the number of
persons is even), then the chief gets to break the tie. If the majority
vote is no, then the chief gets 0 coins and has to leave the game, the
person with the alphabetically next-highest name becomes the new chief, and
the process to distribute the 100 coins is repeated among the persons that
remain. Suppose there are 5 persons and that every person wants to maximize
the number of coins that are distributed to them. Then, what distribution
should chief E propose?

Solution
Reveal

Chief E should propose the distribution $\langle A:1, B:0, C:1, D:0, E:98 \rangle.$ This sounds greedy, but it will work for the following reason.

First, let's determine what will happen if we get down to two players left: A and B. In this case, B should propose $\langle A:0, B:100 \rangle$ because B can vote for it and make it pass unilaterally.

We can now figure out what will happen if we get down to three players left: A, B, and C. In this case, C should propose $\langle A:1, B:0, C:99 \rangle.$ A will vote for this because he knows that if this vote fails the previous paragraph's scenario will occur and he will get nothing. Since A and C vote for it, it succeeds.

We can now figure out what will happen if we get down to four players left: A, B, C, and D. In this case, D should propose $\langle A:0, B:1, C:0, D:99 \rangle.$ B will vote for this because he knows that if this vote fails the previous paragraph's scenario will occur and he will get nothing. Since B and chief D vote for it, it succeeds.

Now, finally, we can see why E should propose $\langle A:1, B:0, C:1, D:0, E:98 \rangle.$ He can count on the votes of A and C because if this vote fails they both get nothing. With the votes of A, C, and E, the vote will pass. It's good to be the chief!