Possible number of L-tetrominoes in covering an $8 \times 8$ chessboard

discrete mathematicstiling

Assuming that we do not have T-tetrominoes in our play, what are the possible numbers of L-tetrominoes that can appear in a covering with tetrominoes?

I have proven that the number can be any even number, of course, there cannot be more than 16 since each tetromino has 4 grids and we have 64 grids.

I doubt the number can be odd but having a hard time proving it.
Any help?

Picture for all types of tetrominoes (Omitting T-tetromino):

Best Answer

Two L-tetrominoes can be used to cover a $2\times 4$ grid completely and a chessboard can be broken into such rectangles.

Color the columns of the $8\times 8$ chessboard alternatingly white and black.

The tetrominoes will cover the following number of colored squares in such a coloring.

$L$-tet covers $1\ W$, $3\ B$ or $3\ W,1\ B$.

$\mathrm{Straight}$-tet covers $4\ B/W$ or $2\ B,2\ W$

$\mathrm{Square}$-tet covers $2\ B,2\ W$.

$\mathrm{Skew}$-tet covers $2\ B,2\ W$.

Since the number of white and black squares to be colored will be $32$ each, there can't be an odd number of $L$-tetrominoes because they will cover an odd number of black, white squares.

Every other even number $0 \le n=2k \le 16$ is possible. Just cover $k$ '$2 \times 4$ grids' with them and arrange.

Related Solutions

Prove that if two graphs, $G$ and $\overline{G}$, are isomorphic, the number of nodes cannot be twice an odd number.

By way of contradiction, suppose that $|V(G)|=2(2n-1)=4n-2$ for some $n\in\mathbb{N}$.

Let $T$ be the total number of edges possible. This value is is

$$T=\frac{(4n-2)(4n-3)}2=\frac{16n^2-20n+6}{2}=8n^2-10n+3$$

Since $T$ is odd, and $|E(G)|+|E(\overline{G})|=T$, it can never be the case that $|E(G)|=|E(\overline{G})|$. Thus $G\ncong\overline{G}$.

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

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.

Best Answer

Related Solutions

Prove that if two graphs, $G$ and $\overline{G}$, are isomorphic, the number of nodes cannot be twice an odd number.

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

Related Question