S2T2

Jim Randell 4:38 pm on 6 November 2020 Permalink Reply
Tags: by: Susan Bricket ( 14 )   

• 

  Jim Randell 5:47 pm on 6 November 2020 Permalink | Reply

  (See also: Puzzle #51, Enigma 1137, Enigma 1127).

  I think there are multiple solutions to this puzzle. Although if no floor is allowed to have the same configuration of circuits as another floor, then I think we can find a unique solution:

  If each light is connected to two other lights, then they must form a circular arrangement (like the candles in Puzzle #51).

  In a circuit where the number of lights is a multiple of 3, the lights can be toggled by switching the central light in each non-overlapping consecutive group of three. Otherwise the lights can be toggled by operating each switch once. Each light is toggled 3 times, so ends up in the opposite state.

  Only in those circuits where the number of lights is not a multiple of 3 can a single light be illuminated. And if one single light can be illuminated, then all the others in that circuit can also be illuminated singly.

  This Python program finds decompositions of 14 into 2 or more different circular circuits; finds those sets that require 30 switches to be operated to toggle every light; and also one of the sets must be composed entirely of circuits that do not consist of a multiple of 3 lights.

  It runs in 49ms.

  Run: [ @repl.it ]

  from enigma import irange, subsets, flatten, printf
  
  # decompose t into increasing numbers
  def decompose(t, m=3, ns=[]):
    if t == 0:
      if len(ns) > 1:
        yield ns
    else:
      for n in irange(m, t):
        yield from decompose(t - n, n + 1, ns + [n])
  
  # number of switches required for circuit with k lights
  def count(k):
    (n, r) = divmod(k, 3)
    return (n if r == 0 else k)
  
  # find 3 splits of 14
  for ss in subsets(decompose(14), size=3, select="C"):
    # sum the number of switches required
    ks = flatten(ss)
    t = sum(count(k) for k in ks)
    if t != 30: continue
    # and one floor must not contain a multiple of 3
    if all(any(k % 3 == 0 for k in s) for s in ss): continue
    # output solution
    a = len(ks)
    b = max(ks)
    printf("{a} circuits; longest = {b}; {ss}")
  

  Solution: (a) There are 7 circuits; (b) There are 10 lights in the longest circuit.

  The three configurations are: (3, 5, 6), (4, 10), (5, 9).

  The (4, 10) configuration requires switches to be operated 14 times to toggle the state of all lights, and in each circuit it is possible to illuminate the lights individually.

  The (3, 5, 6) and (5, 9) configurations, both require switches to be operated 8 times to toggle the state of all lights, and it is not possible to illuminate single lights in the 3, 6 or 9 circuits.

  If we are allowed to use the same configuration of circuits on 2 different floors, then there are two further solutions:

  (3, 5, 6), (3, 5, 6), (4, 10)
  (5, 9), (5, 9), (4, 10)

  The other solutions can be found by changing the select parameter at line 18 to [[ select="R" ]].

  The number of lights in the longest circuit is the same for all solutions. But the total number of circuits differs in each case.

  LikeLike

• 

  Frits 12:44 pm on 8 November 2020 Permalink | Reply

  @Jim,

  “and on one floor she was able turn each light on by itself” and line 24.

  I don’t see this as “on at least one floor”.

  LikeLike

  • 

    Jim Randell 1:02 pm on 8 November 2020 Permalink | Reply

    @Frits: Unless the puzzle says “exactly one” (or “precisely one”, or “only one”, etc) I usually treat such statements as “at least one”. In this case “at least one” or “exactly one” will lead to the same solution(s).

    LikeLike