Sunday Times Teaser 3134 – Stringing Along

by BRG on October 14, 2022

by Peter Good

Published Sunday October 16 2022 (link)

An artist hammered thin nails from a pack of 40 into a board to form the perimeter of a rectangle with a 1cm gap between adjacent nails. He created a work of art by stringing a long piece of wire from one nail to another, such that no section of wire was parallel to an edge of the rectangle. The wire started and ended at two different nails, no nail was used more than once and the length of the wire was a whole number of cm. No longer wire was possible that satisfied the above conditions.

What were the dimensions of the rectangle and the length of the wire chain (in cm)?

Note: the original (later corrected) on-line version omitted the red text.

From → Uncategorized

One Comment Leave one →

Brian Gladman permalink

I assumed that the wire length was an exact integer and that only some of the 40 pins are used.


from itertools import chain
from math import isqrt

# set to True to solve with the original (faulty) wording
faulty  = False

# generate possible wire paths given the set of pin
# coordinates in <pins> and the rectangle size in <w> 
# and <h>, returning the wire length and the pins used
def wire(pins, w, h, wlen=0, pseq=[]):
  # return all sequences of 3 or more connected pins
  if len(pseq) >= 3:
    yield wlen, pseq  
  # place next pin
  xx, yy = pseq[-1]
  for p in pins:
    x, y = p
    dx, dy = x - xx, y - yy
    # the wire cannot be parallel to an edge 
    if faulty:
      if dx == 0 and x in {0, w} or dy == 0 and y in {0, h}:
        continue
    elif dx == 0 or dy == 0:
      continue
    # only allow integer wire lengths between pins
    ln2 = dx ** 2 + dy ** 2
    ln = isqrt(ln2)
    if ln * ln == ln2:
      yield from wire(pins - {p}, w, h, wlen + ln, pseq + [p])

wl_max, sol_max = 0, []
# the horizontal width 
for w in range (3, 11):
  # the vertical height (not less than width)
  for h in range(w, 18):
    # create the set of (x, y) coordinates for the pins
    pins = ( set((x, 0) for x in range(w + 1)) |
             set((x, h) for x in range(w + 1)) |
             set((0, y) for y in range(1, h))  |
             set((w, y) for y in range(1, h)) )
    if len(pins) <= 40:
      
      # consider the first pin on the top and left edges (avoiding
      # solutions refected in x and y)
      for fp in chain((p for p in pins if p[1] == 0 and 2 * p[0] <= w), 
                      (p for p in pins if p[0] == 0 and 2 * p[1] <= h)):
          
        # look for a maximum possible wire length
        for wl, pused in wire(pins.difference([fp]), w, h, 0, [fp]):
          if wl >= wl_max:
            if wl > wl_max:
              sol_max.clear()
              wl_max = wl
            sol_max.append((w, h, len(pins), len(pused), pused))

for w, h, np, npu, pused in sol_max:
  print(f"Length = {wl_max}, rectangle = {w} x {h}, "
        f"{npu} of {np}, pins used at (x, y):\n  {pused}")

from itertools import chain

from math import isqrt

# set to True to solve with the original (faulty) wording

faulty = False

# generate possible wire paths given the set of pin

# coordinates in <pins> and the rectangle size in <w>

# and <h>, returning the wire length and the pins used

def wire(pins, w, h, wlen=0, pseq=[]):

# return all sequences of 3 or more connected pins

if len(pseq) >= 3:

yield wlen, pseq

# place next pin

xx, yy = pseq[-1]

for p in pins:

x, y = p

dx, dy = x - xx, y - yy

# the wire cannot be parallel to an edge

if faulty:

if dx == 0 and x in {0, w} or dy == 0 and y in {0, h}:

continue

elif dx == 0 or dy == 0:

continue

# only allow integer wire lengths between pins

ln2 = dx ** 2 + dy ** 2

ln = isqrt(ln2)

if ln * ln == ln2:

yield from wire(pins - {p}, w, h, wlen + ln, pseq + [p])

wl_max, sol_max = 0, []

# the horizontal width

for w in range (3, 11):

# the vertical height (not less than width)

for h in range(w, 18):

# create the set of (x, y) coordinates for the pins

pins = ( set((x, 0) for x in range(w + 1)) |

set((x, h) for x in range(w + 1)) |

set((0, y) for y in range(1, h)) |

set((w, y) for y in range(1, h)) )

if len(pins) <= 40:

# consider the first pin on the top and left edges (avoiding

# solutions refected in x and y)

for fp in chain((p for p in pins if p[1] == 0 and 2 * p[0] <= w),

(p for p in pins if p[0] == 0 and 2 * p[1] <= h)):

# look for a maximum possible wire length

for wl, pused in wire(pins.difference([fp]), w, h, 0, [fp]):

if wl >= wl_max:

if wl > wl_max:

sol_max.clear()

wl_max = wl

sol_max.append((w, h, len(pins), len(pused), pused))

for w, h, np, npu, pused in sol_max:

print(f"Length = {wl_max}, rectangle = {w} x {h}, "

f"{npu} of {np}, pins used at (x, y):\n {pused}")

Here is a picture of the solution:

Sunday Times Teaser 3134 – Stringing Along

by Peter Good

Published Sunday October 16 2022 (link)

Leave a comment to Brian Gladman Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta