Competition problem — Combinatorics

Library / /68 of 86

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it United States

Problem:

Define a size- $n$ tromino to be the shape you get when you remove one quadrant from a $2n \times 2n$ square. In the figure below, a size-1 tromino is on the left and a size-2 tromino is on the right.

We say that a shape can be tiled with size-1 trominos if we can cover the entire area of the shape—and no excess area—with non-overlapping size-1 trominos. For example, a $2 \times 3$ rectangle can be tiled with size-1 trominos as shown below, but a $3 \times 3$ square cannot be tiled with size-1 trominos.

a) Can a size-5 tromino be tiled by size-1 trominos?

b) Can a size-2013 tromino be tiled by size-1 trominos?

Justify your answers.

Solution

Solution:

We will abbreviate "tile with size-1 trominos" with "tile." It is possible to tile a size-5 tromino as drawn.

It is also possible to tile a size-2013 tromino. In fact, any size- $n$ tromino can be tiled with size-1 trominos, which can be proved with mathematical induction as follows.

Size-1, size-2, and size-3 trominos can be tiled as shown below.

If $k$ is even, it is possible to tile a $3 \times k$ rectangle as shown.

Suppose that a size- $n$ tromino can be tiled. Then we can tile a size- $(n+3)$ tromino as follows.

If $n$ is even, fill in the size- $(n+3)$ tromino with a size- $n$ tromino, plus a border of width 3 that can be made from two $3 \times n$ rectangles at the ends, two $3 \times (2n+2)$ rectangles along the sides, and one corner patch that is a $4 \times 4$ square with a corner removed.

If $n$ is odd, fill in the size- $(n+3)$ tromino with a size- $n$ tromino, plus a border that can be made from two $3 \times (n-1)$ rectangles at the ends, two $3 \times (2n-2)$ rectangles at the sides, and three corner patches. See the figure below.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.