Olympiad Maths Prep

Library / /39 of 55

Combinatorics Difficulty 6.4 National olympiad Prove it Ukraine

A figure is called *polyomino* if it is formed by joining one or more 1×11 \times 1 squares edge to edge. It is known that a rectangle which is not a square can be split into 8 pairwise distinct polyominos. Polyominos are considered equal if one can be transformed into another by translations and rotations. What is the smallest area of such a rectangle?

Solution

We will start with counting polyominos of smallest area. There is only 1 polyomino of area 1, 1 polyomino of area 2, and 2 polyominos of area 3. Thus, the smallest area of a rectangle that consists of 8 polyominos is 11+12+23+44=251 \cdot 1 + 1 \cdot 2 + 2 \cdot 3 + 4 \cdot 4 = 25. But then it has to be of a size 25×125 \times 1 (since 5×55 \times 5 square doesn't satisfy the condition). It is clear for such a rectangle that it can only be split into rectangles of size k×1k \times 1 and, but such a rectangle has an area at least 1+2+...+8=36>251+2+...+8=36 > 25. Thus, the smallest possible area is 26. An example of splitting a 13×213 \times 2 rectangle is shown on Fig. 18.

Figure 1

Looking for a route rather than 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 and solution reproduced as published; topic and difficulty added by this site.