Ponder This Challenge - March 2014 - Toggling lamps

Ponder This Challenge:

N lamps are set in a circle, and for each integer M you have a tool that can toggle the state (on/off) of any set of M consecutive lamps.

Find a possible N which satisfies the following statements:

• The sum of its digits is less than 10.
• By applying the tool for M=105 several times, we can toggle a single lamp.
• If we remove one lamp and start from a random initial setting for the remaining N-1 lamps, the probability that there exists a way to apply the tool for M=32 several times and switch all the lamps off is positive and less than 0.0011%.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  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.

Solvers

• Dan Dima (02/28/2014 02:19 PM EDT)
• Antoine Comeau (02/28/2014 05:22 PM EDT)
• Radu-Alexandru Todor (02/28/2014 08:21 PM EDT)
• Oleg Vlasii (02/28/2014 11:00 PM EDT)
• Alexandre Gilotte (03/01/2014 12:13 PM EDT)
• Alan Murray (03/01/2014 02:31 PM EDT)
• Florian Fischer (03/01/2014 04:40 PM EDT)
• Motty Porat (03/01/2014 05:21 PM EDT)
• Lorenz Reichel (03/02/2014 11:10 AM EDT)
• Jan Fricke (03/02/2014 12:31 PM EDT)
• Olivier Mercier (03/02/2014 06:30 PM EDT)
• Cynthia Beauchemin (03/03/2014 01:20 AM EDT)
• Misha Lavrov (03/03/2014 09:33 AM EDT)
• Joe Clark (03/03/2014 04:46 PM EDT)
• Liubing Yu (03/03/2014 08:11 PM EDT)
• David Friedman (03/04/2014 12:10 PM EDT)
• Reiner Martin (03/04/2014 01:17 PM EDT)
• Armin Krauss (03/04/2014 04:17 PM EDT)
• Gilles-Philippe Paillé (03/04/2014 06:59 PM EDT)
• Peter Gerritson (03/04/2014 07:42 PM EDT)
• Joseph DeVincentis (03/05/2014 11:13 AM EDT)
• Don Dodson & David Dodson (03/05/2014 02:22 PM EDT)
• Xing Hu (03/07/2014 06:56 PM EDT)
• Aharon Malachi (03/08/2014 08:18 AM EDT)
• Mathias Schenker (03/08/2014 01:44 PM EDT)
• Michael D. Schuresko (03/09/2014 06:13 PM EDT)
• Álvaro Begué (03/10/2014 04:12 PM EDT)
• Raj Kumar Pa (03/10/2014 05:39 PM EDT)
• l (03/10/2014 05:39 PM EDT)
• Uoti Urpala (03/11/2014 09:44 PM EDT)
• John Tromp (03/12/2014 12:05 PM EDT)
• Alex Fleischer (03/12/2014 02:05 AM EDT)
• Gale Greenlee (03/15/2014 08:51 AM EDT)
• Andrea Andenna (03/14/2014 02:52 PM EDT)
• Markus Boettle (03/18/2014 10:05 AM EDT)
• Chuck Carroll (03/18/2014 05:47 PM EDT)
• Stefan Rüdrich (03/19/2014 09:47 AM EDT)
• Todd Will (03/19/2014 01:07 PM EDT)
• Daniel Bitin (03/19/2014 04:16 PM EDT)
• Seung Hwan (Sonny) (03/22/2014 09:16 AM EDT)
• Philipp Seemann (03/23/2014 10:30 AM EDT)
• Yewoon Choi (03/23/2014 10:40 AM EDT)
• Michael Rosola (03/23/2014 10:53 AM EDT)
• David Greer (03/23/2014 03:28 PM EDT)
• Abhinav Kumar (03/24/2014 09:50 PM EDT)
• Karthik Eswara (03/26/2014 12:53 AM EDT)
• Stéphane Higueret (03/28/2014 01:34 PM EDT)
• William Heller (03/29/2014 06:47 AM EDT)
• Cindy Ji Won Lim (03/29/2014 10:45 AM EDT)
• Jaesung Son (03/29/2014 06:56 PM EDT)
• William Kang (03/29/2014 09:40 PM EDT)
• Ehud Schreiber (03/30/2014 06:18 AM EDT)
• David Yang (03/30/2014 10:27 AM EDT)
• Hong Seongwoo (03/30/2014 08:47 AM EDT)
• Daniel Nam (03/30/2014 08:51 PM EDT)
• Peter Shim (03/30/2014 10:38 PM EDT)
• Clive Tong (03/31/2014 01:51 AM EDT)