Teaser 3134: Stringing along
From The Sunday Times, 16th October 2022 [link]
An artist hammered thin nails from a pack of 40 into a board to form the perimeter of a rectangle with a 1 cm gap between adjacent nails. He created a work of art by stringing a long piece of wire from one nail to another, such that consecutive nails were on different edges 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)?
The wording of this puzzle was later revised. The underlined section was changed to a more restrictive condition.
See: Teaser 3134: Stringing along [revised] for the revised puzzle.
[teaser3134]
Brian Gladman are discussing. 
S2T2 
Jim Randell 5:07 pm on 14 October 2022 Permalink |
(Note: It seems that my initial interpretation of the puzzle may not be the intended one. See below for a more likely interpretation).
It seems we would need to know the dimensions of the rectangle before we determined the maximum length of wire. I considered all rectangles that can be constructed using 40 nails, and found the maximum possible length of wire that touches each edge of the rectangle no more than once.
This Python program tries all possible rectangles, and all possible stringings.
It runs in 275ms.
Run: [ @replit ]
from enigma import (irange, inf, subsets, tuples, hypot, intr, Accumulator, printf) # generate possible <x> by <y> rectangles, using <n> nails def generate(n): for y in irange(3, inf): x = (n - 2 * y) // 2 if x < 3: break yield (x, y) # calculate length of wire required between points <vs> def dist(vs): d = 0 for ((x1, y1), (x2, y2)) in tuples(vs, 2): d += hypot(x2 - x1, y2 - y1) if abs(d - intr(d)) < 1e-6: return d # collect maximal stringings r = Accumulator(fn=max, collect=1) # consider possible rectangles for (x, y) in generate(40): # choose top, bottom nails for (x1, x2) in subsets(irange(1, x - 1), size=2, select="R"): (T, B) = ((x1, y), (x2, 0)) # choose left, right nails for (y1, y2) in subsets(irange(1, y - 1), size=2, select="P"): (L, R) = ((0, y1), (x, y2)) # calculate possible lengths for vs in [(T, R, B, L), (T, R, L, B), (T, B, R, L)]: d = dist(vs) if d is None: continue printf("[({x}, {y}) {d:g} = {vs}]") r.accumulate_data(d, (x, y, vs)) printf("max wire length = {r.value:g} cm") for (x, y, vs) in r.data: printf("-> {x} cm by {y} cm grid {vs}")Solution: The rectangle was 6 cm × 14 cm, and the wire was 37 cm long.
This program finds what I assume is the required answer (where each section of the wire is an integer length). But by changing the tolerance at line 15 we can find a longer wire that is sufficiently close to an exact whole number of centimetres that it would be physically impossible to determine that it wasn’t.
So we can create a stringing on a 6 cm × 14 cm rectangle that uses 40.0007 cm of wire.
And also a stringing on a 4 cm × 16 cm rectangle that uses 44.99 cm of wire.
LikeLike
Jim Randell 11:19 pm on 14 October 2022 Permalink |
Using a different (and more likely) interpretation of the problem (see below), where each edge of the rectangle may be visited many times (and allowing the corner nails to be used), but each linear section of wire is a whole number of centimetres, we can get a much longer wire.
To be clear: I am assuming we want to find the maximum achievable total length of wire between the nails that can be made using a rectangle constructed from up to 40 nails, with the wire strung between nails where no nail is used more than once and consecutive nails are on different edges of the rectangle (i.e. each linear section of wire must cross part of the interior of the rectangle, and be a whole number of centimetres long).
Here is a quick program to explore that (although there may be some duplication in the patterns found).
It runs in 942ms.
Run: [ @replit ]
from enigma import (irange, ihypot, chain, Accumulator, printf) # generate possible <x> by <y> rectangles, using (up to) <n> nails def generate(n): for y in irange(2, n // 4): for x in irange(2, (n - 2 * y) // 2): yield (x, y) # find paths by adding nails to <vs> def solve(x, y, nails, vs, d=0): # return the current path yield (d, vs) # choose the next nail (x1, y1) = vs[-1] for v in nails: (x2, y2) = v (dx, dy) = (x2 - x1, y2 - y1) if dx == 0 and (x1 == 0 or x1 == x): continue if dy == 0 and (y1 == 0 or y1 == y): continue dd = ihypot(dx, dy) if dd is not None: yield from solve(x, y, nails.difference([v]), vs + [v], d + dd) # collect maximal distance paths r = Accumulator(fn=max, collect=1) # consider possible rectangles for (x, y) in generate(40): # collect possible edge nails nails = set() for i in irange(0, x - 1): nails.update([(i, 0), (x - i, y)]) for i in irange(0, y - 1): nails.update([(0, y - i), (x, i)]) # start in the bottom/left quadrant botm = ((i, 0) for i in irange(0, x // 2)) left = ((0, i) for i in irange(1, y // 2)) for v in chain(botm, left): for (d, vs) in solve(x, y, nails.difference([v]), [v]): r.accumulate_data(d, (x, y, vs)) # output solution(s) printf("max wire length = {r.value} cm") for (x, y, vs) in r.data: printf("-> {x} cm by {y} cm grid {vs}")Solution: The rectangle was 12 cm × 8 cm. The total length of wire used was 258 cm.
Here is a diagram of one maximal length arrangement (there are several):
LikeLike
Brian Gladman 9:56 pm on 14 October 2022 Permalink |
The answer for this one depends on the assumptions being made. I found a different answer by assuming that the wire length was exact and that not all nails are used. I then looked for a number of Pythagorean triangle hypotenuses with a maximum sum (not necessarily alternating x, y edges).
LikeLike
Jim Randell 10:51 pm on 14 October 2022 Permalink |
@Brian: I was assuming that each edge of the rectangle was only used once (and the corners not at all). But the puzzle text only says consecutive nails are on different edges, so if we can visit edges more than once then we can use much more wire. (And get a more artful display into the bargain).
In this case I assumed distance between each consecutive pair of nails was an exact whole number of cm, so that the total length of the wire is as well.
(Although it still seems like we would need to know the size of the rectangle the artist had constructed before we could find the maximum length of wire he could use).
LikeLike