Maths Olympiad Prep

Library / /15 of 31

Combinatorics Difficulty 6.1 National olympiad Prove it Belarus

The 2022×20222022 \times 2022 board was cut into tetraminoes of two types: L-tetramino LL and Z-tetramino ZZ. Each tetramino consists of four unit squares, tetriminoes can be rotated and flipped.
Find the smallest number of ZZ-tetriminoes that could be obtained.

Solution

Answer: 11.
Let's label the columns of the table from bottom to top with the numbers from 11 to 20222022 and color all the cells of the rows with odd numbers in yellow, and with even numbers — in blue. Each LL-tetromino consists of three squares of one color and one square of another. Let's assume that not a single ZZ-tetromino has been obtained. Since the numbers of yellow and blue cells in the table are equal, the number of LL-tetrominoes consisting of three yellow cells and one blue cell is equal to the number of LL-tetrominoes consisting of three blue cells and one yellow cell. This means that the board is divided into an even number of LL-tetrominoes, but this implies that the total number of cells on the board is a multiple of 88, which is not true. Hence at least one ZZ-tetromino has been obtained.
Let's give an example showing what exactly one ZZ-tetromino can be obtained.

Figure 1

The picture shows how to cut a 6×66 \times 6 board into seven LL-tetrominoes and one ZZ-tetromino. If we cut off such 6×66 \times 6 board from the corner of the 2022×20222022 \times 2022 board, then the rest of the board can be easily cut into 2×42 \times 4 and 4×24 \times 2 rectangles, which are made up of two LL-tetrominoes.

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 and solution reproduced as published; topic and difficulty added by this site.