7
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ And can I ask - how did you find it? You just tried randomly or there was some logic behind it? I spent a lot of time, but have not found this. $\endgroup$ – renathy Jan 16 '20 at 22:29
  • 2
    $\begingroup$ I used integer linear programming, with 442 binary variables (one for each of the possible polyomino placements) and 100 constraints (one for each of the 99 squares, and one to use exactly one 1x3 rectangle). $\endgroup$ – RobPratt Jan 16 '20 at 22:33
  • $\begingroup$ So far I understood the problem formulation as integer linear programming, but how did you solved this equations (formulated Int lp problem). Maybe it is obvious, but I have not used 'such math thinking' for year, just elementāru math... $\endgroup$ – renathy Jan 17 '20 at 6:51
  • 1
    $\begingroup$ I used the OPTMODEL procedure in SAS to formulate and solve the problem and verify uniqueness of the solution. $\endgroup$ – RobPratt Jan 17 '20 at 12:46
8
$\begingroup$

Here is a picture which proves it is possible.

enter image description here

$\endgroup$
2
  • $\begingroup$ Did u also used some method to find this solution? $\endgroup$ – renathy Jan 17 '20 at 6:53
  • $\begingroup$ This should be a problem for 5th grader so it is just trial and error process. But there is always some logical pattern to do it, it is not just some random tiling. $\endgroup$ – Aqua Jan 17 '20 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.