Is an grid tileable with tiles, if one of and is even and the other is odd? If yes, come up with a general strategy to tile it.

Question

Homi · Accepted Answer

The grid's total area must be a multiple of the tile's area.

Step 1 — Check the grid's total area

Let us consider a grid of size $m \times n$ . Its total area is $m \times n$ square units. We are using $2 \times 1$ tiles. Each $2 \times 1$ tile covers 2 square units. For tiling to be possible, the grid's total area must be even. This means the total area must be a multiple of 2.

Let one dimension be even. Let the other dimension be odd. Let $m$ be an even number. Let $n$ be an odd number. An even number can be written as $2 \times k$ . Here, $k$ is a whole number. An odd number can be written as $2 \times j + 1$ . Here, $j$ is a whole number. The total area is $m \times n$ .

$\text{Total Area} = m \times n$

$= (2 \times k) \times (2 \times j + 1)$

$= 2 \times k \times (2 \times j + 1)$

$\boxed{\text{Total Area is an even number}}$

So, the total area is always even. This condition for tiling is met.

Step 2 — Develop a general tiling strategy

We know that one dimension is even. The other dimension is odd. Let us consider two cases.

Case 1: The number of rows ( $m$ ) is even. The number of columns ( $n$ ) is odd. We can place all tiles vertically. Each tile will cover $1 \times 2$ cells. Consider one column of the grid. This column has $m$ cells. Its size is $m \times 1$ . Since $m$ is an even number, we can tile this column. We use $m/2$ vertical $1 \times 2$ tiles. Each tile covers two cells. We can do this for every column. There are $n$ such columns. So, the entire $m \times n$ grid can be tiled.

Diagram 1

Case 2: The number of columns ( $n$ ) is even. The number of rows ( $m$ ) is odd. This is similar to Case 1. We can place all tiles horizontally. Each tile will cover $2 \times 1$ cells. Consider one row of the grid. This row has $n$ cells. Its size is $1 \times n$ . Since $n$ is an even number, we can tile this row. We use $n/2$ horizontal $2 \times 1$ tiles. Each tile covers two cells. We can do this for every row. There are $m$ such rows. So, the entire $m \times n$ grid can be tiled.

In both cases, we can tile the grid. The strategy is to align tiles along the even dimension.

Answer

(i) Yes, an $m \times n$ grid is tileable. (ii) The general strategy places tiles along the even dimension. If $m$ is even, tile each column. Use vertical $1 \times 2$ tiles. If $n$ is even, tile each row. Use horizontal $2 \times 1$ tiles.

Question 39

Answer

More questions in IT