### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,158)
- misc (2)
- project euler (2)
- puzzle (40)
- site news (44)
- tantalizer (42)
- teaser (3)

### Site Stats

- 177,972 hits

Advertisements

Programming Enigma Puzzles

9 December 2016

Posted by on **From New Scientist #2293, 2nd June 2001** [link]

There are 8 lights, A, B, C, D, E, F, G, H, in the junior dormitory and each one has its own switch. To save matron having to operate all 8 switches, 12 pairs of lights are connected. They are AB, AD, BC, BE, CF, CH, DF, DG, EF, EG, EH, GH.

Whenever a switch is operated it changes its own light, and each of the lights connected to it, from on to off or from off to on. When matron enters the dormitory at 9.00 pm, lights B, C, E and G are on and the other four lights are off. As an example, if she operates switch F then lights D and F come on and lights C and E go off. If she then operates switch E the lights E and H come on and lights B, F and G go off.

Question 1.Is it possible for matron to operate certain switches so that, when she has finished, all the lights are off? If it is possible, which switches should she operate?If it is not possible, which one of the four lights that were off at 9.00 pm should additionally have been on at 9.00 pm so that matron could have operated certain switches and finished with all the lights off?

The situation is similar in the senior dormitory except that there are 100 lights and 400 pairs of lights are connected and all the lights are on at 9.00 pm.

Question 2.Can we say for certain that matron can find a selection of switches to operate so that when she has finished all the lights are off?

[enigma1137]

Advertisements

%d bloggers like this:

The first part of the puzzle can be solved programatically.

This Python program considers all possible subsets of the switches, and looks for situations were all lights are off, or only one light is left on.

Solution:(Question 1) It is not possible for matron to switch all the lights off. However, if light D had additionally been on at the start matron could have switched all the lights off.So, if lights B, C, D, E, G were on at the start, then switching either A, D, F (or A, B, C, F, G) would have turned all the lights off.

The second part is trickier. In fact I don’t think we’ve had a puzzle requiring a mathematical proof since

Enigma 1248(also set by Keith Austin).For each possible arrangement of 100 lights and switches there are potentially 2^100 (≈ 1.27 × 10^30) subsets of the switches that we could consider, and we would have to check these for each possible arrangement of 100 lights with 400 extra connections.

Fortunately we can show that for

anycollection of lights and switches, there will always be a set of switches that will turn off all the lights (providing they are all on to begin with).The proof is as follows:

We first prove the following lemma:

Lemma:In any odd set of connected lights there is a switch that operates an odd number of lightsBy “odd set” we mean a set of connected lights and switches, (where each switch operates the corresponding light and those it is directly connected to), that has an odd number of lights (and switches, as each switch corresponds to a light).

If we represent the collection of lights (and switches) as a graph, where each node represents both a light and a switch, and the switch at each node changes the state of the light at the node itself and the lights at all its immediate neighbours. Then the number of lights operated by the switch at each node is 1 more than the degree (number of edges associated with) that node.

