Tatami-Free Rooms

Tatami are rectangular mats, used to completely cover the floor of a room, without overlap.
Assuming that the only type of available tatami has dimensions $1 \times 2$, there are obviously some limitations for the shape and size of the rooms that can be covered.
For this problem, we consider only rectangular rooms with integer dimensions $a, b$ and even size $s = a \cdot b$.
We use the term ‘size’ to denote the floor surface area of the room, and — without loss of generality — we add the condition $a \le b$.
There is one rule to follow when laying out tatami: there must be no points where corners of four different mats meet.
For example, consider the two arrangements below for a $4 \times 4$ room:

The arrangement on the left is acceptable, whereas the one on the right is not: a red “X” in the middle, marks the point where four tatami meet.
Because of this rule, certain even-sized rooms cannot be covered with tatami: we call them tatami-free rooms.
Further, we define $T(s)$ as the number of tatami-free rooms of size $s$.
The smallest tatami-free room has size $s = 70$ and dimensions $7 \times 10$.
All the other rooms of size $s = 70$ can be covered with tatami; they are: $1 \times 70$, $2 \times 35$ and $5 \times 14$.
Hence, $T(70) = 1$.
Similarly, we can verify that $T(1320) = 5$ because there are exactly $5$ tatami-free rooms of size $s = 1320$:
$20 \times 66$, $22 \times 60$, $24 \times 55$, $30 \times 44$ and $33 \times 40$.
In fact, $s = 1320$ is the smallest room-size $s$ for which $T(s) = 5$.
Find the smallest room-size $s$ for which $T(s) = 200$.

Firstly, in order to form a tatami-free room by divisions, we notice a rule: the smaller side’s length must be equal to or in between the two factors of the larger side’s length. In other words, if a room’s size is $s = a \cdot b$ with $a ≤ b$, it is tatami-free only when there are $p, q$ such that $a ≠ p$, $a = q$ or $p < a < q$, and $p \cdot q = b$.

The factor pairs $(a, b)$ of a given number $s$ can be picked by stepping from both ends of a sorted list of its factors. To make the scanning process faster, we observe that odd factors should always be paired with even factors – any pair of odd factors will not form a tatami-free room as the rule with the $4 \times 4$ room can’t be violated when every tile has even length sides.

To find the smallest room-size $s$ for which $T(s) = 200$, we can firstly generate a range of $s$ (you may need to adjust this range depending on your system’s performance, a reasonable one could be from $2$ to $10^8$). During the scan, for each $s$, we factorize it into pairs. If the number of tatami-free pairs exceeds $200$, we update $s_{max}$. If it falls short of $200$, we update $s_{min}$. We then narrow the range and repeat the loop, until $s_{max} – s_{min} ≤ 1$. The final $s_{max}$ is the $s$ that produces exactly $200$ tatami-free rooms.

There is no known close form solution for this problem and brute force approach is used usually. Due to the complex nature of this problem and heavy computational resources required, it’s generally outside the scope of work for a human tutor to solve by hand. This problem would be more appropriate to solve with a computer program utilizing an appropriate algorithm.

More Answers: