1 ----------------------------------------------------------------------------- 9-Number Puzzle ^ [1 2 3] 3 1 2 7 1 2 ? 1 4 7 4 5 6 -> 4 5 6 -> 3 5 6 ---> 2 5 8 7 8 9 7 8 9 4 8 9 3 5 9 v Can "rotate" any row or column. Goal: Form transpose. 2 ----------------------------------------------------------------------------- Temple of Forever o bowl: 15 red beads 12 green beads o When Gong of Time rings, you may remove 3 red, add 2 green (if >= 3 red) OR exchange every bead for opposite color o Exit when 5 red, 5 green 3 ----------------------------------------------------------------------------- [note: use induction on time] Thm: No one leaves the Temple of Forever. Pf: By induction. Let P(n) = "after n steps, don't have 5 red, 5 green" Base case: P(0) is true, have 15 red, 12 green Inductive step: Assume don't have 5 red, 5 green after n steps. 8 red, 3 green -> 5 red, 5 green X 4 ----------------------------------------------------------------------------- To prove a system never enters "bad" state. 1. Find a property that is: - true at start - INVARIANT (preserved by every move) - false in "bad" state 2. Use induction on TIME 5 ----------------------------------------------------------------------------- * Monk has at least one bead. true at start, invariant, true in "bad" state [cross out] * red > green True at start, false in "bad" state, not invariant. * red - green = 5k + 2 or 5k + 3 True at start, false in "bad" state, invariant. 6 ----------------------------------------------------------------------------- Some states (red, green) (15, 12) -> (12, 15) -> (9, 17) -> (17, 9) | v (12, 14) -> (14, 12) -> (11, 14) -> (14, 11) -> (11, 13) etc. 7 ----------------------------------------------------------------------------- Proof. We use induction on # gongs. P(n) = "After n rings, red - green = 5k + 2 or 5k + 3 for some k in Z." Base case: P(0) true because 15 - 12 = 5.0 + 3 8 ----------------------------------------------------------------------------- Inductive step: Assume P(n): red - green = 5k + 2 or 5k + 3. 1. Remove 3 red, add 2 green: new red - new green = (red - 3) - (green + 2) = (red - green) - 5 = 5(k-1) + 2 or 5(k-1) + 3 => P(n+1) 9 ----------------------------------------------------------------------------- 2. Swap red and green: new red - new green = green - red = -(5k+2) or -(5k+3) = -5k-5+3 or -5k-5+2 = -5(k+1)+3 or -5(k+1)+2 By induction red - green = 5k+2 or 5k+3 always. So red = green = 5 is unreachable. [] 10 ---------------------------------------------------------------------------- 9-Number Puzzle PERMUTATION of 1 to 9 is sequence containing every digit exactly once: 1 2 3 4 5 6 -> 1 2 3 4 5 6 7 8 9 ZERO 7 8 9 inversions INVERSION is a pair of digits in reverse order 11 ---------------------------------------------------------------------------- Inversions 3 1 2 4 5 6 -> 3 1 2 4 5 6 7 8 9 3-1, 3-2 TWO 7 8 9 7 1 2 3 5 6 -> 7 1 2 3 5 6 4 8 9 7-1 7-2 7-3 7-5 EIGHT 4 8 9 7-6 7-4 5-4 6-4 12 ---------------------------------------------------------------------------- 1 4 7 2 5 8 -> 1 4 7 2 5 8 3 6 9 4-2 4-3 7-2 NINE 3 6 9 7-5 7-3 7-6 5-3 8-3 8-6 13 ---------------------------------------------------------------------------- Lemma 1: Swapping any two digits changes the PARITY of # inversions. Pf. Take an arbitrary permutation: ---- x b1 ... bk y ---- (---- = other digits) Swapping x and y gives: ---- y b1 ... bk x ---- 2k + 1 pairs reversed: x-y, all x-b_i, all b_i-y Changes parity 2k + 1 times, effectively once. [] 14 ---------------------------------------------------------------------------- Lemma 2: Rotating any three digits preserves parity of # inversions. Pf. The arbitrary permutation: ---- x ---- y ---- z ---- Forward rotation = swap y-z, x-z ---- z ---- x ---- y ---- /---> 2 swaps change parity twice | => parity preserved Backward rotation = swap x-y, x-z | | ---- y ---- z ---- x ---- -----/ 15 ---------------------------------------------------------------------------- Thm: The 9-Number Puzzle is unsolvable. Pf: By induction. Let P(n) = "after n moves, # of inversions is even" Base case: P(0) is true; initially zero inversions 16 ---------------------------------------------------------------------------- Ind. Step: Assume even # inversions after n steps. By Lemma 2, rotating three digits preserves parity. So even # inversions after n+1 steps also. By induction, # inversions is ALWAYS even. So the transpose (9 inversions) is unreachable. 17 ---------------------------------------------------------------------------- Error #1 Thm. For all n >= 0 1^2 + 2^2 + ... + n^2 = n (n + 1/2)(n + 1) / 3 Pf. We use induction. Let P(n) = "For all n >= 0, 1^2 + 2^2 + ... + n^2 = n (n + 1/2)(n + 1) / 3". Base case... No "For all n" in P(n)! [box this, cross out error] 18 ---------------------------------------------------------------------------- Error #2 Pf. We use induction. Let P(n) = "1^2 + 2^2 + ... + n^2 = n (n + 1/2)(n + 1) / 3" Base case: P(0) = 0 (0 + 1/2) (0 + 1) / 3 = 0 Ind step: P(n) + (n+1)^2 = n(n+1/2)(n+1) ------------- + (n+1)^2 3 = (n+1)(2(n+1)+1)(n+2) -------------------- = P(n+1) 6 P(n) is a statement, not a numerical function 19 ---------------------------------------------------------------------------- Error #3 [comes up in strong induction proofs] Fibonacci numbers: F_0 = 0 F_1 = 1 F_n = F_(n-1) + F_(n-2) for n >= 2 0, 1, 1, 2, 3, 5, 8, ... \+-|-/ Claim: All Fibonacci numbers are even. [Going to be more obvious here; usually screw up when proving something true.] 20 ---------------------------------------------------------------------------- Pf. We use strong induction. Let P(n) = "F_n is even". Base case: F_0 is even, so P(0) is true. Ind step: Assume P(0), ... P(n-1) to prove P(n). Only for n >= 2 F_n = F_{n-1} + F_{n-2} = even + even = even So P(n) is true. 21 ---------------------------------------------------------------------------- Strong induction axiom [x] P(0) [ ] P(0) => P(1) => P(n) for all n >= 0 [x] P(0) and P(1) => P(2) [x] P(0), P(1), and P(2) => P(3) etc. [Cross out the implies on the right. Note that change F_1 = 2, then second line would be correct; then theorem woudl be true!] 22 ---------------------------------------------------------------------------- Error #4 Def: An AUTOCITY is a city with a road to another city. Boston------Albany o Barrow \ / \ / New York-----Philadelphia 23 ---------------------------------------------------------------------------- Thm: You can drive between any two autocities. Pf. By induction. Let P(n) = "You can drive between any two autocities in a world with n autocities." Base case: P(2) is true: o---------o 24 ---------------------------------------------------------------------------- Ind step: We show P(n) -> P(n+1) for all n >= 2 (n+1)st autocity o n autocities (connected up by P(n) By induction, P(n) is true for all n. 25 ---------------------------------------------------------------------------- o o | | | | o o Buildup error: not every object of size n+1 is an object of size n plus 1 more. Take an object of size n+1. Remove 1. Reason about remainder. Add the 1 back.