Maths Olympiad Prep

Library / Junior Balkan Mathematical Olympiad /81 of 95

Junior Balkan Mathematical Olympiad

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(r−1)2\binom{r}{2} = r(r-1). Since b+r=nb + r = n, this leads to condition r+r(r−1)=r2≥nr + r(r-1) = r^2 \ge n, i.e. r≥⌈n⌉r \ge \lceil \sqrt{n} \rceil, so b≤n−⌈n⌉b \le n - \lceil \sqrt{n} \rceil.

A simple model is given by r=⌈n⌉r = \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 n−rn - r blue points among those r(r−1)r(r-1) given by all pairs (i,j)(i, j), 1≤i<j≤r1 \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−(ri−rj2)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,j′B'_{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 n−r≤r(r−1)n - r \le r(r-1), since it comes to n≤⌈n⌉2n \le \lceil \sqrt{n} \rceil^2, and that (ri−rj)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 2009−⌈2009⌉=2009−45=19642009 - \lceil \sqrt{2009} \rceil = 2009 - 45 = 1964.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.