Maths Olympiad Prep

Library / /16 of 19

Combinatorics Difficulty 6.7 National olympiad Prove it Romania

Each of 2009 (distinct) points in the plane is coloured blue or red, so that on every blue-centered unit circle lie exactly two red points. Determine the largest possible number of blue points.

Solution

Suppose there are rr red points among some nn points. Since any pair of them can lie on at most two blue-centered unit circles, it means that the number bb of blue points can be at most 2(r2)=r(r1)2\binom{r}{2} = r(r-1). Since b+r=nb + r = n, this leads to condition r+r(r1)=r2nr + r(r-1) = r^2 \ge n, i.e. rnr \ge \lceil \sqrt{n} \rceil, so bnnb \le n - \lceil \sqrt{n} \rceil.

A simple model is given by r=nr = \lceil \sqrt{n} \rceil red points of coordinates Ri(ri,0)R_i(r_i, 0), with 0<ri<20 < r_i < 2, for all i=1,2,,ri = 1, 2, \dots, r. Take nrn - r blue points among those r(r1)r(r-1) given by all pairs (i,j)(i, j), 1i<jr1 \le i < j \le r, and of coordinates Bi,j(xi,j,bi,j)B_{i,j}(x_{i,j}, b_{i,j}) and Bi,j(xi,j,bi,j)B'_{i,j}(x_{i,j}, -b_{i,j}), with
xi,j=ri+rj2andbi,j=1(rirj2)2. x_{i,j} = \frac{r_i + r_j}{2} \quad \text{and} \quad b_{i,j} = \sqrt{1 - \left(\frac{r_i - r_j}{2}\right)^2}.
It is trivial to check that all blue points Bi,jB_{i,j}, Bi,jB'_{i,j} are distinct, while on unit circles of these centers lie points RiR_i and RjR_j, and only them.

The choices made warrant that nrr(r1)n - r \le r(r-1), since it comes to nn2n \le \lceil \sqrt{n} \rceil^2, and that (rirj)2/4<1(r_i - r_j)^2/4 < 1. For the given n=2009n = 2009, the answer is thus that the largest possible number of blue points is 20092009=200945=19642009 - \lceil \sqrt{2009} \rceil = 2009 - 45 = 1964.

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.