Maths Olympiad Prep

Library / /78 of 94

Geometry Difficulty 6.8 National Olympiad Prove it Hong Kong

Alice and Bob play a game on the plane. Firstly, Alice draws 4 red points which are the vertices of a square, and draws another 2021 red points inside this square such that no three red points are collinear. Next, Bob draws nn blue points such that for every triangle whose three vertices are the red points, there is at least one blue point lying strictly inside this triangle.

The goal of Alice is to maximize nn, while the goal of Bob is to minimize nn. Find the value of nn if both players play optimally.

Solution

The answer is 40444044.

After Alice has drawn the 44 red vertices of a square, we can draw one of the diagonals of the square to form 22 triangles. Each time when Alice draws one more red point inside the square, it must lie inside one of the triangles formed. By joining the new red point to the 33 vertices of this triangle, we obtain a new triangulation with 22 more triangles. At the end, when Alice has drawn all the red points, there is a triangulation with 2+2×2021=40442 + 2 \times 2021 = 4044 triangles. Since there is a blue point in each of these triangles, we must have n4044n \ge 4044.

Figure 1

Next, we provide a strategy for Bob so that it is sufficient to draw 40444044 blue points. We set up a coordinate system such that all red points have different xx-coordinates. For each red point P(x,y)P(x, y) inside the square, Bob draws two blue points (x,y+ϵ)(x, y+\epsilon) and (x,yϵ)(x, y-\epsilon) where 2ϵ2\epsilon is the distance from PP to the closest line joining two red points different from PP. We say that these two blue points are associated to the point PP. For the 44 red vertices of the square, Bob does the same thing except that points outside the square need not be drawn. Note that there are only 22 blue points each of which is associated to a vertex of the square whose xx-coordinate is neither the smallest nor the largest. In total, there are 2×2021+2=40442 \times 2021 + 2 = 4044 blue points. We claim that the condition is satisfied.

Indeed, consider any triangle ABCABC with red vertices where the xx-coordinates of AA, BB and CC are in ascending order. WLOG assume BB lies below the line ACAC. Then ABC\angle ABC contains the blue point associated to BB lying above BB since this blue point also lies below the line ACAC. This completes the proof.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.