A square grid is given. Let us consider all possible paths along grid lines, going from the centre of the grid to the border, such that (1) no point of the grid is reached more than once, and (2) each of the squares homothetic to the grid having its centre at the grid centre is passed through only once.
(a) Prove that the number of all such paths is equal to .
(b) Find the number of pairs of such paths that divide the grid into two congruent figures.
(c) How many quadruples of such paths are there that divide the grid into four congruent parts?
Solution
### Part (a)
1. Define the Concentric Squares:
Let the concentric squares be denoted by . Each is a square of side length centered at the origin.
2. Initial Step from Center:
There are 4 ways to move from the center to the first square .
3. **Path from to :**
- Once on , the path can wander around in one of two senses (clockwise or counterclockwise).
- If the path reaches a corner of (there are 4 corners, each with 2 ways to reach, totaling 8 ways), there are 2 ways to step out to .
- If the path reaches a non-corner point of (there are such points), there is only 1 way to step out to .
4. Counting the Paths:
- For each , the number of ways to step out to is (since and ).
- Therefore, the total number of paths is given by:
### Part (b)
1. Restricting the Paths:
- For pairs of paths that divide the grid into two congruent figures, each path must be symmetric with respect to the center.
- This restricts the wandering on such that no point is touched by more than one path.
2. Counting the Pairs:
- The number of such pairs is given by:
### Part (c)
1. Restricting the Paths Further:
- For quadruples of paths that divide the grid into four congruent parts, each path must be symmetric with respect to both the center and the axes.
- This further restricts the wandering on such that no point is touched by more than one path.
2. Counting the Quadruples:
- The number of such quadruples is given by: