Maths Olympiad Prep

Library / /611 of 740

, 2024

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Compute the number of ways to color each cell of an 18×1818 \times 18 square grid either ruby or sapphire such that each contiguous 3×33 \times 3 subgrid has exactly 1 ruby cell.

Solution

Solution:

Subdivide the grid into 36 subgrids of size 3×33 \times 3. Each contains exactly one ruby cell.
Consider four adjacent subgrids
ABCD \begin{array}{c|c} A & B \\ \hline C & D \end{array}
and the relative positions of the ruby cells within their respective 3×33 \times 3 subgrids. Between AA and CC, we can check that the ruby cells differ by only a horizontal shift. Likewise, between AA and BB, the ruby cells differ by only a vertical shift.
Figure 1
The black star indicates the ruby in A, and the white stars indicate potential locations for rubies in B,CB, C.
It can further be checked that the shift between A,BA, B is the same as between C,DC, D, and likewise between A,CA, C and B,DB, D. Also, it cannot be the case that both a horizontal and a vertical shift is present, as some 3×33 \times 3 subgrid will have an invalid number of ruby cells:
Figure 2
Now, in the original grid
Figure 3
we conclude that between each of the 5 pairs of adjacent columns of subgrids, there is some constant vertical shift, and that between each of the 5 pairs of adjacent rows of subgrids, there is some constant horizontal shift. However, if there exists both a pair of columns (x1,x2)\left(x_{1}, x_{2}\right) with a nontrivial vertical shift and also a pair of rows (y1,y2)\left(y_{1}, y_{2}\right) with a nontrivial horizontal shift, the four subgrids at their intersection (x1,x2)×(y1,y2)\left(x_{1}, x_{2}\right) \times\left(y_{1}, y_{2}\right) would violate our reasoning above. Hence, there are either only vertical shifts, only horizontal shifts, or neither. Equivalently, all rubies are contained within either six equally spaced rows or six equally spaced columns. It can be checked that all such configurations are valid.
To count the number of ways to place all rubies into six equally spaced rows, we have 3 choices for which rows to choose, and 3 choices within each row for where the rubies are located. This gives 373^{7}. Symmetrically, there are 373^{7} ways to place all rubies into six equally spaced columns. To adjust for overcounting, we note that there are 9 possibilities where all rubies are contained in six rows and six columns. The answer is
2379=4365 2 \cdot 3^{7}-9=4365
For completeness, examples of each of the three cases (no shifts, horizontal shifts only, vertical shifts only) is shown below.
Figure 4
No shifts
Figure 5
Vertical shifts only
Figure 6
Horizontal shifts only

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.