Olympiad Maths Prep

Track / Stage 6 / 272 of 400 #1272 of 2000

Problem 1272

National olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

A 23×2323 \times 23 square is tiled with 1×1,2×21 \times 1, 2 \times 2 and 3×33 \times 3 squares. What is the smallest possible number of 1×11 \times 1 squares?

Official solution

1. Initial Assumption and Coloring:
- Suppose we do not need any 1×11 \times 1 tiles.
- Color the 23×2323 \times 23 square in a checkerboard pattern, starting with the first row as black. This means alternate rows are black and white.
- In this pattern, there will be 1212 black rows and 1111 white rows, each containing 2323 squares.
- Therefore, the number of black squares is 12×23=27612 \times 23 = 276 and the number of white squares is 11×23=25311 \times 23 = 253.
- The difference between the number of black and white squares is 276253=23276 - 253 = 23.

2. **Properties of 2×22 \times 2 and 3×33 \times 3 Tiles:
-
Observation 1:** A 2×22 \times 2 tile covers 22 black and 22 white squares, so the difference in the number of black and white squares within any 2×22 \times 2 tile is 00.
- Observation 2: A 3×33 \times 3 tile covers either 66 black and 33 white squares or 33 black and 66 white squares. Thus, the difference in the number of black and white squares within any 3×33 \times 3 tile is ±3\pm 3.

3. Divisibility Argument:
- The difference in the number of black and white squares in the entire 23×2323 \times 23 square is 2323, which is not divisible by 33.
- Since the difference contributed by 2×22 \times 2 tiles is 00 and by 3×33 \times 3 tiles is ±3\pm 3, the total difference must be a multiple of 33 if only 2×22 \times 2 and 3×33 \times 3 tiles are used.
- However, 2323 is not a multiple of 33, leading to a contradiction.

4. Conclusion:
- Therefore, it is impossible to tile the 23×2323 \times 23 square using only 2×22 \times 2 and 3×33 \times 3 tiles without using at least one 1×11 \times 1 tile.

5. Example Construction:
- Place one 1×11 \times 1 tile in the center of the 23×2323 \times 23 square.
- This leaves a 22×2222 \times 22 area to be tiled.
- The 22×2222 \times 22 area can be divided into four 11×1111 \times 11 squares.
- Each 11×1111 \times 11 square can be tiled using 2×22 \times 2 and 3×33 \times 3 tiles.

The final answer is 1\boxed{1}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.