Unit 2 of 4
Puzzles That Make You Think
- 24 chapters
- Video 2, chapters 1 to 24
This video solves classic puzzles about boards, crossings, weighings, hats, games and bridges, each with one idea such as an invariant, a recursion, a binary code or a graph.
Colorings and parity show why the mutilated chessboard and the swapped fifteen puzzle are impossible, while a recursive tiling covers any power-of-two board with one square missing. River crossings, the bridge and torch, water jugs, the Tower of Hanoi and the two-egg problem turn legal moves into plans. Weighings, pooled tests, hats and a single coin flip carry information, and prisoners, islanders and knights and knaves reason together. Nim, Chomp and a take-away game have winning strategies, and the bridges of Königsberg, the Icosian tour and the party handshake puzzle become graphs.
Every chapter will be part of one of 4 long videos. The videos are coming soon, and each chapter page already has the definitions and an example for every key term.
See what cannot change
The Mutilated Chessboard
Why the mutilated chessboard problem has no domino tiling, shown by a coloring argument that makes a color count an invariant, and why equal color counts alone do not guarantee a tiling.
Video 2, chapter 1
The Missing-Square Tromino Tiling
Why a board whose side is a power of 2, with any one square missing, can always be tiled by L-trominoes, proved by mathematical induction from a 2 by 2 base case with a divide and conquer step.
Video 2, chapter 2
The Impossible Fifteen Puzzle
Why exchanging tiles 14 and 15 gives an unsolvable position of the 15 puzzle, a sliding puzzle, shown by an invariant that adds the number of inversions, which sets the permutation parity, to the row of the blank.
Video 2, chapter 3
Frogs and Toads
How the frogs and toads puzzle is solved, how a counting argument of jumps and slides gives a lower bound, and why a legal route then proves that the minimum number of moves for three of each is 15.
Video 2, chapter 4
Plan the moves
The River-Crossing Shuttle
How a river crossing puzzle with two adults, two children and a small boat is solved in nine crossings, using states, the state space, legal states and a repeatable shuttle strategy, and why no plan is shorter.
Video 2, chapter 5
The Bridge and Torch
How the bridge and torch problem with walkers taking 1, 2, 5 and 10 minutes is solved in 17 minutes, why a greedy strategy takes 19, and how a case argument and an exhaustive search prove the schedule optimal.
Video 2, chapter 6
The Water-Jug Puzzle
How unmarked 5-liter and 3-liter jugs measure exactly 4 liters in the water pouring puzzle, why only full and empty jugs give exact measurement, and how the greatest common divisor decides which amounts are possible.
Video 2, chapter 7
The Tower of Hanoi
How recursion solves the Tower of Hanoi, why the fewest moves for n disks on three pegs obey a recurrence relation that doubles and adds one, and why that count shows exponential growth.
Video 2, chapter 8
Two Eggs and One Hundred Floors
How the egg drop problem with two eggs and 100 floors is solved in at most 14 drops, why binary search fails with only two eggs, and how worst-case analysis and triangular numbers prove that 14 is the fewest.
Video 2, chapter 9
Extract information
The Counterfeit Coin
How the counterfeit coin problem finds one heavier coin among nine with two uses of a balance scale, and how a decision tree and ternary search show that no strategy can do it in fewer.
Video 2, chapter 10
The Broken Stick Puzzle
How the broken stick problem gives a triangle with probability one quarter, using the triangle inequality, two cut points with a uniform distribution and probability as area in the unit square.
Video 2, chapter 11
One Thousand Samples, Ten Tests
How group testing with pooled samples can find one special sample among 1,000 with ten yes-or-no tests, by binary encoding each sample's number, and why ten bits are the fewest that can do it.
Video 2, chapter 12
The Hat-Parity Puzzle
How the prisoners and hats puzzle lets 99 of 100 people in a line name their own hat color, with the parity of the red hats ahead sent as a parity bit, and why no plan can promise all 100.
Video 2, chapter 13
The One-Coin Chessboard Message
How the chessboard coin puzzle names any of 64 squares with one coin flip, by giving the squares binary labels and reading the board as the XOR of its heads, six parity checks at once.
Video 2, chapter 14
Reason together
The Prisoners and the Light Switch
How the light switch puzzle is solved by a counting protocol with one counter, why this distributed algorithm never declares too early, and why finishing needs a fairness assumption on the visits.
Video 2, chapter 15
The 100 Prisoners Puzzle
How the 100 prisoners problem is solved by the cycle-following strategy, which wins exactly when the random permutation in the boxes has no cycle longer than 50, about 31.18 percent of the time.
Video 2, chapter 16
The Blue-Eyed Islanders
How the blue-eyed islanders puzzle is solved night by night by induction, and why a public announcement of something everyone can see creates common knowledge, the central idea of epistemic logic.
Video 2, chapter 17
Knights and Knaves
How the knights and knaves puzzle about a queue of truth-tellers and liars is solved by case analysis, and how checking logical consistency shows that 25 people include exactly 12 knights.
Video 2, chapter 18
Find the winning move
The Take-Away Game
How the take-away game, a subtraction game with moves of one to three counters, is solved by backward induction, why its losing positions under normal play are the multiples of four, and how misère play changes them.
Video 2, chapter 19
Nim
How Nim, a combinatorial game played with several piles of counters, is solved by Bouton's theorem, which writes the pile sizes as binary numbers and says the player to move loses exactly when their nim-sum is zero.
Video 2, chapter 20
Chomp
How Chomp, a game on a chocolate bar with a poisoned corner, is shown to be a first-player win on every rectangle of more than one square by a strategy-stealing argument, a nonconstructive proof that names no winning move.
Video 2, chapter 21
Turn a route into a graph
The Seven Bridges of Königsberg
Why no walk crosses each of the seven bridges of Königsberg exactly once, shown by counting vertex degrees, and Euler's theorem on when a graph has an Eulerian path or an Eulerian circuit.
Video 2, chapter 22
The Icosian Tour and Hamiltonian Cycles
How the Icosian game asks for a Hamiltonian cycle of the dodecahedral graph, a route that visits every vertex once before returning, how to build one, and why Euler's count of odd vertices does not decide it.
Video 2, chapter 23
The Party Handshake Puzzle
Why at every party of two or more people two guests know the same number of others, proved with the pigeonhole principle and the degree sequence of a simple graph, and which assumptions the proof needs.
Video 2, chapter 24