Puzzles and Brainteasers, lesson 5
Working backwards
Solve the last move first, then the one before it.
Some puzzles look tangled from the front: five people bargaining over a pot, or a room of people reasoning about each other. Start at the end instead, where only one choice is left, and each step back is easy. Probability used the same method to value a reroll; here it settles votes and what people know.
Part 1. Last move first
Solve a game of offers and votes by starting with the last offer and working back.
Guess first
Five partners, A to E by seniority, split 100 chips. The most senior one left proposes a split and all vote, proposer included. If at least half vote yes, it passes; if not, the proposer leaves with nothing and the next proposes. Each wants the most chips, and votes yes only if offered more than voting no would bring. What does A propose?
Starting with A means guessing what B to E would do if A failed, which depends on what they'd do after that. So start at the other end.
Example 1.1
Five partners, from the end
Find the split each proposer makes, from two partners left up to all five.
- Two left: D and ED 100, E 0
D's own vote is half of two, and a tie passes, so E can't stop it.
- Three left: C, D and EC 99, D 0, E 1
C needs one more vote. E gets nothing if C fails, so 1 chip buys E; D would cost 101.
- Four left: B to EB 99, C 0, D 1, E 0
B needs 2 votes of 4: B's own and one more. D gets 0 if B fails, so 1 chip buys D.
- All fiveA 98, B 0, C 1, D 0, E 1
A needs 3 votes of 5. C and E get 0 under B's split, so each costs 1 chip; B and D cost more.
Answer98, 0, 1, 0, 1, passing by 3 votes to 2.
Each partner compares the offer with what the row below would give them. That row is already solved, so every vote compares two known numbers.
Backward induction
Solve a game from its last decision, where nothing comes after, then use that answer to solve the one before it, and so on back to the start.
Suppose partners who'd get the same either way vote yes. Then votes cost nothing all the way up: C keeps 100 with three left, B with four, and A keeps all 100. Write the rules down before you solve.
Your turn
Now seven partners, A to G, split 100 chips under the same rules. How many chips does A keep?
Part 2. Induction on people
Work out what people can know by solving for one person, then two, then any number.
Keep going with Pro
You've done the first part. Pro opens the rest of this lesson, and every other one.
- Induction on people
Puzzles and Brainteasers overviewSpotted a mistake? Tell us.