Maths Olympiad Prep

Library / /73 of 101

Combinatorics Difficulty 6.7 National olympiad Prove it Estonia

A rectangular grid whose side lengths are integers greater than 1 is given. Smaller rectangles with area equal to an odd integer and length of each side equal to an integer greater than 1 are cut out one by one. Finally one single unit square is left. Find the least possible area of the initial grid before the cuttings.

Solution

Denote by XX the unit square left. Then XX cannot lie in a corner of the initial rectangle, as the strip between the neighbouring rectangle of XX and the edge of the rectangle could not be cut out (painted gray in Fig. 33). Similarly, XX cannot lie at a side of the initial rectangle, because the strip between two neighbouring rectangles of XX could not be cut out (Fig. 34).

Consider all possibilities of how the unit squares around XX can be distributed between rectangles that are cut out from the initial figure; for simplicity, we identify the 8 unit squares by principal winds. Suppose that the eastern neighbour of XX belongs to rectangle AA. Then either the northeastern

Figure 1
Fig. 34

or southeastern neighbour of XX belongs to AA, too; w.l.o.g., let the northeastern neighbour of XX belong to AA (Fig. 35). The northern neighbour of XX must belong to a rectangle BB distinct from AA. Then the northwestern neighbour of XX must belong to BB. Similarly, the western and southwestern neighbours of XX must belong to a third rectangle CC and the southern and southeastern neighbour of XX must belong to a fourth rectangle DD (Fig. 36).

Figure 2
Fig. 35
Fig. 36

The unit squares of the strip starting from the eastern neighbour of XX and continuing eastward until the edge of the figure distribute between rectangles, as well as the unit squares of the strip starting from the southern neighbour of XX and continuing eastward until the edge of the figure distribute between rectangles. As the area of each rectangle is odd, their side lengths are odd. Thus the lengths of both strips must be representable as sums of 1 or more odd integers greater than 1. These lengths themselves are two consecutive positive integers. The least two consecutive positive integers representable as sums of odd integers greater than 1 are 5 (which is odd itself) and 6 (which is 3+33+3). Hence at least 5 unit squares of the initial figure must be located to the east of XX. Similarly, at least 5 unit squares of the initial figure must be located in each cardinal direction from XX. Thus each side length of the initial rectangle is at least 11 and the area is at least 121. As Fig. 37 shows, this limit can be achieved.

Figure 3
Fig. 37

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.