0

This question is question $6$ on INMO $2020$:

A stromino is a $3 \times 1$ rectangle. Show that a $5 \times 5$ board divided into twenty-five $1 \times 1$ squares cannot be covered by $16$ strominos such that each stromino covers exactly three unit squares of the board and every unit square is covered by either one or two strominos. (A stromino can be placed either horizontally or vertically on the board.)

The solution is provided here, but I was thinking of a different method.

If we assume that we can divide the strominoes into two layers, the problem becomes quite simple. However, the list of common mistakes includes:

Covering the boards with $2$ ‘layers’ of strominoes. Not all arrangements are composed of two disjoint layers.

While this is true, I was wondering if we can prove that all arrangements that are not composed of two disjoint layers, can be converted to equivalent arrangements of two disjoint layers, by only vertical displacement (i.e. moving a strominoe up or down into a different layer). For example:

enter image description here

is equivalent to enter image description here

So my question is:

Is there a way to prove or disprove this?

Vivaan Daga
  • 5,531
Righter
  • 811
  • Are we restricted to just a $1 \times n$ board? Also, I presume the original arrangements have to satisfy the problem requirement (that each square is covered by either one or two stromino)? – VTand Nov 23 '21 at 15:01
  • Excuse me for my poor understanding, but could you define layer and disjoint? – Jiaze Zhang Nov 23 '21 at 16:16
  • @VTand Sorry for the bad diagram. This is meant to be a side view of the $5 \times 5$ board, with $3$ layers in the first one and $2$ layers in the second one. Yes, the original arrangements have to satisfy the condition. – Righter Nov 23 '21 at 17:43
  • @JiazeZhang A layer is a part of the arrangement, which is only one stromino high. A disjoint layer is one that is possible to separate from the other layers, i.e. if we glue together all the pieces in a disjoint layer, we can pick it up without disturbing any other layer. – Righter Nov 23 '21 at 17:45

1 Answers1

1

Here is a configuration satisfying the conditions of the question

$$ \begin{array} { c c c } ak & k & jk & j & ij\\ a & x & x & x & i\\ ab & de & e &ef & hi\\ b & dy & y & fy & h\\ bc & cd &cg & fg & gh\\ \end{array} $$

Notice that the triminos from $a$ to $k$ give us a chain of 11 triminos where each one overlaps with the 2 adjacent ones ($k$ and $a$ are adjacent), hence each adjacent pair of letters have to be on distinct layers.
Thus, it's not possible to split these 11 triminos onto 2 distinct layers. (An odd-chain is not a bipartite graph.)

Hence, it is true that "Not all arrangements are composed of 2 disjoint layers".

Original writeup:

Caveat: I'm not satisfying the condition of "each square is covered by 1 or 2 triminos". I've not investigated if there's a way to modify this example easily. (EG In this example, the bottom left square cannot be covered)

Note: With the relaxation of this condition, we can place 16 triminos (without covering the center square). Hence, this is an important condition to consider, which suggests the solution as listed in the document.

Here is a $5 \times 5 $ board where each square is covered by at most 2 triminos.

We have a chain of 9 triminos ($a, b, c, \ldots i$), where each trimino covers the adjacent 2 triminos (and $i$ covers $a$ too).
Hence we cannot split them up into 2 disjoint layers.
(No way to split an odd-chain into a bipartite graph.)

$$ \begin{array} { c c c } a & & & & \\ ai & i & hi & h & gh\\ ab & bc &be & &g \\ &c & ef & f& fg\\ &cd &de &d & \\ \end{array} $$

Calvin Lin
  • 68,864