Problem:
Compute the number of ways to color each cell of an square grid either ruby or sapphire such that each contiguous subgrid has exactly 1 ruby cell.
Problem:
Compute the number of ways to color each cell of an square grid either ruby or sapphire such that each contiguous subgrid has exactly 1 ruby cell.
Solution:
Subdivide the grid into 36 subgrids of size . Each contains exactly one ruby cell.
Consider four adjacent subgrids
and the relative positions of the ruby cells within their respective subgrids. Between and , we can check that the ruby cells differ by only a horizontal shift. Likewise, between and , the ruby cells differ by only a vertical shift.
The black star indicates the ruby in A, and the white stars indicate potential locations for rubies in .
It can further be checked that the shift between is the same as between , and likewise between and . Also, it cannot be the case that both a horizontal and a vertical shift is present, as some subgrid will have an invalid number of ruby cells:
Now, in the original grid
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 with a nontrivial vertical shift and also a pair of rows with a nontrivial horizontal shift, the four subgrids at their intersection 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 . Symmetrically, there are 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
For completeness, examples of each of the three cases (no shifts, horizontal shifts only, vertical shifts only) is shown below.
No shifts
Vertical shifts only
Horizontal shifts only