Maths Olympiad Prep

Library / /78 of 86

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it United States

Problem:

Five mathematicians find a bag of 100 gold coins in a room. They agree to split up the coins according to the following plan:
- The oldest person in the room proposes a division of the coins among those present. (No coin may be split.) Then all present, including the proposer, vote on the proposal.
- If at least 50%50\% of those present vote in favor of the proposal, the coins are distributed accordingly and everyone goes home. (In particular, a proposal wins on a tie vote.)
- If fewer than 50%50\% of those present vote in favor of the proposal, the proposer must leave the room, receiving no coins. Then the process is repeated: the oldest person remaining proposes a division, and so on.
- There is no communication or discussion of any kind allowed, other than what is needed for the proposer to state his or her proposal, and the voters to cast their vote.
Assume that each person is equally intelligent and each behaves optimally to maximize his or her share. How much will each person get?

Problem:

Five mathematicians find a bag of 100 gold coins in a room. They agree to split up the coins according to the following plan:
- The oldest person in the room proposes a division of the coins among those present. (No coin may be split.) Then all present, including the proposer, vote on the proposal.
- If at least 50%50\% of those present vote in favor of the proposal, the coins are distributed accordingly and everyone goes home. (In particular, a proposal wins on a tie vote.)
- If fewer than 50%50\% of those present vote in favor of the proposal, the proposer must leave the room, receiving no coins. Then the process is repeated: the oldest person remaining proposes a division, and so on.
- There is no communication or discussion of any kind allowed other than what is needed for the proposer to state his or her proposal, and the voters to cast their vote.
Assume that each person wishes to maximize his or her share of the coins and behaves optimally. How much will each person get?

Solution

Solution:

The first (oldest) person will get 98 coins, the second will get no coins, and one coin apiece will go to two of the last three people. If we write the distribution as an ordered 5-tuple, with leftmost being oldest, etc., then the three possible solutions are (98,0,1,0,1)(98, 0, 1, 0, 1), (90,0,0,1,1)(90, 0, 0, 1, 1), and (98,0,1,1,0)(98, 0, 1, 1, 0).

To see why, we first mention a few principles. Since the mathematicians are all intelligent, and equally intelligent, but only out for themselves and unable to cooperate or negotiate, each person must assume the worst. No one will approve a plan that gives them zero coins. But furthermore, no one will vote against a plan that gives them a positive number of coins, if it may be possible that they could end up with fewer coins. This is not a game of chance; a person will settle, for example, for just one coin, if by rejecting this offer he or she may end up with no coins.

This explains why the common wrong answer "everyone votes against the oldest in order to decrease the number of players" will not happen with rational players. If the number of players dropped to 4 people, then the first person would have the advantage, and need only propose something that one other person would agree to. For example, the proposal may be (50,0,0,50)(50,0,0,50). This would give players #2, #3 (originally #3, #4) no coins at all, but only 2 votes are needed for the proposal to pass. On the other hand, the proposal could be (50,0,50,0)(50,0,50,0). In other words, when there are 5 people present, it is not in the best interest of #3, #4, or #5 to reject the proposal, if they are offered non-zero amounts of coins, since they may end up with zero later, and have absolutely no control over what happens!

Indeed, by analyzing smaller cases, it becomes clear how much advantage the first person has, and how the second person is in the worst situation. With just two people, (100,0)(100,0) wins all for the first person. With three people, (99,0,1)(99,0,1) will be accepted, since #3 dare not reject it, for then #3 would be the loser in the 2-person situation. Consequently, with 4 people, the winning proposals will be (99,0,1,0)(99,0,1,0) or (99,0,0,1)(99,0,0,1). In both cases, the people with zero will vote against the proposal, and the one person who is offered a single coin will accept, since in no circumstances will they do better than this. (Conceivably, the youngest person can vote against (99,0,0,1)(99,0,0,1), reasoning that the next proposal will be (99,0,1)(99,0,1) which also offers him or her one coin; knowing this, the most likely 4-person proposal will be (99,0,1,0)(99,0,1,0) which will definitely not be rejected by person #3.)

Finally, looking at 5 people, it is now clear that the first person need only "pay off" two others, with the least amount. Person #2 cannot be paid off, since he or she will always be better off being the proposer. Knowing this, person #1 always offers nothing to person #2. Persons #3, #4, #5 all realize that they may end up with no coins at all, by the analysis above. Consequently, if any two of them are offered just a single coin, they will accept, realizing that failing to accept will result in just 4 players, with absolutely no guarantee of any coins at all. In particular, player #3 (in the 5-person situation) realizes that with 4 players, he will surely be offered (and will receive) no coins, so she will gladly accept one coin in the 5-person situation. Persons #4 and #5 (in the 5-person case) are in the situation of not knowing for sure whether they will be offered 1 or 0 coins in the 4-person case. Consequently, if either of them is offered just one coin, the offer is accepted, since a certainty of getting one coin is superior to a possibility of getting no coins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.