Turning on lamps
Source: DeMO 2005, classes 11 and 12/13, 1st day, problem 3
May 9, 2005
analytic geometrynumber theoryrelatively primenumber theory proposed
Problem Statement
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 if , , ..., are different primes which are all . [This is my extension of the problem, generalizing both parts (a) and (b).]
(d) ... if s is an integer whose prime factors are all . [This is ZetaX's extension of the problem, and it is stronger than (c).]
Darij