Sunday Times Teaser 3033 – Goldilocks and the Bear Commune

by BRG on November 7, 2020

by Susan Bricket

Published Sunday November 08 2020 (link)

In the bears’ villa there are three floors, each with 14 rooms. The one switch in each room bizarrely toggles (on <—> off) not only the single light in the room but also precisely two other lights on the same floor; moreover, whenever A toggles B, then B toggles A.

As Goldilocks moved from room to room testing various combinations of switches, she discovered that on each floor there were at least two separate circuits and no two circuits on a floor had the same number of lights. Furthermore, she found a combination of 30 switches that turned all 42 lights from “off” to “on”, and on one floor she was able turn each light on by itself.

(a) How many circuits are there?

(b) How many lights are in the longest circuit?

From → Uncategorized

One Comment Leave one →

Brian Gladman permalink

This teaser appears to have a flaw since it produces three solutions. But if we require the configuration of the circuits on the three floors to all be different we then obtain a unique solution.


from itertools import chain, combinations

# rooms are linked in circular chains of length three or more with 
# each switch acting on its own room and the two adjacent rooms

# return the set of all subsets of the input sequence
def powerset(s):
  s = list(s)
  return chain.from_iterable(combinations(s, r) 
                        for r in range(len(s) + 1))

# return the sequence of items in the sub-sequences of a sequence
def flatten(seq):
  return list(x for y in seq for x in y)

# partition the integer <n> into two or more 
# different integers not less than <m>  
def partition(n, m, seq=()):
  if not n:
    if len(seq) > 1:    
      yield seq
  else:
    for i in range(m, n + 1):
      yield from partition(n - i, i + 1, seq + (i,))

# with all <n> lights starting off, find the minimum subsets of <n> 
# switches that leave <m> lights on after each switch is toggled once
def switch(n, m):
  sseq = []
  # consider all subsets of the <n> switches (0 .. n - 1)
  for ss in powerset(range(n)):
    # start with all <n> switches off
    sw = [0] * n
    # each switch toggles itself and the two adjacent switches
    for i in ss:
      sw[(i - 1) % n] ^= 1
      sw[i] ^= 1
      sw[(i + 1) % n] ^= 1
    # save the subset of switches if it leaves <m> lights on
    if sum(sw) == m:
      sseq.append(ss)
  # return the minimum subset of switches needed (or None if none)
  return sorted(sseq, key = lambda x:len(x))[0] if sseq else None

# list the possible groups of circuits for 14 room floors
fcts = tuple(x for x in partition(14, 3))
# list all circuits
cls = flatten(fcts)
# for each circuit starting with all lights off, save a minimum set of
# switches that leave one light on (c2s1) and all lights on (c2sa)
c2s1, c2sa = dict(), dict()
for c in cls:
  if sw := switch(c, 1):
    c2s1[c] = sw
  if sw := switch(c, c):
    c2sa[c] = sw

# select groups of circuits for three floors
for c3f in combinations(fcts, 3):
  # all the circuits on one floor can toggle one light
  if sum(all(c in c2s1 for c in cf) for cf in c3f) == 1:
    # collect all circuits and ... 
    cts = flatten(c3f)
    # ... the minimum number of switches needed to toggle all their lights
    sws = tuple(len(c2sa[s]) for s in cts)
    # find a set of circuits in all floors that require a
    # minimum of 30 switches to toggle all 42 lights
    if sum(sws) == 30:
      print(f"{len(cts)} circuits (max length {max(cts)}): {c3f}")

from itertools import chain, combinations

# rooms are linked in circular chains of length three or more with

# each switch acting on its own room and the two adjacent rooms

# return the set of all subsets of the input sequence

def powerset(s):

s = list(s)

return chain.from_iterable(combinations(s, r)

for r in range(len(s) + 1))

# return the sequence of items in the sub-sequences of a sequence

def flatten(seq):

return list(x for y in seq for x in y)

# partition the integer <n> into two or more

# different integers not less than <m>

def partition(n, m, seq=()):

if not n:

if len(seq) > 1:

yield seq

else:

for i in range(m, n + 1):

yield from partition(n - i, i + 1, seq + (i,))

# with all <n> lights starting off, find the minimum subsets of <n>

# switches that leave <m> lights on after each switch is toggled once

def switch(n, m):

sseq = []

# consider all subsets of the <n> switches (0 .. n - 1)

for ss in powerset(range(n)):

# start with all <n> switches off

sw = [0] * n

# each switch toggles itself and the two adjacent switches

for i in ss:

sw[(i - 1) % n] ^= 1

sw[i] ^= 1

sw[(i + 1) % n] ^= 1

# save the subset of switches if it leaves <m> lights on

if sum(sw) == m:

sseq.append(ss)

# return the minimum subset of switches needed (or None if none)

return sorted(sseq, key = lambda x:len(x))[0] if sseq else None

# list the possible groups of circuits for 14 room floors

fcts = tuple(x for x in partition(14, 3))

# list all circuits

cls = flatten(fcts)

# for each circuit starting with all lights off, save a minimum set of

# switches that leave one light on (c2s1) and all lights on (c2sa)

c2s1, c2sa = dict(), dict()

for c in cls:

if sw := switch(c, 1):

c2s1[c] = sw

if sw := switch(c, c):

c2sa[c] = sw

# select groups of circuits for three floors

for c3f in combinations(fcts, 3):

# all the circuits on one floor can toggle one light

if sum(all(c in c2s1 for c in cf) for cf in c3f) == 1:

# collect all circuits and ...

cts = flatten(c3f)

# ... the minimum number of switches needed to toggle all their lights

sws = tuple(len(c2sa[s]) for s in cts)

# find a set of circuits in all floors that require a

# minimum of 30 switches to toggle all 42 lights

if sum(sws) == 30:

print(f"{len(cts)} circuits (max length {max(cts)}): {c3f}")

Sunday Times Teaser 3033 – Goldilocks and the Bear Commune

by Susan Bricket

Published Sunday November 08 2020 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta