---
title: "Brainteasers and Logic"
book: "The Interview Book"
subject: quant
language: en
chapter: 12
exercises: 0
source: https://one-course.com/books/quant/18/en/chapter/12-brainteasers-and-logic
---

# Chapter 12 — Brainteasers and Logic

A candidate is asked how a hundred people standing in a line, each seeing the hats of everyone in front, can agree on a rule so that all but one name the colour of their own hat. He says “this is the parity puzzle” and recites the rule for two colours. The interviewer changes it to three colours and waits. The puzzle was never the point: the family was, and the idea behind the family, and a candidate who knows only the answer to the famous version has nothing to say when the version changes. This chapter organises brainteasers into families, gives the idea behind each, and then asks only variants.

## 12.1 Invariants and parity

**Definition 12.1 (Invariant method).**

The *invariant method* solves a puzzle about a process by finding a quantity that no allowed move changes (a parity, a sum modulo $m$, a product, a colouring count); every reachable state shares the starting value, so a state with another value is unreachable, and the final state is determined.

**Method 12.2 (Finding an invariant).**

1. Play a few moves by hand and write the state after each.
2. Try, in order: the parity of each count, the sum modulo small numbers, the sum or product of a function of the entries ( $\prod(1 + x_i)$ for merges of the form $a + b + ab$ ), a colouring of a board.
3. Prove that each move preserves it; then read the answer from the initial value.

**Example 12.3 (The hat line).**

With $k$ colours numbered $0, \dots, k-1$, the last person in the line (who sees everyone else) announces the sum of the colours in front modulo $k$. Each following person knows that sum, hears every answer given after the first, sees everyone in front, and so can subtract to find their own colour. All but the first are right, whatever $k$: the invariant is the announced sum.

## 12.2 Working backwards

**Definition 12.4 (Backward induction).**

*Backward induction* solves a finite sequential game or decision problem by determining the best action at the last stage, then at the one before given the best continuation, and so on to the first stage.

