Irrational painting device

Question

Part a) of the following problem appeared in one of the Putnam Exams (sorry, don't know which year exactly).

If you want to solve Part a) don't read Part b).

You have a painting device, which given the co-ordinates of a points in the 2D plane, will colour all points on that plane black, which are at an irrational distance from the given point.

Initially you start out with the 2D plane being white.

a) You want to colour the whole plane black. What is the minimum number of points you need to feed to the painting device?

_{b) Show that it is sufficient to feed $(0,0), (1,0), (\sqrt{2},0)$.}

Answer 1

Just so I don't forget, here is the solution I was thinking of, for part b).

Let $(x,y)$ be a point which is at a rational distance from $(0,0), (1,0)$ and $(\sqrt{2},0)$.

Then we have that $x^2 + y^2$, $(x-1)^2 + y^2$ and $(x-\sqrt{2})^2 + y^2$ are all squares of rational numbers.

The difference of the first and second implies $x$ is rational.

The difference of the second and third implies that $x = 0$.

Thus $y$ is rational.

Thus we have that for some integers $a,b,p,q$, $a \neq 0$, $b \neq 0$ that

(1) $a^2 + b^2 = p^2$

and

(2) $a^2 + 2b^2 = q^2$

Square (1) and multiply (2) by $a^2$ and subtract.

We get

$b^4 = p^4 - (aq)^2$.

It is well known that the equation $x^4 + y^2 = z^4$ has no non-trivial solutions (and in fact can be used to show that Fermat's Last theorem is true for $n=4$).

See here for instance: Link

Answer 2

I decided to give this problem a go, but I couldn't get a complete solution. Lets look at the distances squared:

1. $x_1^2+y_1^2$
2. $(x_1-1)^2+y_1^2$
3. $(x_1 - \sqrt{2})^2+y_1^2$

These must all be rational. The difference between any two rational numbers must be rational, so $-2x_1+1$ is rational and so is $x_1$. Subtracting 2. and 3., we get: $(-2 \sqrt(2)-2)x_1+3$, implying that $x_1$ must be 0 if it is rational.

This then gives us:

$y_1^2, y_1^2+1, y_1^2+2$

Suppose $y_1^2=a^2/b^2$ where a and b are integers. Clearly, $y_1^2+1, y_1^2+2$ are rational if and only if $a^2+b^2$ and $a^2+2*b^2$ are perfect squares. Using modular arithmetic it is pretty clear that b needs to be divisible by 2 (squares are only 0 or 1 mod 4), implying $b^2$ is divisible by 4.

Answer 3

Suppose that there exists a point A that is left uncolored after feeding in the three points (0,0), (1,0), and $(\sqrt{2},0)$. The distances from point A to each of these three points (call these b, c, and d, respectively) must be rational numbers.

Apply Stewart's Theorem: $$b^2(\sqrt{2}-1)+c^2\cdot 1=\sqrt{2}(d^2+(\sqrt{2}-1)\cdot 1).$$ So $$\sqrt{2}(b^2-d^2+1)=b^2-c^2+2$$ or $$\sqrt{2}=\frac{b^2-c^2+2}{b^2-d^2+1}.$$ Since b, c, and d are rational numbers, the right side is rational, but the left side is irrational, so there is no such point A. Thus, to color the entire plane black, it is sufficient to feed in the three points (0,0), (1,0), and $(\sqrt{2},0)$.

Answer 4

Each proof thus far is computational, some relying heavily on number theory. The top-rated answer has a noted flaw. Below, I've reproduced a proof from Halmos' "Problems for Mathematicians, Young and Old" (problem 4k):

It's easy to see that two points will not suffice: take a point on the perpendicular bisector of the first two points with irrational distance from both. To show that three points are sufficient, we note that each of the first two points leaves unpainted countably many circles of points (those with rational distance from the center). Thus, after two applications, we are left with countably many points, corresponding to intersection points of countably many circles. Take an arbitrary line in $\mathbb{R}^2$. It will intersect the remaining points in a countable set. Take a point on the arbitrary line, not one of the countably many points. Center our painting device here; then it is (by definition) an irrational distance from each remaining point.

The upshot of this approach: full generality to higher dimensions.