Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
I think you are going to receive flak for this question because people favor questions the OP genuinely wants to know the answer to. This answer for instance could be found here: amc.maa.org/a-activities/a7-problems/putnamindex.shtml However I could be off-base and people could be cool with this. I guess we'll see :/ –  BBischof Aug 16 '10 at 1:39
1  
@BBischof: Well, at least it will help define the FAQ in that case. I am fine if you close this. I was under the impression there might be a minimum (quantity) requirement for questions/answers for the site to move out of Beta and become permanent. Also, the link you posted won't have the solution to Part b) I suppose. –  Aryabhata Aug 16 '10 at 1:44
    
@Moron Oh the irony! Four upvotes on my comment, yet no votes to close! I didn't even vote to close, yet instead left that comment! What a strange situation. I cannot in good faith vote to close until another person jumps the shark. –  BBischof Aug 16 '10 at 20:49
1  
@BBischof: I suppose it is because the guidelines are not very clear. Do you want to open a meta question to discuss this? Also, the part b) I have added to the problem and I don't think you will find it with the standard putnam exam solutions on the web. Perhaps that is another reason people are reluctant to close? –  Aryabhata Aug 16 '10 at 20:55
1  
BTW, I don't think there is a dearth of questions here. If anything, there are so many questions that one cannot look at every question in detail. –  ShreevatsaR Aug 16 '10 at 22:12
show 3 more comments

4 Answers 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.

share|improve this answer
    
Thanks. I was aware of this proof of part a). I was more interested in proofs for part b). +1 though. –  Aryabhata Nov 8 '11 at 2:43
add comment

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.

diagram

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

share|improve this answer
4  
This proof is incomplete. What if $b^2 - d^2 +1 = 0$? –  Aryabhata Aug 16 '10 at 14:23
add comment

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.

share|improve this answer
    
How about taking the difference of 2 and 3? –  Aryabhata Aug 16 '10 at 17:11
    
Good point. $(-2 \sqrt{2}-2)x_1+3$ needs to be rational as well. Since $x_1$ is irrational, that won't occur. –  Casebash Aug 16 '10 at 20:41
1  
Not so fast :-) What if x_1 = 0? –  Aryabhata Aug 16 '10 at 20:56
    
Hmm, then we need the roots of $y_1^2$, $y_1^2+1$, $y_1^2+2$. If we let $y_1^2=a^2/b^2$ where a,b are integers, then we need $a^2+b^2$ and $a^2+2*b^2$ to be perfect squares –  Casebash Aug 16 '10 at 21:19
add comment
up vote 0 down vote accepted

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: http://planetmath.org/encyclopedia/X4Y4z2HasNoSolutionsInPositiveIntegers.html

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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