0%

Problem 256


Problem 256


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×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·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 ≤ 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×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×10.
All the other rooms of size s = 70 can be covered with tatami; they are: 1×70, 2×35 and 5×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×66, 22×60, 24×55, 30×44 and 33×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.


无法铺满榻榻米的房间

榻榻米是一种长方形的垫子,常常用来不重叠地铺满房间的地板。

假定现在只有唯一一种形状为1×2的榻榻米,显然这对于能够铺满榻榻米的房间的形状和大小都将有所限制。

在这个问题中,我们考虑的房间为长方形,相邻两边长为a和b,且面积s=a·b是偶数。
我们用“大小”这个词来表示房间的地板面积,此外,不失一般性,我们假定a ≤ b。

在铺榻榻米的时候必须遵循一个规则:不能有四个榻榻米共用一个顶点。
例如,考虑下面两种铺满4×4房间的铺法:

左边的铺法是可行的,而右边的则不是:有一个红色的”X“出现在当中,标记出被四个榻榻米共用的顶点。

因为这个原因,有些面积为偶数的房间依然不能铺满榻榻米:我们称之为无法铺满榻榻米的房间。
进一步地,我们定义T(s)是面积为s且无法铺满榻榻米的房间种数。

最小的无法铺满榻榻米的房间面积为s = 70,两边长为7×10。
其它所有面积为70的房间都能铺满榻榻米;这些房间的大小分别是:1×70, 2×35和5×14。
因此,T(70) = 1。

同样地,我们可以验证T(1320) = 5,因为当房间面积为s = 1320时,恰好有5种房间无法铺满榻榻米:
20×66,22×60,24×55,30×44和33×40。
事实上,s=1320是使得T(s) = 5的最小房间面积s。

求出使得T(s) = 200的最小房间面积s。