Irrational painting device

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)$.}

Solution 1:

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.

Solution 2:

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)$.