Maths Olympiad Prep

Library / /47 of 52

Geometry Difficulty 7.1 National olympiad, round 2 Prove it Belarus

Call a polygon on a Cartesian plane to be integer if all its vertices are integer. A convex integer 14-gon is cut into integer parallelograms with areas not greater than CC.
Find the minimal possible CC.
(A. Yuran)

Solution

Answer: minimal possible CC equals 55.

First we prove two lemmas.

Lemma 1: the given 14-gon has 77 pairs of opposite parallel sides.
Since the 14-gon is convex, it suffices to prove that each side has a side parallel to it. Consider an arbitrary side ABAB of the given 14-gon. Draw the line perpendicular to ABAB and define on this line the direction to the right in such way that the whole 14-gon lies to the right of ABAB (it is possible since the 14-gon is convex). Consider a parallelogram P1P_1 with one (left) side lying on ABAB and the opposite (right) side lies on another side or inside the 14-gon. If it lies inside the 14-gon, there is another parallelogram P2P_2, the left side of which intersect the right side of P1P_1, while the right side of P2P_2 lies on the side or inside the 14-gon. Continue choosing such parallelograms P1,P2,,PnP_1, P_2, \dots, P_n until finally we find the parallelogram PnP_n, the right side of which lies on some side of the given 14-gon. This side is the required side, parallel to ABAB. Lemma 1 is proved.

Call the sequence P1,P2,,PnP_1, P_2, \dots, P_n of the parallelograms, defined in the proof of the lemma 1 for an arbitrary side ABAB, the chain of the side ABAB.

Lemma 2: the chains of any two distinct non-opposite sides intersect (i.e. have a common parallelogram).
Consider any two pairs ABABAB \parallel A'B' and CDCDCD \parallel C'D' of opposite sides. Since the 14-gon is convex, if we bypass its perimeter (in some direction), the sides ABAB, CDCD, ABA'B', CDC'D' go in that order. Connect the midpoints of the parallel to ABAB sides of the parallelograms from the chain of ABAB to obtain a polyline (the ends of the polyline are the midpoints of ABAB and ABA'B'). This polyline divides the 14-gon into two parts, with the sides CDCD and CDC'D' lying in distinct parts. Therefore, if we consider a similar polyline, corresponding to the chain of CDCD, these two polylines will intersect. This means that the chains of the sides ABAB and CDCD have a common parallelogram. Lemma 2 is proved.

Take any 77 pairwise nonparallel sides of the 14-gon and to each of them (say, for EFEF) put in the correspondence the shortest possible integer vector v(EF)\vec{v}(EF). Call this vector to be directive for EFEF and denote its coordinates by x(EF)x(EF) and y(EF)y(EF). The minimality of the length of v(EF)\vec{v}(EF) implies gcd(x(EF),y(EF))=1\gcd(x(EF), y(EF)) = 1. From Lemma 2 it follows that for any two non-opposite sides ABAB and CDCD there exists a parallelogram PP with the sides parallel to ABAB and CDCD. The area of PP is divisible by the area of the parallelogram with the sides v(AB)v(AB) and v(CD)v(CD), since PP can be divided into such parallelograms.

Finally, we will prove that there exists a parallelogram with area divisible by 55. The area S(P)S(P) of the parallelogram PP equals x(AB)y(CD)x(CD)y(AB)|x(AB)y(CD) - x(CD)y(AB)|. If both x(AB)x(AB) and x(CD)x(CD) are divisible by 55, then S(P)S(P) is divisible by 55. Suppose that not more than one directive vector has an xx-coordinate which is divisible by 55. Among at least 66 directive vectors with nonzero xx-coordinates there exist vectors with y(AB)x(AB)y(CD)x(CD)(mod5)\frac{y(AB)}{x(AB)} \equiv \frac{y(CD)}{x(CD)} \pmod{5}. Therefore, the area S(P)S(P) of the corresponding parallelogram equals
x(AB)y(CD)x(CD)y(AB)=(y(AB)x(AB)y(CD)x(CD))x(AB)x(CD)0(mod5). |x(AB)y(CD) - x(CD)y(AB)| = \left| \left( \frac{y(AB)}{x(AB)} - \frac{y(CD)}{x(CD)} \right) \cdot x(AB)x(CD) \right| \equiv 0 \pmod{5}.

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.