insideout Get Pro

05 · Working backwards

Pro

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?

A keeps 98 and gives 1 chip each to C and E. The example shows why those two.

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

ABCDE5 left9801014 left990103 left99012 left1000Solve the bottom row first. Boxed: the proposer's share.
Figure 1Each row is solved from the row below it. The orange chips buy the votes of the partners who would get nothing one row down.

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?

With six partners the split is 98, 0, 1, 0, 1, 0, so if A fails, C, E and G get 0. A needs 4 votes of 7, A's own and 3 more, at 1 chip each: A keeps 97. The answer 98 copies the five-partner split without solving the row below.

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.

Still to come
  1. Induction on people

Puzzles and Brainteasers overviewSpotted a mistake? Tell us.