Enigmatic Code

Programming Enigma Puzzles

Enigma 1137: On, off, on, off

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

4 responses to “Enigma 1137: On, off, on, off

  1. Jim Randell 9 December 2016 at 9:03 am

    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.

    from collections import defaultdict
    from enigma import subsets, join, printf
    
    # labels for lights and switches
    labels = 'ABCDEFGH'
    
    # connections between lights
    connections = ( 'AB', 'AD', 'BC', 'BE', 'CF', 'CH', 'DF', 'DG', 'EF', 'EG', 'EH', 'GH' )
    
    # map of switch -> lights
    switch = defaultdict(set)
    
    # each switch operates it's own light
    for k in labels:
      switch[k].add(k)
    
    # if lights X and Y are connected then switch X also operates light Y
    # and switch Y also operates light X
    for (x, y) in connections:
      switch[x].add(y)
      switch[y].add(x)
    
    # operate a set of switches
    # return the lights that are on
    def operate(s, on, switch):
      d = defaultdict(int)
      # initially the lights in "on" are on
      for k in on:
        d[k] = 1
      # operate each switch
      for x in s:
        for k in switch[x]:
          d[k] ^= 1
      return sorted(k for (k, v) in d.items() if v)
    
    # lights that are initially on
    on = 'BCEG'
    
    # consider possible subsets of switches
    for s in subsets(labels):
      r = operate(s, on, switch)
      if len(r) == 0:
        printf("(1a) on = {on}, switch {s} -> all off", s=join(s))
      elif len(r) == 1 and r[0] not in on:
        printf("(1b) on = {on} + {r[0]}, switch {s} -> all off", s=join(s))
    

    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 any collection 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 lights

    By “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 n connected lights that are initially lit can all be turned off by some subset of the switches.

    For n = 1 we 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 n connected lights. Which we know can all be turned off by using a subset of the remaining n switches available. So we can switch those switches, and all the remaining n lights 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. n is 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 exactly n times (by every special set of switches except the set that leaves that particular light’s state unchanged). As n is 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. n is 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 set X. For each light in X we 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 set X have their state changed an odd number of times (the state is changed once for every element of X apart 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 are not in set X have their state changed an even number of times (once for every element of X). 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 Problem or All-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 2 requires a Yes/No answer it would probably have been easier just to submit solutions with both answers.

  2. Jim Randell 11 December 2016 at 9:36 am

    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 N lights with a randomly selected additional M connections:

    # increase the default recursion limit
    import sys
    sys.setrecursionlimit(1000000)
    
    from collections import defaultdict, Counter
    from enigma import C, irange, flatten, cached, arg, printf
    
    # apply a set of switches
    def switch(switches, on, lights):
      d = dict((x, x in on) for x in lights)
      for s in switches:
        for x in connected[s]:
          if x in lights: d[x] ^= 1
      return tuple(sorted(k for (k, v) in d.items() if v))
    
    # return the elements of s that appear an odd number of tumes
    def dedup(s):
      return tuple(sorted(x for (x, n) in Counter(s).items() if n % 2 == 1))
    
    import random
    
    # N = number of lights
    # M = number of additional connections
    N = arg(20, 0, int)
    M = arg(60, 1, int)
    assert not(M > C(N, 2))
    
    # there are N lights
    lights = tuple(irange(1, N))
    
    # and M additional pairs are connected
    groups = list()
    while len(groups) < M:
      a = random.choice(lights)
      b = random.choice(lights)
      if a == b: continue
      if b < a: (a, b) = (b, a)
      if (a, b) not in groups:
        groups.append((a, b))
    
    # construct the connection table
    connected = defaultdict(set)
    for x in lights:
      connected[x].add(x)
    for g in groups:
      for x in g:
        connected[x].update(g)
    
    # output the table
    printf("{N} lights, {M} connections")
    for k in lights:
      printf("{k} -> {v}", v=sorted(connected[k]))
    
    # find a set of switches that extinguish the specified lights
    @cached
    def solve(lights):
      # for 1 light, just operate the switch
      if len(lights) == 1:
        return lights
    
      # otherwise, consider each of the lights
      # and record sequences that turn of all the other lights
      r = dict()
      for (i, n) in enumerate(lights):
        s = solve(lights[:i] + lights[i + 1:])
        # apply the solution to the entire set
        x = switch(s, lights, lights)
        # has it turned off all the lights?
        if not x: return s
        # otherwise record the sequence
        r[lights[i]] = s
    
      # if we get this far none of the sequences turned off all the lights
    
      # if there are an even number of lights, just operate all the sequences
      if len(lights) % 2 == 0:
        return dedup(flatten(r.values()))
    
      # otherwise, find a switch that operates an odd number of lights
      for k in lights:
        vs = list(v for v in connected[k] if v in lights)
        if len(vs) % 2 == 0: continue
        return dedup([k] + flatten(r[x] for x in lights if x not in vs))
    
    
    # find a solution that turns all the lights off
    s = solve(lights)
    
    # verify the solution
    x = switch(s, lights, lights)
    if len(x) == 0:
      printf("switch {s} -> {x}")
    

    The algorithm isn’t efficient enough to produce a solution for N=100, M=400 in a reasonable amount of time, so the default is N=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:

    assert len(lights) % 2 == 1
    

    at line 78 seems to fix this.

    • Jim Randell 12 December 2016 at 10:23 pm

      Here’s a Python program that generates a random set of connections for a set of N lights with M additional connections, and then uses MiniZinc to find a set of switches that turns off all the lights.

      It can solve N = 40, M = 160 in a few seconds (and I’ve run it with N = 70, M=280 in about 20 minutes).

      from collections import defaultdict
      
      from enigma import arg, C, irange, sprintf, printf
      from minizinc import MiniZinc
      
      import random
      
      # N = number of lights
      # M = number of additional connections
      N = arg(20, 0, int)
      M = arg(60, 1, int)
      assert not(M > C(N, 2))
      
      # there are N lights
      lights = tuple(irange(1, N))
      
      # and M additional pairs are connected
      groups = list()
      while len(groups) < M:
        a = random.choice(lights)
        b = random.choice(lights)
        if a == b: continue
        if b < a: (a, b) = (b, a)
        if (a, b) not in groups:
          groups.append((a, b))
      
      # construct the connection table
      connected = defaultdict(set)
      for x in lights:
        connected[x].add(x)
      for g in groups:
        for x in g:
          connected[x].update(g)
      
      # output the table, and collect the rows of the connection matrix
      matrix = list()
      printf("{N} lights, {M} connections")
      for k in lights:
        v = connected[k]
        matrix.extend(int(i in v) for i in lights)
        printf("{k} -> {v}", v=sorted(v))
      
      
      # create the MiniZinc model
      m = MiniZinc(sprintf("""
      
      % the connection matrix
      array[1..{N}, 1..{N}] of 0..1: connected = array2d(1..{N}, 1..{N}, {matrix});
      
      % the switches to operate
      array[1..{N}] of var 0..1: switch;
      
      % operating the switches should operate each light an odd number of times
      constraint forall (i in 1..{N}) ((sum (s in 1..{N}) (switch[s] * connected[s, i])) mod 2 = 1);
      
      % solve it
      solve satisfy;
      
      """))
      
      # solve it (mzn-gecode seems to be the fastest solver)
      for s in m.solve(solver="mzn-gecode", results='switch'):
        switches = tuple(k for (k, v) in s['switch'].items() if v) 
        printf("switch = {switches}")
      

      I used the minizinc.py wrapper for MiniZinc that I wrote for Enigma 361, which lets me create the model using Python and returns the results to Python for output.

    • Jim Randell 13 June 2017 at 8:46 am

      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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: