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 3696.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 9­Number 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