Olympiad Maths Prep

Library /

Geometry Difficulty 7.5 National olympiad, round 2 Prove it Greece

For a given positive integer n>2n > 2, let C1C_1, C2C_2, C3C_3 be the boundaries of three convex nn-gons in the plane such that the sets C1C2C_1 \cap C_2, C2C3C_2 \cap C_3, C3C1C_3 \cap C_1 are finite. Find the maximum number of points of the set C1C2C3C_1 \cap C_2 \cap C_3.

Solutions — 2

Solution 1

Let us first observe that, if a line intersects a convex nn-gon at finitely many points, then the number of such points is at most 22. Therefore any two of the nn-gons may intersect in at most 2n2n points. Choose two of the nn-gons, C1C_1, C2C_2, and say that their intersection points are p1,p2,,pkp_1, p_2, \dots, p_k. Thus k2nk \le 2n. Say that the union of the set of vertices of C1C_1 and C2C_2 is {q1,q2,,q2n}\{q_1, q_2, \dots, q_{2n}\}. We note that it is possible to have qi=qjq_i = q_j for some iji \ne j.

We will define a one-to-one function ff from {p1,p2,,pk}\{p_1, p_2, \dots, p_k\} to {q1,q2,,q2n}\{q_1, q_2, \dots, q_{2n}\} as follows. First of all, orient all nn-gons in the clockwise direction. Thus, if one traverses an nn-gon according to this orientation, the interior is on the right and the exterior is on the left. For every pip_i, there exist precisely two line segments (of non-zero length) which are subsets of C1C_1 or C2C_2, say [qj,pi][q_j, p_i] on C1C_1 and [qk,pi][q_k, p_i] on C2C_2, such that one can approach to pip_i via these line segments in the clockwise direction. Suppose that the two vectors piqjp_i - q_j and piqkp_i - q_k, in this order, form a right handed coordinate system. Then none of the points on [qj,pi][q_j, p_i] can be on or in the interior of C2C_2, since for any point qq on or in the interior of C2C_2, the vectors piqp_i - q and piqkp_i - q_k are either positive multiples of each other, or form a left handed coordinate system. In this case we set f(pi)=qjf(p_i) = q_j. Otherwise we set f(pi)=qkf(p_i) = q_k. In both cases, the argument above shows that there are no other intersection points between f(pi)f(p_i) and pip_i, in the clockwise direction.

Let us now show that ff is 1-1. If f(pi)=f(pl)=qf(p_i) = f(p_l) = q and qq say (without loss of generality) belong to C1C_1, then the first intersection point encountered when one starts from qq and traverses C1C_1 in the clockwise direction has to be both pip_i and plp_l, hence pi=plp_i = p_l.

Now let us estimate the number of pip_i's that can be contained by the third polygon C3C_3. Each edge of C3C_3 contains exactly 00, 11 or 22 of the pip_i's. Suppose that a given edge of C3C_3 contains 22 of the pip_i's, say p1p_1 and p2p_2. Since C1C_1 and C2C_2 are convex and their intersection with C3C_3 is generic, they should have vertices between (in the clockwise sense) p1p_1 and p2p_2 (with this order), and outside C3C_3. We claim that at least one of these vertices is not in the set f(C1C2C3)f(C_1 \cap C_2 \cap C_3). Let q1C1q_1 \in C_1 and q2C2q_2 \in C_2 respectively be between (in the clockwise sense) p1p_1 and p2p_2 (with this order). If q1q_1 is on or in the interior of C2C_2 (or q2q_2 is on or in the interior of C1C_1), then q1q_1 (or q2q_2) is not in the image of ff, since recall that f(p)f(p) for any pC1C2p \in C_1 \cap C_2 (thus for any pC1C2C3p \in C_1 \cap C_2 \cap C_3) is a point of one of C1C_1, C2C_2 not on or in the interior of the other. So the claim is established in this case. The remaining case is to assume that none of the vertices of any of C1C_1, C2C_2 that lie outside C3C_3 (and between (in the clockwise sense) p1p_1 and p2p_2 (with this order)) also lies in the interior of the other of C1C_1, C2C_2. In this case clearly the polygons C1C_1 and C2C_2 must meet at some point between (in the clockwise sense) p1p_1 and p2p_2 (with this order). Say p3p_3 is the closest to p1p_1 such point. Then clearly f(p3)f(p_3) is a vertex of one of C1C_1, C2C_2 between (in the clockwise sense) p1p_1 and p2p_2 (with this order). These parts of C1C_1, C2C_2 though, lie outside C3C_3; the interior of C3C_3 lies on the other side of the line p1p2p_1p_2. Thus f(p3)f(p_3) is not in f(C1C2C3)f(C_1 \cap C_2 \cap C_3) and the claim is established in all cases.

