Maths Olympiad Prep

Library / /149 of 520

Combinatorics Difficulty 6.6 National olympiad Find the answer

A square 2n×2n2n\times 2n 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 4i=2n(16i9)4\prod_{i=2}^n(16i-9).
(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 S1,S2,,Sn S_1, S_2, \ldots, S_n . Each Sk S_k is a square of side length 2k 2k centered at the origin.

2. Initial Step from Center:
There are 4 ways to move from the center to the first square S1 S_1 .

3. **Path from Sk S_k to Sk+1 S_{k+1} :**
- Once on Sk S_k , the path can wander around Sk S_k in one of two senses (clockwise or counterclockwise).
- If the path reaches a corner of Sk S_k (there are 4 corners, each with 2 ways to reach, totaling 8 ways), there are 2 ways to step out to Sk+1 S_{k+1} .
- If the path reaches a non-corner point of Sk S_k (there are 8k8 8k - 8 such points), there is only 1 way to step out to Sk+1 S_{k+1} .

4. Counting the Paths:
- For each Sk S_k , the number of ways to step out to Sk+1 S_{k+1} is 16k9 16k - 9 (since 8+(8k8)=8k 8 + (8k - 8) = 8k and 8k1=8k9 8k - 1 = 8k - 9 ).
- Therefore, the total number of paths is given by:
4i=2n(16i9) 4 \prod_{i=2}^n (16i - 9)

### 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 Sk S_k such that no point is touched by more than one path.

2. Counting the Pairs:
- The number of such pairs is given by:
2i=2n(8i5) 2 \prod_{i=2}^n (8i - 5)

### 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 Sk S_k such that no point is touched by more than one path.

2. Counting the Quadruples:
- The number of such quadruples is given by:
i=2n(4i3) \prod_{i=2}^n (4i - 3)

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.