Maths Olympiad Prep

Library / /34 of 34

, 2010

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Austria

Two dissections of a square into three rectangles are considered essentially different if one cannot be switched to the other by simple rearrangement of the pieces.
How many essentially different dissections of the 2010×20102010 \times 2010 square into three rectangles with integer side lengths exist such that the area of one rectangle is equal to the arithmetic mean of the areas of the other two?
G. Baron, Vienna

Solution

There are two distinct possibilities for dissections that we must consider. The rectangles can either be in the form of three "strips" (i.e. all with one side of length 20102010) or there can be one such strip, with the other two rectangles resulting from a cut at right angles to the first cut.

We first consider the case of the three strips. Since the areas of the strips are all equal to 20102010 times their width, they must be such that the middle one has a width that is the arithmetic mean of the widths of the other two. Since 2010:3=6702010 : 3 = 670, the width of the middle strip is certainly 670670, and the width of the smallest strip can be any integer less than or equal to 670670. There are therefore 670670 possible dissections in this case.

We now consider the other option. Naming the areas of the three strips AA, BB and CC with B=A+C2B = \frac{A+C}{2} and ACA \leq C, we again have two possible cases. The rectangle with area BB can either be the strip or one of the other rectangles.

Let us assume that the strip has area BB. Since its area is one third of the area of the square, this rectangle has the dimensions 670×2010670 \times 2010. The other two together therefore have the dimensions 1340×20101340 \times 2010, and the common edge must be of length 13401340. Since A<CA < C the shorter edge of the rectangle with area AA can be any integer from 11 to 2010:2=10052010 : 2 = 1005, and there are therefore 10051005 possible dissections in this case.

Finally, we assume that the strip, which has the dimensions a×2010a \times 2010, either has area AA or CC. There must then exist an integer b<2010b < 2010, so that we can write B=(2010a)b=6702010B = (2010-a) \cdot b = 670 \cdot 2010. Since 672670201067^2|670 \cdot 2010 and 672>201067^2 > 2010, both aa and bb must be divisible by 6767, and we can write a=67ca = 67c and b=67db = 67d. Substituting, we therefore obtain (30c)d=300(30-c) \cdot d = 300 with d<30d < 30. Since 30c<3030-c < 30 also holds, we also have d>10d > 10. dd must therefore be a divisor of 300300 between 1010 and 3030, which yields possible values 1212, 1515, 2020 and 2525 for dd. This yields possible values of 55, 1010, 1515 and 1818 for cc, which in turns yields possible values of 335335, 670670, 10051005 and 12061206 for aa. The value a=670a = 670 was already counted in the previous case, however, since this is the case for which A=B=CA = B = C holds. We therefore have possible dissections that have not already been counted.

In total, we obtain 670+1005+3=1678670 + 1005 + 3 = 1678 possible dissections which the required properties.

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.