For the side aa of C3C_3 containing p1p_1, p2p_2 let us call q(a)q(a) a vertex as the one in the claim we just proved. It is easy to see that for distinct sides aa, tt of C3C_3 that contain two of the pp's, the points qaq_a, qbq_b are distinct. Indeed, let aa contain p1p_1, p2p_2 and bb contain p3p_3, p4p_4 among the pp's. If one of qaq_a, qbq_b belongs to one of C1C_1, C2C_2 and the other does not belong to it, we are okay. If both qaq_a, qbq_b belong to say C1C_1, then in a clockwise tour around C1C_1 starting at p1p_1, we meet p1p_1, p2p_2, p3p_3, p4p_4 in this order. If not, say the order is p1p_1, p3p_3, p2p_2, p4p_4. Then the segments p1p2p_1p_2, p3p4p_3p_4 intersect at an interior point, since C1C_1 is a convex polygon. But then the sides aa, bb of C3C_3 have a common interior point, a contradiction. So the correct order is p1p_1, p2p_2, p3p_3, p4p_4. But we know that adding q(a)q(a), q(b)q(b) in this tour the correct order is p1p_1, q(a)q(a), p2p_2, p3p_3, q(b)q(b), p4p_4. Thus q(a)q(a), q(b)q(b) are distinct as claimed.

Now if xx of the edges of C3C_3 contain 11 of the pip_i's and yy of them contain 22 of the pip_i's, then x+yx + y \le number of sides of C3C_3, i.e. x+ynx + y \le n. The number of points in C1C2C3C_1 \cap C_2 \cap C_3 is x+2yx + 2y. Since ff is injective, x+2yx + 2y is also the number of qq's in f(C1C2C3)f(C_1 \cap C_2 \cap C_3). Also, by the argument in the previous paragraph, we see that for every distinct edge of C3C_3 containing 22 points we can assign a corresponding distinct qiq_i outside the image of f(C1C2C3)f(C_1 \cap C_2 \cap C_3). Therefore xx is less or equal to the number of qq's that do not belong in f(C1C2C3)f(C_1 \cap C_2 \cap C_3). So (x+2y)+y(x + 2y) + y is at most as much as the number of qq's. I.e. x+3y2nx + 3y \le 2n. Adding this with x+ynx + y \le n and dividing by 22, and also taking into account that x+2yx + 2y is an integer

x+2y3n2 x + 2y \le \left\lfloor \frac{3n}{2} \right\rfloor

Let us now show that this is the best upper bound for every n3n \ge 3. One way (among many) to construct an example is as follows: Construct two regular nn-gons C1C_1, C2C_2 with the same center, such that their intersection points form a regular 2n2n-gon. Call the vertices p1,p2,,p2np_1, p_2, \dots, p_{2n} in a cyclic order. Let the circumcircle of this 2n2n-gon be CC. Then let the nn-gon bounded by the lines p1p3p_1p_3, p5p7p_5p_7, p9p11p_9p_{11}, \dots (including p2k+1p1p_{2k+1}p_1 in case nn is an odd n=2k+1n = 2k+1) together with the tangent lines to CC at p4p_4, p8p_8, p12p_{12}, \dots be C3C_3. It can easily be checked that C1C2C3=3n2|C_1 \cap C_2 \cap C_3| = \left\lfloor \frac{3n}{2} \right\rfloor.

Solution 2

Let AA and BB be two consecutive points of C1C2C3C_1 \cap C_2 \cap C_3 observed in the clockwise direction from a point in the interior of all three nn-gons. Let's look for each CiC_i its section in the clockwise direction between AA and BB excluding these points. If some two of these sections both do not contain any vertices of their corresponding nn-gons, then the segment ABAB belongs to both nn-gons, a contradiction. Thus at least two of these segments have at least one vertex each, and moreover they do not contain the segment. Trivially, two distinct such vertices exist. Since there exist C1C2C3|C_1 \cap C_2 \cap C_3| many consecutive points AA and BB of C1C2C3C_1 \cap C_2 \cap C_3, there should exist at least 2C1C2C32|C_1 \cap C_2 \cap C_3| distinct vertices of the three nn-gons. Thus 2C1C2C33n2|C_1 \cap C_2 \cap C_3| \le 3n i.e. C1C2C33n2|C_1 \cap C_2 \cap C_3| \le \left\lfloor \frac{3n}{2} \right\rfloor since C1C2C3|C_1 \cap C_2 \cap C_3| is an integer as well).

Actually we can achieve this upper bound by the example given in the Solution 1.

Looking for a route rather than 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.