Ravi Dayabhai & Conrad Warren 🧱 2024-06-21
Consider the following array of 25 squares:
You are filling the array with rectangles by repeating the following two steps:
Select one of the 12 squares along the outer perimeter that has not yet been selected as part of a rectangle.
Form the largest rectangle you can that includes the square you just selected and other squares that are not yet part of any such rectangle.
You repeat these steps until every square along the perimeter has been selected.
How many distinct final states are possible? (Note: States that are rotations or reflections of each other should be counted as distinct.)
106 distinct final states.
We proceed with casework.
First, we can place a $3 \times 5$ rectangle by selecting a perimeter square on the third or fifth row. This results in two singleton squares on the left and right, and two "t-blocks" on the top and bottom.
It can be shown that any "t-block" can then result in two different states (as illustrated above), and the singleton squares when selected only result in one unique state.
Therefore, the total unique states from having initially selecting a perimeter square that generates a $3 \times 5$ rectangle is $2 \times 2 \times 1 \times 1 = 4$. Due to symmetry, this results in $8$ distinct states.
Second, we can place a $1 \times 7$ rectangle by selecting a perimeter square at the very top/bottom or left/right of the array. This divides the shape into two symmetrical "pyramids" formed by $1 \times 5$, $1 \times 3$, and $1 \times 1$ rows (bottom to top, respectively).
$1$ state arises from placing a $2 \times 3$ rectangle on this "pyramid" (since the remaining three singleton squares each result in one unique state):
Another $2$ states arise from placing a $1 \times 5$ rectangle on the base of the "pyramid". As shown below, the resultant "t-block" produces two unique states.
Lastly, placing a $1 \times 3$ rectangle (by selecting the top of the "pyramid"), the "pyramid" is divided into two symmetric 3-square "L-blocks". As show, each of these "L-blocks" produce two unique states.
Hence, $2 \times 2 + 2 + 1 = 7$ total unique states arise from the "pyramid".
By first placing the $1 \times 7$ rectangle (and by symmetry), we count $2 \times 7 \times 7 = 98$ resulting unique states.
Thus, in total, there are $8 + 98 = 106$ distinct final states.
