DE-MO 2005 Problem 3

Let s be a positive real.

Consider a two-dimensional Cartesian coordinate system. A lattice point is defined as a point whose coordinates in this system are both integers. At each lattice point of our coordinate system, there is a lamp.

Initially, only the lamp in the origin of the Cartesian coordinate system is turned on; all other lamps are turned off. Each minute, we additionally turn on every lamp L for which there exists another lamp M such that

• the lamp M is already turned on, and
• the distance between the lamps L and M equals s.

Prove that each lamp will be turned on after some time ...

(a) ... if s = 13. [This was the problem for class 11.] (b) ... if s = 2005. [This was the problem for classes 12/13.] (c) ... if s is an integer of the form $s=p_1p_2...p_k$ if $p_1$ , $p_2$ , ..., $p_k$ are different primes which are all $\equiv 1\mod 4$ . [This is my extension of the problem, generalizing both parts (a) and (b).] (d) ... if s is an integer whose prime factors are all $\equiv 1\mod 4$ . [This is ZetaX's extension of the problem, and it is stronger than (c).]

Darij