Question

A single – square – covered board is a board of 2ⁿ x 2ⁿ squares in which one square is covered with a single square tile. Show that it is possible to cover this board with triominoes without overlap.

Answer 1

size of the board is 2nⁿ x 2ⁿ

Number of squares = 2ⁿ x 2ⁿ = 4ⁿ

Number of squares covered = 1

Number of squares to be covered = 4ⁿ – 1

4ⁿ – 1 is a multiple of 3

Case 1 : n = 1

The size of the board 2 x 2

one triominoe can cover 3 squares without overlap.

We can cover it with one triominoe and solve the problem.

Case 2 : n ≥ 2

1. place a triominoe at the center of the entire board so as to not cover the covered sub – board.

2. One square in the board is covered by a tile. The board has 4 sub – boards of size 2 x 2 . 2n – 1 2n – 1.

Out of 4 sub – boards one sub – board is a single square covered sub – board.

One triominoe can cover remaining three sub –boards into single square covered sub – board. The problem of size n is divided into 4 sub – problems of size (n – 1). Each sub – board has 2^n-1 x 2^2n-1 – 1 = 2^2n-2 – 1 = 4ⁿ – 1 squares to be covered.

4^n-1 – 1 is also a multiple of 3

In this, the 2ⁿ x 2ⁿ board is reduced to boards of size 2×2 having are square covered. A triominoe can be placed in each of these boards and hence the whole original 2ⁿ x 2ⁿ . board is covered with triominoe with out overlap.