6.042/18.] Mathematics for Computer Science February 15, 2005 Srini devadas and Eric Lehman Lecture notes Induction ill 1 Two Puzzles Here are two challenging puzzles 1.1 The 9-Number puzzle The numbers 1, 2,..., 9 are arranged in a 3 x 3 grid as shown below: 123 4|51|6 78|9 You can rearrange the numbers by rotating rows and columns. For example, rotating the first row to the right gives 231 4|56→[4|56 7S|9 Notice that 1 and 2 both moved right one position and the rightmost number, 3, jumped back to the left. Similarly, if we now rotate the first column downward, then 3 and 4 both move down one position and the bottom number, 7, jumps back up to the top 35|6 489 Can you find a sequence of moves that transposes the original configuration? 2|58 369
6.042/18.062J Mathematics for Computer Science February 15, 2005 Srini Devadas and Eric Lehman Lecture Notes Induction III 1 Two Puzzles Here are two challenging puzzles. 1.1 The 9Number Puzzle The numbers 1, 2, . . . , 9 are arranged in a 3 × 3 grid as shown below: 1 2 3 4 5 6 7 8 9 You can rearrange the numbers by rotating rows and columns. For example, rotating the first row to the right gives: 1 2 3 4 5 6 7 8 9 −→ 3 1 2 4 5 6 7 8 9 Notice that 1 and 2 both moved right one position and the rightmost number, 3, jumped back to the left. Similarly, if we now rotate the first column downward, then 3 and 4 both move down one position and the bottom number, 7, jumps back up to the top: 3 1 2 4 5 6 7 8 9 −→ 7 1 2 3 5 6 4 8 9 Can you find a sequence of moves that transposes the original configuration? −→ . . . ? . . . −→ 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9
2 Induction ill 1. 2 The Temple of Forever Each monk entering the Temple of Forever is given a bowl with 15 red beads and 12 green beads. Each time the Gong of Time rings, the monk must do one of two thing 1. If he has at least 3 red beads in his bowl, then he may remove 3 red beads and add 2 green beads 2. He may replace every bead in his bowl with a bead of the opposite color For example, at the first ring of the Gong of Time, the monk might replace every bead with one of the opposite color, giving him 12 red and 15 green. Then, at the second ring, he might remove 3 red and add 2 green, leaving 9 red and 17 green. A monk may leave the Temple of Forever only when he has exactly 5 red beads and 5 green beads in his bowl. Can you find a way to escape? 2 Using Induction to Analyze a Process An important application of induction is proving that a system never enters some unde- sirable state. For example, we might want to prove that a file system is never corrupted, records in a data structure are always rapidly retrievable, or a communication protocol never deadlocks. No new mathematical techniques are required to use induction for such purposes. But you'll need to think about induction somewhat differently. We'll use the umbe uzzle and the Temple of Forever as illustrations 2.1 Induction on time Some frustrating experiments suggest that there is no way to escape from the Temple of Forever or solve the 9-Number Puzzle But how could we hope to prove these conclusions using induction? Remember that induction establishes that some predicate P(n)is true for all n E N. For the Temple problem, should we use induction on the number of red beads? Green beads? The total? Worse the -Number puzzle doesn 't seem to involve a natural-valued variable at all! The common solution when analyzing a system is to use induction on time; that is 7e'll use induction to prove that some predicate P() is true for every n20 where n is the number of rotations, gong rings, moves, hours, steps, or whatever. Unfortunately, a naive approach still doesn't work. Let's try such an argument and see where we get stuck Theorem. No one leaves the temple of forever
2 Induction III 1.2 The Temple of Forever Each monk entering the Temple of Forever is given a bowl with 15 red beads and 12 green beads. Each time the Gong of Time rings, the monk must do one of two things: 1. If he has at least 3 red beads in his bowl, then he may remove 3 red beads and add 2 green beads. 2. He may replace every bead in his bowl with a bead of the opposite color. For example, at the first ring of the Gong of Time, the monk might replace every bead with one of the opposite color, giving him 12 red and 15 green. Then, at the second ring, he might remove 3 red and add 2 green, leaving 9 red and 17 green. A monk may leave the Temple of Forever only when he has exactly 5 red beads and 5 green beads in his bowl. Can you find a way to escape? 2 Using Induction to Analyze a Process An important application of induction is proving that a system never enters some undesirable state. For example, we might want to prove that a file system is never corrupted, records in a data structure are always rapidly retrievable, or a communication protocol never deadlocks. No new mathematical techniques are required to use induction for such purposes. But you’ll need to think about induction somewhat differently. We’ll use the 9Number Puzzle and the Temple of Forever as illustrations. 2.1 Induction on Time Some frustrating experiments suggest that there is no way to escape from the Temple of Forever or solve the 9Number Puzzle. But how could we hope to prove these conclusions using induction? Remember that induction establishes that some predicate P(n) is true for all n ∈ N. For the Temple problem, should we use induction on the number of red beads? Green beads? The total? Worse, the 9Number Puzzle doesn’t seem to involve a naturalvalued variable at all! The common solution when analyzing a system is to use induction on time; that is, we’ll use induction to prove that some predicate P(n) is true for every n ≥ 0 where n is the number of rotations, gong rings, moves, hours, steps, or whatever. Unfortunately, a naive approach still doesn’t work. Let’s try such an argument and see where we get stuck. Theorem. No one leaves the Temple of Forever
Induction Ill Proof. We use induction. Let P(n) be the proposition, "After n gong rings, the number of red beads in the monk's bowl is not equal to the number of green beads Base case. Initially, there are 15 red beads and 12 green beads, so P(O)is true Inductive step. We must show that P(n)implies P(n+1) for all n 20. So assume that after n gong rings the number of red beads in the monks bowl is not equal to the number of green beads. Then after n+ l gong rings Ne re stuck! If we assume that P(n)is true, the monk might have, say,onen leaves him red beads and 3 green beads after n gong rings. But then removing 3 red and adding 2 grec with 5 red and 5 green, making P(n+ 1)false! In other words, we can't hope to prove P(n)implies P(n+1)in the inductive step--not because we aren' t sufficiently clever, but because it's just not true o we must be clever-er 2.2 Finding an Induction Hypothesis The key to proving that a system can never reach a"bad"state is chosing the right induc tion hypothesis. In particular, the induction hypothesis should describe a property that 1. True at the start 2. Invariant, meaning that if the system has the property before a move then it must also have the property after the move 3. False in the"bad"state Intuitively, were looking for a property that the system has initially and can never lose This means any state of the system lacking that property is unreachable Let's check a couple properties against these criteria The monk always has at least one bead. This is true initially since the monk starts with a bowlful of beads. Furthermore, this property is invariant. Suppose thethe monk has at least one bead If the monk removes 3 red beads and adds 2 green, then he is left with at least the 2 green.(Remember this operation is only allowed if the monk has at least 3 red. If the monk has at least one bead before swapping colors then he has at least one bead after doing so; in fact, chaning colors does not affect the number of beads at all
Induction III 3 Proof. We use induction. Let P(n) be the proposition, “After n gong rings, the number of red beads in the monk’s bowl is not equal to the number of green beads.” Base case. Initially, there are 15 red beads and 12 green beads, so P(0) is true. Inductive step. We must show that P(n) implies P(n+ 1) for all n ≥ 0. So assume that after n gong rings the number of red beads in the monk’s bowl is not equal to the number of green beads. Then after n + 1 gong rings... × We’re stuck! If we assume that P(n) is true, the monk might have, say, 8 red beads and 3 green beads after n gong rings. But then removing 3 red and adding 2 green leaves him with 5 red and 5 green, making P(n + 1) false! In other words, we can’t hope to prove P(n) implies P(n+1) in the inductive step— not because we aren’t sufficiently clever, but because it’s just not true! So we must be cleverer. 2.2 Finding an Induction Hypothesis The key to proving that a system can never reach a “bad” state is chosing the right induction hypothesis. In particular, the induction hypothesis should describe a property that is: 1. True at the start. 2. Invariant, meaning that if the system has the property before a move, then it must also have the property after the move. 3. False in the “bad” state. Intuitively, we’re looking for a property that the system has initially and can never lose. This means any state of the system lacking that property is unreachable. Let’s check a couple properties against these criteria. The monk always has at least one bead. This is true initially since the monk starts with a bowlful of beads. Furthermore, this property is invariant. Suppose the the monk has at least one bead. • If the monk removes 3 red beads and adds 2 green, then he is left with at least the 2 green. (Remember this operation is only allowed if the monk has at least 3 red.) • If the monk has at least one bead before swapping colors, then he has at least one bead after doing so; in fact, chaning colors does not affect the number of beads at all
Induction ill The problem is that this property also holds in the state we're trying to rule out, where the monk has 5 red and 5 green. So this property does not meet all our The monk has an unequal number of red and green beads. This property does hold at this start and does not hold in the " bad"state where the monk has 5 red and 5 green. However, this property is not preserved by every move. For example, if the monk has 13 red and 8 green, then after the next gong he could have 10 red and 10 green. In other words the property is not invariant. a good way to find an invariant is to list a lot of states and look for a distinctive feature they have in common For example here are some states the monk can reach (15,12)→(12,15) (9,17) (17,9) (12,14)→(14,12)→(11,14)→(14,11) (9,16) (11,13) Here the pair (r, g) denotes the state where the monk has r red beads and g green beads Continuing in this way, you might notice that the difference r-g only takes on certain values: 2,-2, 3,-3, 7,-7,8,-8, etc. In particular, the number of red beads minus the number of green beads is always of the form 5k+2 or 5k +3 where k is an integer. The rules for the Temple provide an explanation: adding 3 red and removing 2 green changes the difference by 5 And swapping colors negates the difference. Furthermore, this property holds at the start (since 15-12=5.0+3)and does not hold in the state were trying to prove unreachable (since 5-5=0 is not of the form 5k+ 2 or 5k+ 3). This is exactly the sort of property we need, so we re ready for a proof! Theorem 1. No one leaves the Temple of forever Proof. We use induction on the number of gong rings. Let P(n)be the proposition that after n rings, the number of red beads in the monk's bowl minus the number of green beads is equal to 5k+2 or 5k +3 for some integer k Base case: P(O)is true because initially(after zero rings)the number of red beads minus the number of green beads is 15-12=5.0+3 Inductive step: Now assume that P(n)holds after n gong rings, where n 20. Let r denote the number of red beads in the monk's bowl, and let g denote the number of green beads In these terms, we are assuming that r-g is equal to 5k+ 2 or 5k+ 3 for some integer k After n+ l gong rings, there are two cases to consider, depending on the monk's action 1. If r> 3, then the monk may have replaced 3 red beads with 2 green beads. Thus, the number of red beads minus the number of green becomes (r-3)-(g+2)=(r-g) This is equal to either 5(k-1)+2 or 5(k-1)+3, so P(n+ 1)is true
4 Induction III The problem is that this property also holds in the state we’re trying to rule out, where the monk has 5 red and 5 green. So this property does not meet all our criteria. The monk has an unequal number of red and green beads. This property does hold at this start, and does not hold in the “bad” state where the monk has 5 red and 5 green. However, this property is not preserved by every move. For example, if the monk has 13 red and 8 green, then after the next gong he could have 10 red and 10 green. In other words, the property is not invariant. A good way to find an invariant is to list a lot of states and look for a distinctive feature they have in common. For example, here are some states the monk can reach: (15, 12) → (12, 15) → (9, 17) → (17, 9) ↓ (12, 14) → (14, 12) → (11, 14) → (14, 11) ↓ ↓ ↓ (9, 16) → (16, 9) (8, 16) (11, 13) Here the pair (r, g) denotes the state where the monk has r red beads and g green beads. Continuing in this way, you might notice that the difference r − g only takes on certain values: 2, 2, 3, 3, 7, 7, 8, 8, etc. In particular, the number of red beads minus the number of green beads is always of the form 5k+2 or 5k+3 where k is an integer. The rules for the Temple provide an explanation: adding 3 red and removing 2 green changes the difference by 5. And swapping colors negates the difference. Furthermore, this property holds at the start (since 15 − 12 = 5 0 + 3 · ) and does not hold in the state we’re trying to prove unreachable (since 5 − 5 = 0 is not of the form 5k + 2 or 5k + 3). This is exactly the sort of property we need, so we’re ready for a proof! Theorem 1. No one leaves the Temple of Forever. Proof. We use induction on the number of gong rings. Let P(n) be the proposition that after n rings, the number of red beads in the monk’s bowl minus the number of green beads is equal to 5k + 2 or 5k + 3 for some integer k. Base case: P(0) is true because initially (after zero rings) the number of red beads minus the number of green beads is 15 − 12 = 5 0 + 3 · . Inductive step: Now assume that P(n) holds after n gong rings, where n ≥ 0. Let r denote the number of red beads in the monk’s bowl, and let g denote the number of green beads. In these terms, we are assuming that r − g is equal to 5k + 2 or 5k + 3 for some integer k. After n + 1 gong rings, there are two cases to consider, depending on the monk’s action: 1. If r ≥ 3, then the monk may have replaced 3 red beads with 2 green beads. Thus, the number of red beads minus the number of green becomes: (r − 3) − (g + 2) = (r − g) − 5 This is equal to either 5(k − 1) + 2 or 5(k − 1) + 3, so P(n + 1) is true
5 2. Alternatively, the monk may have exchanged every red bead for a green bead and vice versa. In this case, the number of reds minus the number of greens becomes g-r.Ifr-g=5k+3, then g-r=5(-k)-3=5(-k-1)+2.lfr-g=5k+2 5(k)-2=5(-A-1)+3. Thus, P(n +1)is again tr Therefore, P(n) implies P(n+1) for all n 20 By the induction principle, P(n)is true for all n 20. Since the number of red beads minus the number of greens is always of the form 5k+ 2 or 5k +3 and the difference required to leave the temple does not match either form, no monk can ever leave the Temple of Forever Q Many proofs that a system can not reach a"bad"state share several features with this The induction hypothesis holds initially and is preserved by every move, but does not hold in the"bad state The proof uses induction on time, as measured by gong rings, operations, or what- ever In the inductive step, there is one case for every possible operation In fact the proof that the 9-Number puzzle is unsolvable has the same format 3 The 9-Number puzzle We'l prove the 9-Number Puzzle insoluble using a property that probably would not occur to you immediately, but comes up all the time in puzzles and protocols involving arrangements of objects 3.1 Permutations and inversions A permutation of the numbers 1 thorugh 9 is a sequence containing each digit exactly once. Placing the rows of the puzzle side-by-side gives a permutation of the numbers 1 to 9. For example, the original configuration corresponds to a permutation as shown below: 4|5|6 123456789
Induction III 5 2. Alternatively, the monk may have exchanged every red bead for a green bead and vice versa. In this case, the number of reds minus the number of greens becomes g − r. If r − g = 5k + 3, then g − r = 5(−k) − 3 = 5(−k − 1) + 2. If r − g = 5k + 2, then g − r = 5(−k) − 2 = 5(−k − 1) + 3. Thus, P(n + 1) is again true. Therefore, P(n) implies P(n + 1) for all n ≥ 0. By the induction principle, P(n) is true for all n ≥ 0. Since the number of red beads minus the number of greens is always of the form 5k + 2 or 5k + 3 and the difference required to leave the temple does not match either form, no monk can ever leave the Temple of Forever. Many proofs that a system can not reach a “bad” state share several features with this one: • The induction hypothesis holds initially and is preserved by every move, but does not hold in the “bad state”. • The proof uses induction on time, as measured by gong rings, operations, or whatever. • In the inductive step, there is one case for every possible operation. In fact, the proof that the 9Number Puzzle is unsolvable has the same format. 3 The 9Number Puzzle We’ll prove the 9Number Puzzle insoluble using a property that probably would not occur to you immediately, but comes up all the time in puzzles and protocols involving arrangements of objects. 3.1 Permutations and Inversions A permutation of the numbers 1 thorugh 9 is a sequence containing each digit exactly once. Placing the rows of the puzzle sidebyside gives a permutation of the numbers 1 to 9. For example, the original configuration corresponds to a permutation as shown below: −→ 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9