Each one of 2009 distinct points in the plane is coloured in blue or red, so that on every blue-centered unit circle there are exactly two red points. Find the gratest possible number of blue points.
Problem
Source: JBMO 2009 Problem 4
Tags: ceiling function, analytic geometry, geometry, circumcircle, combinatorics proposed, combinatorics
28.06.2009 00:46
Saleme, are the two red points on the blue-centered circle or are they in it? Btw thank you very much for posting the problems
28.06.2009 00:56
They are "on" I have edited my post Thank you for informing me about this.
28.06.2009 00:59
You're very welcome
28.06.2009 04:39
I see no-one hurries to post a solution Suppose there are $ r$ red points among some $ n$ points. Since any pair of them can lie on at most two blue-centered unit circles, it means that the number $ b$ of blue points can be at most $ 2\genfrac {(} {)} {0pt} {} {r} {2} = r(r - 1)$. Since $ b + r = n$, this leads to condition $ r + r(r - 1) = r^2 \geq n$, i.e. $ r \geq \left \lceil \sqrt{n} \ \right \rceil$, so $ b \leq n - \left \lceil \sqrt{n} \ \right \rceil$. A simple model is given by $ r = \left \lceil \sqrt{n} \ \right \rceil$ red points of coordinates $ R_i(r_i, 0)$, with $ 0 < r_i < 2$, for all $ i = 1,2,\dots,r$. Take $ n - r$ blue points among those $ r(r - 1)$ given by all pairs $ (i, j)$, $ 1 \leq i < j \leq \left \lceil \sqrt{n} \right \rceil$, and of coordinates $ B_{i,j}(x_{i,j}, b_{i,j})$ and $ B'_{i,j}(x_{i,j}, -b_{i,j})$, with \[ x_{i,j} = \frac {r_i + r_j} {2} \ \textrm{ and } \ b_{i,j} = \sqrt{1 - \left ( \frac {r_i - r_j} {2} \right ) ^2 }.\] It is trivial to check that on a unit circle of center $ B_{i,j}$ or $ B'_{i,j}$ lie points $ R_i$ and $ R_j$, and only them. The choices made warrant that $ n - r \leq r(r - 1)$, since it comes to $ n \leq \left \lceil \sqrt{n} \ \right \rceil ^2$, and that $ \displaystyle \left ( \frac {r_i - r_j} {2} \right ) ^2 < 1$. For the given $ n = 2009$, the answer is thus that the largest possible number of blue points is $ 2009 - \left \lceil \sqrt{2009} \ \right \rceil = 2009 - 45 = 1964$.
30.06.2009 20:24
02.07.2009 19:35
any other solution to the problem? :
03.07.2009 11:33
@bugi: The red points are located inside this 45-gon???
02.09.2009 10:01
Late answer The red points are the vertices of the regular 45-gon, its circumradius is less than 1. It isn't the best configuration (putting them on a line is much much better).