March 2014
<<February March April>>
We decided to present Jan Fricke's solution (thanks, Jan)
Lemma 1. Toggling a single lamp is possible, if and only if N and M are coprime, and M is odd.
Proof. Let N and M be coprime, and M be odd. Then there exists positive integers a and b such that aM - bN = 1. Since also (a + N)M - (b +M)N = 1, we can assume b is even. Now we can toggle a single lamp L in the following way: Use the tool for the lamps L, . . . ,L+M-1, for L+M, . . . ,L+2M-1, and so on until L+(a-1)M, . . . ,L+aM-1. After that the lamp L is switched (b + 1) times, all others are switched b times.
Let N and M have a common prime factor p. Consider the p circles“ each consisting by taking every p-th lamp. Since also M is divisible by p, any application of the tool switches the same amount of lamps in any of the p circles. So it is impossible to switch a single lamp.
Let M be even. For toggling exactly one lamp, this lamp has to be switched odd times, and any other even times. So the overall number of switchings has to be odd, which is impossible for even M.
Since we have to solve an equation system of N linear equations in N variables over F2, the possibility of solvability is equal to the possibility being in the image of the corresponding linear map. The dimension of the image can be estimated as follows:
Lemma 2. Let g be the greatest common divisor of M and N. Then the dimension of the coimage is at least g - 1.
Proof. Split the N variants to use the tool in g parts: part x consists of the applications starting at lamp x, x + M, x + 2M, and so on.
Applying all variants of a part always gives the same result, so even if we do not use the tool on the starting lamps 2, 3, . . . , g, we can reach the same set of configurations. As a result, the coimage has at least the dimension g - 1.
So, if a number N fulfills the following:
- The sum of the digits of N is less than 10.
- N and 105 are coprime.
- 32 | N - 1.
then N has the desired properties. The numbers less than 10, 000 with these properties are
1121, 1313, 1601, 2113, 3041, and 4001.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com