Maths Olympiad Prep

Library / /15 of 19

Geometry Difficulty 6.9 National olympiad Prove it Ukraine

Let n=2m+1n = 2m + 1 for some integer mm. nn points A1,A2,,AnA_1, A_2, \dots, A_n are chosen on two parallel lines. What is the largest possible number of acute triangles among the triangles AiAjAkA_iA_jA_k over 1i<j<kn1 \le i < j < k \le n?

Solution

Let us put points on these two lines in such a way that projections of every two adjacent points from one line to another surround exactly one point on another line and there are no obtuse angles ABC\angle ABC such that BB lies on one line and A,CA, C on another one (clearly, we can achieve this if distances between points will be sufficiently small). It's easy to check that in this case there are exactly 16m(m+1)(2m+1)\frac{1}{6}m(m+1)(2m+1) acute triangles.

Let us project all the points on one of the two lines and color projections of the points from one line in white and from another one in black. Then an acute triangle may be obtained only from points A,B,CA, B, C such that BB lies between AA and CC and AA and CC have the same color which is different from BB (but we should note that the converse is not necessarily true). We will show by induction that there are at most 12+22++m2=16m(m+1)(2m+1)1^2 + 2^2 + \cdots + m^2 = \frac{1}{6}m(m+1)(2m+1) such good triples if there are 2m+12m+1 points.

For m=0m=0 the statement is obvious. Suppose that we proved it for m1m-1. Let us show that this is also true for mm. We number the points as A1,A2,,A2m+1A_1, A_2, \dots, A_{2m+1} and consider a coloring with the largest number of such triples.

Assume that A1,A2m+1A_1, A_{2m+1} have the same color (WLOG it's white). Let among the points from A2A_2 to A2mA_{2m} exactly ww are white and bb are black points. Observe that there are at most 12+22++(m1)21^2 + 2^2 + \cdots + (m-1)^2 good triples among the points from A2A_2 to A2mA_{2m}, bb triples which contain A1A_1 and A2m+1A_{2m+1} and also bwbw triples which contain exactly one point from A1A_1 and A2m+1A_{2m+1} (because for every pair of points of different colors, there is exactly one point from A1A_1 and A2m+1A_{2m+1} which will form a good triple with them). So, we have at most 12+22++(m1)2+b(w+1)1^2 + 2^2 + \cdots + (m-1)^2 + b(w+1) good triples. Observe also that b+w=2m1b+w=2m-1, hence b(w+1)m2b(w+1) \le m^2 and there are at most 12+22++(m1)2+m21^2 + 2^2 + \cdots + (m-1)^2 + m^2 good triples and in this case the induction proceeds.

From now we will assume that A1A_1 and A2m+1A_{2m+1} have different colors.

Consider any two adjacent points Ai,Ai+1A_i, A_{i+1} such that AiA_i is white and Ai+1A_{i+1} is black. Let there are w1w_1 white and b1b_1 black points among the points from A1A_1 to Ai1A_{i-1}, and w2w_2 white and b2b_2 black points among the points from Ai+2A_{i+2} to A2m+1A_{2m+1}. Then if we swap AiA_i and Ai+1A_{i+1}, the number of good triples will increase by (b2+w1)(b1+w2)(b_2+w_1)-(b_1+w_2). Since our coloring is optimal by assumption then (b1+w2)(b2+w1)(b_1+w_2) \ge (b_2+w_1) and so (w1b1)(w2b2)(w_1-b_1) \le (w_2-b_2).

WLOG A1A_1 is white and A2m+1A_{2m+1} is black. Let AkA_k be the first black point and AlA_l be the last white (k<lk<l, because otherwise, we don't have good triples). Let us apply the statement above for the points Ak1,AkA_{k-1}, A_k: for the points to the left of them the difference (white points)–(black points) = k20k-2 \ge 0 and so for the points to the right of them this is non-negative. Hence, the difference (white points)–(black points) for all the points is non-negative. On the other hand, let us apply this statement for the points Al,Al+1A_l, A_{l+1}: for the points to the right of them the difference (white points)–(black points) = (2m+1l1)=l2m0-(2m+1-l-1)=l-2m \le 0 and so for the points to the left of them this is non-positive. Hence, the difference (white points)–(black points) for all the points is non-positive. But before we showed that this difference is non-negative, so it's zero and then the number of points is even, so we got a contradiction.

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.