In chess, a rook at position hr, ci can move in a straight line either horizontally or vertically (to hr ± x, ci or hr, c ± xi, for any integer x). (See Figure 5.11.) A rook’s tour is a sequence of...

In chess, a rook at position hr, ci can move in a straight line either horizontally or vertically (to hr ± x, ci or hr, c ± xi, for any integer x). (See Figure 5.11.) A rook’s tour is a sequence of legal moves, starting from a square of your choice, that visits every square of the board once and only once. Prove by induction that there exists a rook’s tour for any n-by-n chessboard for any n ≥ 1.

Figure 5.12 shows three different fractals. One is the Von Koch snowflake (Figure 5.12(a)), which we’ve already seen: a Von Koch line of size s and level 0 is just a straight line segment; a Von Koch line of size s and level ℓ consists of four Von Koch lines of size (s/3) and level (ℓ − 1) arranged in the shape ; a Von Koch snowflake of size s and level ℓ consists of a triangle of three Von Koch lines of size s and level ℓ. The other two fractals in Figure 5.12 are new. Figure 5.12(b) shows the Sierpinski triangle: a Sierpinski triangle of level 0 and size s is an equilateral triangle of side length s; a Sierpinski triangle of level (ℓ + 1) is three Sierpinski triangles of level ℓ and side length s/2 arranged in a triangle. Figure 5.12(c) shows a related fractal called the Sierpinski carpet, recursively formed from 8 smaller Sierpinski carpets (arranged in a 3-by-3 grid with a hole in the middle); the base case is just a filled square.