$n$ -by- $n$ grid ception?

Logic Level 4

Find the largest positive integer $n$ that satisfies these conditions:

1 . $n$ is not divisible by $3$ .

2 . The $n$ -by- $n$ cannot be covered by 1 I-shaped-tetromino piece and $\dfrac{n^2-4}{3}$ I-shaped-triomino pieces.

Image of an I-shaped-tetromino:

Image of an I-shaped-triomino:

This problem is not original

The answer is 5.

1 solution

Tran Hieu
Mar 7, 2016

If n = 3k+1

We can fill the left 3k columns with I-shaped-triomino, using n*k pieces, stack into k 3-width-columns, each column have n pieces stacking horizontally. After that, the grid have a 1-by-(3k+1) grid unfilled. This could be filled by k-1 I-shaped-triominos and one I-shaped-tetromino stack vertically.

An example with n=7

If n=3k+2 and n>=8:

First we see that a 8-by-8 grid could be filled

For any other n=3k+2 and >8, we could apply a 8-by-8 grid at the top left and divide the rest into two grid: one is 3(k-2) 8 and the other is 3(k-2) n and fill the rest easily.

Now all left is to prove that you cannot fill a 5-by-5 grid.

Let's label a 5-by-5 grid by number like this

We see that each triomino when placed will take place of exactly one of each type of cell (i.e. one cell label 1, one cell label 2 and one cell label 3). There are 9 cells label 1, 8 cells label 2 and 8 cells label 3 so that mean the tetromino will have one of its head take place of cell label 1. This hold true for both way of labeling, and the only cell that label 1 in both way is the center cell, so that mean the tetromino will have one of its head in the center cell, which is impossible.

Nice work \Ò v Ó/

Trung Đặng Đoàn Đức - 5 years, 3 months ago

n n n -by- n n n grid ception?

The answer is 5.

1 solution

0 pending reports

$n$ -by- $n$ grid ception?