Maths Olympiad Prep

Library / /11 of 15

Combinatorics Difficulty 5.0 AIME, harder Prove it United States

Problem:

A 23×2323 \times 23 square is divided into smaller squares of dimensions 1×11 \times 1, 2×22 \times 2, and 3×33 \times 3. What is the minimum possible number of 1×11 \times 1 squares?

Solution

Solution:

Color the rows of the square black and white alternately, so the top and bottom rows are black. Then each 2×22 \times 2 tile covers two cells of each color, and each 3×33 \times 3 tile covers six of one color and three of the other. In particular, if only 2×22 \times 2 and 3×33 \times 3 tiles are used, the difference between the number of black and white cells covered is divisible by 33. But the entire board has 2323 more black than white cells (if the bottom row were removed, the colors would be equally represented). So there must
Figure 1
be at least one 1×11 \times 1 tile.

To construct the required tiling with only one 1×11 \times 1 tile, first use 3×33 \times 3 tiles to build a 9×129 \times 12 rectangle and 2×22 \times 2 tiles to build a 2×122 \times 12 rectangle. Join these two rectangles to form an 11×1211 \times 12 rectangle. Then use four copies of this 11×1211 \times 12 rectangle, together with the 1×11 \times 1 square, to build a 23×2323 \times 23 square as shown in the diagram.

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.