The Handshaking Lemma [ https://en.wikipedia.org/wiki/Handshaking_lemma ] tells us that every undirected graph has an even number of nodes of odd degree. So if the graph representing the collection of lights has an odd number of nodes, then an even number of those nodes have odd degree, and so there must be an odd number of nodes with even degree. Hence there is at least 1 even node, and this completes the proof.

We now prove the main theorem by induction on the number of lights/switches in the set:

Theorem:For any set of lights and corresponding set of switches, such that each switch operates its own light and those of its connected neighbours, if we start with all lights on, then it is always possible to find a subset of switches which when operated will leave all the lights off.Suppose a collection of

nconnected lights that are initially lit can all be turned off by some subset of the switches.For

n = 1we can easily achieve this. There is only one light and one switch, and the switch operates the light.So, consider a set of

(n + 1)lights.We cover up one of the lights (and the corresponding switch). This leaves us with a collection of

nconnected lights. Which we know can all be turned off by using a subset of the remainingnswitches available. So we can switch those switches, and all the remainingnlights will be off. We then reveal the covered light. If it is off, we are done.If it is still on, we note this “special” subset of switches that turns of all the lights except the particular one we are interested in.

We reset all the lights to being on and cover a different light, then try the same trick. Eventually we might find a light that goes off with the rest, and we are done.

However, if every light we cover remains on when we try this trick, then we have a special set of switches for every light that will turn off all the other lights while leaving the particular light we are interested in lit.

If there are an even number of lights in the set of

(n + 1)lights (i.e.nis odd), then we can operate the special set of switches for each of the(n + 1)lights, one after another (operating switches multiple times if necessary). The state of every light will be changed exactlyntimes (by every special set of switchesexceptthe set that leaves that particular light’s state unchanged). Asnis odd, if we started with all lights on then all lights will now be off, and we have achieved our goal. (And we can determine the switches we need to operate by selecting those that are only operated an odd number of times during the entire sequence).If there are an odd number of lights in the set of

(n + 1)lights (i.e.nis even), then, using the lemma above, we know that there is (at least) one switch that will operate an odd number of the lights. So we find such a switch and operate it. It turns off an odd number of lights, leaving an even number of lights lit. We identify the lights that remain lit as setX. For each light inXwe operate the special sequence of switches that changes the state of all other lights, while leaving the particular light were are interested in unchanged. All the lights in setXhave their state changed an odd number of times (the state is changed once for every element ofXapart from the one element that leaves that particular light alone), and as they were all originally on they are now all off. And all the lights that arenotin setXhave their state changed an even number of times (once for every element ofX). They were initially off, and so they too are also all off. So we end up with all the lights being off.This covers both cases in the inductive step, and so the entire theorem is proved.

So, in reference to part 2 of the problem, it doesn’t matter how many lights there are, or how many extra connections between them it will always be possible to find a set of switches that will extinguish all the lights.

Solution:(Question 2): We can say for certain that there is a set of switches which will extinguish all the lights.This problem is known as the

Lamp Lighting ProblemorAll-Ones Problem.In the case of the set of lights given in Question 1, we could turn them all off (from being all on) by switching B, F, H (or C, D, F, G, H).

Given that

Question 2requires a Yes/No answer it would probably have been easier just to submit solutions with both answers.We can prove the lemma directly:

Suppose we start with an odd number of lights, all connected to their own switches.

Each switch operates a single light, so every switch operates an odd number of lights (and there are an odd number of switches that operate an odd number of lights).

We will talk about a light whose switch operates an odd number of lights as an “odd light” and a light whose switch operates an even number of lights as an “even light”.

If we then start adding connections between the lights, there are three options:

(1) We connect two odd lights. They both become even lights, so the total number of odd lights decreases by 2.

(2) We connect two even lights. They both become odd lights, so the total number of odd lights increases by 2.

(3) We connect an odd light and an even light. The odd light becomes an even light and the even light becomes an odd light. Overall the number of odd lights remains unchanged.

As we see, each time we add a connection the total number of odd lights changes by an even number (+2, 0, or −2). As we start with an odd number of odd lights there must always be an odd number of odd lights whatever additional connections we make, and so there is always as least one odd light.

This proves the lemma.

And here is a program that uses the method of the proof to construct a solution for

Nlights with a randomly selected additionalMconnections:The algorithm isn’t efficient enough to produce a solution for

N=100, M=400in a reasonable amount of time, so the default isN=20, M=60, which takes a few seconds, although these parameters can be specified on the command line if you want to try different numbers.The program applies the algorithm from the proof to construct a sequence that extinguishes all the lights, and then verified that it does indeed do this.

Interestingly I see the program fail when running under PyPy 5.6.0, although adding:

at line 78 seems to fix this.

Here’s a Python program that generates a random set of connections for a set of

Nlights withMadditional connections, and then usesMiniZincto find a set of switches that turns off all the lights.It can solve

N = 40, M = 160in a few seconds (and I’ve run it withN = 70, M=280in about 20 minutes).I used the

minizinc.pywrapper for MiniZinc that I wrote forEnigma 361, which lets me create the model using Python and returns the results to Python for output.I submitted the issue I found as a bug to the PyPy team (issue #2528), and the 5.8.0 release of PyPy includes a fix that sorts out this problem.