Maths Olympiad Prep

Library / /815 of 1394

, 2024

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Compute the number of ways to divide a 20×2420 \times 24 rectangle into 4×54 \times 5 rectangles. (Rotations and reflections are considered distinct.)

Solution

Solution:

For convenience, say the edge of length 2020 is vertical.

Consider some vertical line inside the rectangle. It must pass through rectangles of some heights adding to 2020. In particular, these heights correspond to ways to add up to 2020 with fours and fives, which is either 4+4+4+4+44+4+4+4+4 or 5+5+5+55+5+5+5. These options correspond to columns of rectangles with width 55 or 44, respectively. In particular, we need to span the width of the original 20×2420 \times 24 rectangle using these columns, meaning that we can just count the number of ways to add to 2424 with fours and fives.

Figure 1

There are two ways to do this: either 4+4+4+4+4+44+4+4+4+4+4 or 4+5+5+5+54+5+5+5+5. Considering the orders in which the second sum can be written, we get an answer of 1+5=61+5=6.

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.