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 true4 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