Is it possible to divide $9\times 11$ rectangle into one $1\times 3$ rectangle and N tetrominoes

combinatoricscontest-mathdiscrete mathematicstiling

There is a rectangle of size $9\times 11$. Is it possible to divide it using 1 tromino and $N$ tetrominoes?

enter image description here

I have tried a lot and it seems that this is not possible, thus I want to prove it is not possible.

  1. Such a simple method as counting the number of squares, count
    add/even contradictions – seems to not work.
  2. Coloring method. Maybe this works, but then we have not found the
    right coloring.

What I mean – I read that sometimes such problems can be proved by coloring rectangle squares using some specific pattern and this could give some contradiction usually with something odd/even.

We tried a lot of coloring patterns (the simplest one was coloring rectangle squares black and white as chessboard, also coloring first line black, second one line white etc., also tried other coloring patterns). We have not found any contradictions that help us to prove that this is not possible.

It would be nice if someone suggests any ideas, how to proceed with such type of problems.

P.S. I tried this to solve together with my 5th grader and now I am so much into it that I really want to solve it

Best Answer

Here's what turns out to be the only solution, with the $1 \times 3$ tromino in the center:

   i\j 1  2  3  4  5  6  7  8  9 10 11 
    1  2  2  2  3  4  4  4  5  6  6  6 
    2 18  2  3  3  3  4  5  5  5  6 23 
    3 18 18  7  7  7  8  9  9  9 23 23 
    4 18 19 21  7  8  8  8  9 22 24 23 
    5 19 19 21 21  1  1  1 22 22 24 24 
    6 20 19 21 10 11 11 11 12 22 24 25 
    7 20 20 10 10 10 11 12 12 12 25 25 
    8 20 13 14 14 14 15 16 16 16 17 25 
    9 13 13 13 14 15 15 15 16 17 17 17

I used the following integer linear programming formulation. Let $P$ be the set of polyominoes, and let $T \subset P$ be the set of $1 \times 3$ trominoes. Note that $|T| = 9\cdot 9+ 7\cdot 11=158$ and $|P|=|T|+ 2(8\cdot 9+7\cdot 10)= 442$. For $i\in\{1,\dots,9\}, j\in\{1,\dots,11\}$, let $P_{i,j}\subset P$ be the subset of polyominoes that contain square $(i,j)$. Let binary decision variable $x_p$ indicate whether polyomino $p\in P$ is used. The constraints are: \begin{align} \sum_{p \in P_{i,j}} x_p &= 1 &&\text{for $i\in\{1,\dots,9\}, j\in\{1,\dots,11\}$} \\ \sum_{t\in T} x_t &= 1 \\ x_p &\in \{0,1\} &&\text{for $p \in P$} \end{align} The first constraint enforces that exactly one polyomino contains square $(i,j)$. The second constraint forces exactly one tromino to be used.

Related Question