22
$\begingroup$

I recently stumbled upon the following problem:

Consider the plane: You may color each point either red or blue. Is there a way to color it such that each unit circumference (centred anywhere) contains exactly one blue point? And two?

I solved it relatively easy: the "one" case has no solution, and the "two" case is solved placing the blue points in a set of parallel lines, at a distance of two from their neighbours.

Of course I couldn't resist the temptation to consider the $n$ case: For $n$ even, the solution is easily extended considering lines at a distance of $4/n$.

My question is: any help for the odd $n$ case?

If there is any justice in the world, there should be no solution, but I honestly don't know where to start.

EDIT: I have had this idea: if I have a solution for an $m$ case, and another for the $n$ case, such that they do not intersect (that is, whenever a point is blue in a solution it is not in the other) then simply superimposing the solutions yields a valid $m+n$ solution. It also stands to reason that if a $k$ solution exists, and contains an $m$ solution, then removing it yields a $k-m$ solution.

So all that I need to prove is that an odd $k$ solution must contain a $k-1$ solution, and therefore also a $1$ solution, which I have shown cannot exist, and therefore also the generic odd solution cannot exist.

For reference: I know geometry up to the basics of manifolds, analysis up to (but not including) Lebesgue measure and integration, and some group theory.

Here is the proof for the $n = 1$ case: Obviously, there must be at least one blue point: otherwise any circumference would contain no blue points and break the condition. Consider the circle centred in that blue point: it must have one blue point. We therefore have two blue points at a distance of 1, therefore there is a circle that contains both, and violates the condition. Thus, there cannot be a successful configuration of blue points, QED.

I also have this other proof: Take one blue point. Consider all circles containing that point. Those circles cannot have any other blue point, because they must have exactly one. All those circles cover a disc of radius 2 centered in the blue point, and said disc cannot contain any other blue points. Therefore the circle centered in the blue point contains no blue points and breaks the condition, QED.

$\endgroup$
  • 1
    $\begingroup$ Small observation: doing this (for $n$) is the same as choosing a bunch of circles of radius 1 on the plane so that each point lies on exactly $n$ circles. $\endgroup$ – Mees de Vries Apr 28 '16 at 17:10
  • 3
    $\begingroup$ I think $8$ upvotes within $17$ minutes resolves the "improper use of Stackexchange" issue :-) $\endgroup$ – joriki Apr 28 '16 at 17:19
  • 2
    $\begingroup$ Perhaps you could share your proof for $n=1$? Since this is the one you want to generalise. $\endgroup$ – joriki Apr 28 '16 at 17:20
  • 1
    $\begingroup$ @RiccardoOrlando, instead of choosing a point $p$ on the plane, and thus adding one blue point to each of the circles centered at distance 1 from $p$, we put a circle on the plane centered at $p$, which "adds 1 present circle" to each point distance 1 away from $p$. $\endgroup$ – Mees de Vries Apr 29 '16 at 12:10
  • 1
    $\begingroup$ @RiccardoOrlando, "Choosing points in the plane so that each unit circle contains precisely $n$ of the chosen points" is the same as "choosing points in the plane so that each point has precisely $n$ of the chosen points at unit distance" is the same as "choosing unit circles in the plane so that each point has precisely $n$ of the chosen circles hitting it". $\endgroup$ – Mees de Vries Apr 29 '16 at 12:28
1
$\begingroup$

Assuming the axiom of choice, there is nothing really preventing a solution with $n=3$ to exist (unlike the $n=1$ case where a single blue point forced some red all over the place)

Biject the set of unit circles onto the smallest ordinal with $\Bbb R$'s cardinality, $\alpha$, and do a transfinite induction on $\alpha$.

Let $\beta \in \alpha$, and suppose we have selected blue points for all the circles number $\gamma$ with $\gamma \in \beta$ without creating any circle with unit circumference that have four blue points.

If circle $\beta$ already has three blue points, we don't have to do anything.

If not, we will have to select between one and three points on it, while not introducing any circle with four blue points. For any triplet of blue points, if their circle has unit circumference, then we can't add anymore blue point on them. But in total, there are always at most $\beta^3 <\alpha$ circles who already have three blue points, and each of those circles can only intersect circle number $\beta$ at at most two points, so those cannot cover our circle completely.

So we will always have room to choose the few necessary blue points without making any circle with four blue points.

$\endgroup$
  • 1
    $\begingroup$ Perhaps worth pointing out (although it is sort of mentioned in the first sentence), as this initially confused me, that the crucial difference between $n = 1$ and $n \geq 3$ is that for $n \geq 3$, $\kappa$ chosen points can "fill" at most $\kappa$ circles, while when $n = 1$, even a single point can fill $\mathfrak c$ circles. $\endgroup$ – Mees de Vries Oct 20 '16 at 9:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.