In a take-away game (players alternately remove tokens, the one who takes the last wins), a position is losing for the player to move if every move leads to a winning position for the other, and winning if some move leads to a losing one. Computing this from zero upwards gives the pattern ([Figure 12.1](#fig-iv-brainteasers-and-logic-game)): with moves of 1 or 2 the losing positions are the multiples of 3; with moves of 1 to $m$, the multiples of $m+1$; with irregular move sets the pattern is eventually periodic but has to be computed.

![The take-away game with moves of one or two tokens, last to take wins, solved by backward induction from 0. Arrows are moves (straight: take one; curved: take two). Positions 0, 3 and 6 are losing for the player to move. Exhaustive search in iv_teasers.py.](https://one-course.com/images/onecourse/chapters/quant-18/iv-brainteasers-and-logic/fig-cd0765127c56.svg)

***Figure 12.1.** The take-away game with moves of one or two tokens, last to take wins, solved by [backward induction](#def-iv-brainteasers-and-logic-backward) from 0. Arrows are moves (straight: take one; curved: take two). Positions 0, 3 and 6 are losing for the player to move. Exhaustive search in `iv_teasers.py`.*

Division games (a senior proposer, a vote, a proposer who leaves if rejected) are solved the same way: find the outcome with one player, then with two, and at each size give the minimum needed to the voters who would do worst if the proposal failed. The classic version is Stewart’s pirate puzzle (1999); the bank’s variant has different voting rules and a different answer.

## 12.3 Strategy stealing, pigeonholes and extremal arguments

**Definition 12.5 (Strategy-stealing argument).**

A *strategy-stealing argument* proves that the first player in a finite game with no draws has a winning strategy, without finding it: if the second player had one, the first player could make an arbitrary move and then follow that strategy as if second, and an extra move never hurts, which is a contradiction.

The argument proves existence, not construction: Gale’s chocolate-bar game (1974), in which players remove a rectangle from the corner of a bar and the player forced to take the poisoned square loses, is a first-player win on every rectangle larger than one square, and nobody knows a general winning move. Gale’s proof that Hex cannot end in a draw (1979) is the other famous use.

Pigeonhole arguments show that something must coincide because there are more objects than boxes; extremal arguments look at the largest or smallest element and show it has the property asked for. Both reward naming the boxes or the extreme element explicitly.

**Example 12.6 (A block of trades summing to a multiple of ten).**

Among any ten integer P&Ls in sequence, some block of consecutive ones sums to a multiple of ten. The eleven prefix sums (including the empty one) fall into ten residues modulo ten, so two coincide, and the block between them sums to a multiple of ten.

## 12.4 Information puzzles

Weighing and questioning puzzles are about counting outcomes: $k$ weighings on a balance have $3^k$ outcomes and can distinguish at most $3^k$ cases, and a design that splits the cases as evenly as possible at each step reaches the bound or nearly. Common-knowledge puzzles are about what each person knows about what the others know: an announcement that everyone already knew can still change behaviour, because after it everyone knows that everyone knows it (Fagin, Halpern, Moses and Vardi, 1995).

**Method 12.7 (Information puzzles).**

1. Count the cases to distinguish and the outcomes each test has; the logarithm is a lower bound on the number of tests.
2. Design each test to split the remaining cases as evenly as the outcomes allow.
3. For knowledge puzzles, start from the smallest case (one person, one round) and induct: “if there were only one, she would know at once; nobody spoke, so there are at least two”.

The simultaneous hat game, in which players guess or pass at the same time and win if at least one guesses and nobody is wrong, was popularised by Ebert’s thesis (1998); its solution for seven players uses a Hamming code.

## 12.5 Worked answers

**Example 12.8 (Pigeonholes, and the fewest that force it).**

*“Thirteen trades print within one hour, from 10:00 to 11:00 inclusive. Prove that two of them are at most five minutes apart. Is thirteen the fewest that forces it?”* Cut the hour into twelve closed intervals of five minutes; with thirteen trades, two share an interval and are at most five minutes apart. For the second part, an extremal construction: twelve trades at 10:00, 10:05 and a hair, 10:10 and two hairs, and so on, span $11 \times (5 + \epsilon)$ minutes, which fits in the hour for small $\epsilon$, with every gap above five minutes. So twelve do not force it and thirteen is the fewest. The two halves (the argument and the construction showing it is tight) are both expected; the second is what separates a proof from a recitation.

**Example 12.9 (A parity invariant).**

*“The numbers 1 to 20 are on a board. Repeatedly erase two numbers and write the absolute value of their difference. Can the last number be 1? Can it be 0?”* Look for what an operation cannot change. Since $|a - b| \equiv a +
b \pmod 2$, the parity of the sum of the board never changes; it starts at $210$, even, so the last number is even and cannot be 1. Zero is reachable: pair the numbers as $(1,2), (3,4), \dots, (19,20)$ to get ten 1s, then pair the 1s to get five 0s, and every further difference of zeros is zero. The invariant rules outcomes out; an explicit sequence rules one in, and the answer needs both.

## 12.6 Question bank

**Interview question 12.1 ★ trader • market maker.**

A bag holds 20 red and 13 blue tokens. Repeatedly take two out: if they have the same colour put back one red, if they differ put back one blue. What colour is the last token?

**Solution of Interview question 12.1.**

Blue. Each move changes the number of blue tokens by 0 (two reds out, a red back; two blues out, a red back: $-2$) or leaves it (one of each out, a blue back): the parity of the blue count never changes. It starts odd (13), so the last token, when the bag holds one, is blue. With 12 blues it would be red.

*What the interviewer is looking for: the parity invariant, found by writing out the three moves.*

**Interview question 12.2 ★ trader, developer • proprietary firm.**

Thirty tokens; players alternately take one to four; whoever takes the last wins. Do you want to go first? With 31 tokens, what is your first move?

**Solution of Interview question 12.2.**

The losing positions for the player to move are the multiples of 5: from a multiple of 5 every move leaves a non-multiple, and from a non-multiple a move to a multiple exists. With 30 tokens, go second. With 31, take one and then always answer the opponent’s $k$ with $5 - k$.

*What the interviewer is looking for: [backward induction](#def-iv-brainteasers-and-logic-backward) to a periodic pattern and the pairing strategy.*

**Interview question 12.3 ★ trader, researcher • any.**

A firm employs 400 people. Prove that two of them have the same birthday.

**Solution of Interview question 12.3.**

There are 366 possible birthdays (29 February included) and 400 people; by the pigeonhole principle two share one. The argument needs no assumption about how birthdays are distributed.

*What the interviewer is looking for: naming the boxes and counting.*

**Interview question 12.4 ★ researcher, developer • any.**

In a group of traders, some pairs have traded with each other. Prove that the number of traders who have traded with an odd number of the others is even.

**Solution of Interview question 12.4.**

Summing each trader’s number of counterparties counts every pair twice, so the sum is even. A sum of integers is even only if the number of odd terms is even. (A check on random graphs in the chapter’s code agrees.)

*What the interviewer is looking for: double counting and a parity argument.*

**Interview question 12.5 ★ trader • market maker.**

You have a 3-minute and a 5-minute sand timer. Measure exactly 7 minutes.

**Solution of Interview question 12.5.**

Start both at 0. At 3 minutes the small timer runs out: turn it over. At 5 minutes the large one runs out; the small one has run for 2 minutes since it was turned, so turn it over again: its 2 minutes of sand run back, ending at 7 minutes.

*What the interviewer is looking for: tracking the sand in both halves, not only the elapsed time.*

**Interview question 12.6 ★★ trader, developer • proprietary firm.**

A hundred people stand in a line, each seeing the hats of all those in front; hats come in three colours. Guessing from the back, each says one colour aloud. Give a rule agreed in advance that guarantees at least 99 correct answers, and explain why it works.

**Solution of Interview question 12.6.**

Number the colours 0, 1, 2. The last person announces the sum of the hats in front modulo 3 (a colour, so a legal answer). Each following person knows that sum, subtracts the colours announced by those behind them after the first (which are correct) and the colours they see in front, and obtains their own colour modulo 3. Everyone but the last is right: at least 99. The same rule works for any number of colours, which is the family’s idea: one announcement can carry one number modulo $k$.

*What the interviewer is looking for: the sum-modulo-$k$ invariant, and the generalisation.*

**Interview question 12.7 ★★ trader, researcher • market maker.**

Ten bags of coins; in one bag every coin weighs 0.9 gram instead of 1 gram. With a single reading of a digital scale, find the bag.

**Solution of Interview question 12.7.**

Take $i$ coins from bag $i$, 55 coins in all, and weigh them. If every coin were genuine the scale would read 55 grams; the reading is short by $0.1\,i$ grams when bag $i$ is light, so the shortfall divided by 0.1 is the bag’s number. The design gives each hypothesis a distinct, readable outcome.

*What the interviewer is looking for: encoding the hypothesis in the quantity taken.*

**Interview question 12.8 ★★ trader, researcher • any.**

Four partners, ranked by seniority, divide 100 coins. The most senior remaining partner proposes a division; it passes if at least half of the remaining partners (the proposer included) vote for it; if it fails, the proposer leaves with nothing and the next proposes. Each partner votes for a proposal only if it gives strictly more than they would get after a rejection. What does the most senior partner propose?

**Solution of Interview question 12.8.**

One partner keeps everything. With two, the senior’s vote is half, so it passes: $(100, 0)$. With three, the proposal needs one vote besides the proposer’s: the partner who would get nothing in the two-partner case (the most junior) is bought with 1: $(99, 0, 1)$. With four, two votes of four pass, so again one vote is needed besides the proposer’s. If the proposal failed, the other three would split $(99, 0, 1)$: the second partner would get 99, the third 0 and the fourth 1. The cheapest vote is the third partner’s, bought with 1: the proposal is $(99, 0, 1, 0)$. An exhaustive [backward induction](#def-iv-brainteasers-and-logic-backward) in the chapter’s code gives the same, and $(98, 0, 1, 0, 1)$ for five.

*What the interviewer is looking for: [backward induction](#def-iv-brainteasers-and-logic-backward) from the smallest case and buying the cheapest votes.*

**Interview question 12.9 ★★ researcher, developer • any.**

Two players alternately bite a rectangular corner off a four-by-five chocolate bar (choosing a square and removing it together with every square below and to its right); whoever must take the top-left square loses. Prove that the first player can win without finding the winning move.

**Solution of Interview question 12.9.**

The game is finite and cannot end in a draw, so one player has a winning strategy. Suppose it is the second. Let the first player bite only the bottom-right square. Whatever the second player answers is a position the first player could have produced in one bite from the full bar, because any bite also removes the bottom-right square. So the first player could have made that bite first and then used the second player’s winning strategy: a contradiction. The first player wins; an exhaustive search on the four-by-five bar confirms it, and finds a move, but the argument never needs one.

*What the interviewer is looking for: the [strategy-stealing argument](#def-iv-brainteasers-and-logic-stealing), including why the stolen position is reachable.*

**Interview question 12.10 ★★ trader, researcher • proprietary firm.**

Five traders wear red or blue badges; each sees the others’ badges but not their own; three badges are red. A supervisor says: “At least one of you wears red. Whoever knows their colour, step forward.” She repeats the instruction at each round. Who steps forward, and at which round? What did the supervisor’s sentence add, since everyone could already see a red badge?

**Solution of Interview question 12.10.**

The three red-badged traders step forward together at the third round. If there were one red badge, its wearer would see none and know at once. If there were two, each would see one; when nobody steps forward at round one, each learns that the other saw a red badge, which must be their own, so both step forward at round two. With three, each red wearer sees two and waits; when nobody steps forward at round two, each concludes that there are three. The sentence added common knowledge: before it, everyone knew there was a red badge, but not that everyone knew that everyone knew it, which is what the induction needs. A model-checking search over all consistent worlds gives round 3 and the three red wearers.

*What the interviewer is looking for: induction on the number of red badges and the idea of common knowledge.*

**Interview question 12.11 ★★★ researcher, developer • systematic fund.**

Three players each get a red or blue hat with probability one half. Each sees the other two hats, then all simultaneously guess their own colour or pass. The team wins if at least one guesses and nobody guesses wrong. Find a strategy that wins three times in four and prove that no strategy does better.

**Solution of Interview question 12.11.**

Rule: if the two hats you see have the same colour, guess the other colour; otherwise pass. The team loses only when all three hats match (two of the eight configurations), where everyone guesses wrong; in the other six exactly one player sees two equal hats and guesses right: $\tfrac34$. No strategy does better: for each player and each view, a guess is right in one of the two configurations sharing that view and wrong in the other, so the total number of right guesses equals the total of wrong ones. A win needs at least one right guess and a loss can absorb up to three wrong ones, so wins are at most three times losses: at most $\tfrac34$. With seven players a Hamming code wins $\tfrac78$ of the time; both are checked exhaustively in the chapter’s code.

*What the interviewer is looking for: concentrating the wrong guesses on few configurations, and the counting bound.*

**Interview question 12.12 ★★★ trader, researcher • any.**

The numbers 1 to 10 are written on a board. Repeatedly erase two numbers $a$ and $b$ and write $a + b + ab$. What number is left at the end, and why does the order not matter?

**Solution of Interview question 12.12.**

$1 + (a + b + ab) = (1 + a)(1 + b)$, so the product $\prod(1 + x)$ over the board is invariant. It starts at $2 \times 3 \times \dots \times 11 = 11!$, so the last number is $11! - 1 = 39\,916\,799$, whatever the order.

*What the interviewer is looking for: spotting the factorisation that turns the move into a product.*

**Interview question 12.13 ★★★ trader, developer • market maker.**

Twenty tokens; players alternately take one, three or four; whoever takes the last wins. Who wins, and what is the first move? Describe the losing positions.

**Solution of Interview question 12.13.**

Computing losing positions upwards with moves $\{1, 3, 4\}$ gives 0, 2, 7, 9, 14, 16, 21, 23, …: the positions congruent to 0 or 2 modulo 7. Twenty is winning: take 4, leaving 16. The pattern is periodic, but its period (7) is not $1 +$ the largest move, which is why it must be computed rather than guessed.

*What the interviewer is looking for: a clean backward-induction table and suspicion of patterns guessed from the classic game.*

**Interview question 12.14 ★★★ researcher • systematic fund.**

Prove that among any ten integer daily P&L figures, listed in order, some run of consecutive days has a total that is a multiple of ten. Is ten days the fewest that guarantees it?

**Solution of Interview question 12.14.**

The prefix sums $P_0 = 0, P_1, \dots, P_{10}$ are eleven numbers in ten residue classes modulo 10, so two are congruent, and the days strictly between them sum to a multiple of 10. Ten is the fewest: nine days of P&L equal to 1 have runs summing to 1 to 9 only. A check on 500 random sequences of ten confirms the statement.

*What the interviewer is looking for: the pigeonhole on prefix sums and a tightness example.*

Sources and further reading

- I. Stewart, “A puzzle for pirates”, *Scientific American* 280(5), 1999, 98–99.
- D. Gale, “A curious Nim-type game”, *American Mathematical Monthly* 81(8), 1974, 876–879.
- D. Gale, “The game of Hex and the Brouwer fixed-point theorem”, *American Mathematical Monthly* 86(10), 1979, 818–827.
- R. Fagin, J. Y. Halpern, Y. Moses and M. Y. Vardi, *Reasoning about Knowledge* , MIT Press, 1995.
- T. Ebert, doctoral thesis, University of California, Santa Barbara, 1998 (the simultaneous hat game), as reported in P. Winkler, *Mathematical Puzzles: A Connoisseur’s Collection* , A K Peters, 2004.