Teaser 3134: Stringing along [revised]
From The Sunday Times, 16th October 2022 [link] [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 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)?
This is a revised version of the puzzle posted as Teaser 3134. The underlined text has been changed from the previously published version on The Sunday Times website.
This is the version of the puzzle that appeared in the printed newspaper.
[teaser3134]
Hugh Casement are discussing. 
S2T2 
Jim Randell 4:01 pm on 15 October 2022 Permalink |
Having solved the (more general) previously published version of this puzzle [link], it is a simple case of adapting my program to account for the additional condition.
For this version 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), and no linear section of wire is parallel to the edges of the rectangle.
You can think of the wire being available in various stiff lengths with looped ends, but these individual links can only ever fit between nails that are a whole number of centimetres apart. We wish to make a chain of these wire links, where each link goes from the end of the previous link to a currently unoccupied nail. What is the longest possible chain that can be made, on a rectangle whose perimeter is constructed from no more than 40 nails spaced 1 cm apart, where each link must cross the interior of the rectangle not parallel to the edges of the rectangle, and the start and end of the complete chain are on different nails.
This Python program runs in 104ms.
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 or dy == 0: 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 102 cm.
Here is a diagram of the maximal length layout:
LikeLike
Jim Randell 11:28 am on 28 October 2022 Permalink |
In my program above, in order to get a total distance that is a whole number we require the individual segments between consecutive pins in the stringing to be a whole number.
This is a reasonable assumption. As we can show that if we have a collection of positive integers, and at least one of them has a square root that is irrational, then the sum of the square roots of the entire collection is irrational. (See below [*]).
However, this does not mean we cannot construct stringings that are very close to an integer value using segments that are not themselves integers. And this lets us find solutions that are much longer than the published solution.
For example here is a stringing on the 12cm × 8 cm grid that has a total length of 440.999925 cm (i.e. 750 nanometres short of 441 cm). It would be practically impossible to tell this apart from a 441 cm length of wire.
Note that in this construction every pin is visited.
If we want more accuracy we can get within 6nm of 438 cm.
[*] The core of the proof is:
Suppose x, y are integers, such that at least one of √x and √y are irrational.
Then (x − y) is also an integer, and:
If (√x + √y) is rational (= p), then:
But then:
Which is a contradiction, hence the sum (√x + √y) is irrational.
LikeLike
Hugh Casement 10:16 am on 16 October 2022 Permalink |
The change in wording makes quite a difference to the total length, at least with the solution I worked out.
The puzzle does not seem to be well thought out. That the nails are thin clearly means that we are to ignore their diameter (and the thickness of the wire). But with centimetres as the unit they are not nails at all but pins, and it’s fine fuse wire. Inches would have been somewhat less unrealistic.
I also feel that if the “artist” had allowed himself more nails, the resulting pattern could have been more interesting. For example, 12 occurs in the Pythagorean triangles (9, 12, 15) and (12, 16, 20) as well as (5, 12, 13), which would presumably give more scope. But the length + width of the rectangle must not exceed 20, so we are much restricted.
LikeLike
Jim Randell 12:03 pm on 17 October 2022 Permalink |
@Hugh: Yes for the original wording I found a maximal solution with 24 links. For this revised version there are only 10 links. The rectangle was the same in both cases.
LikeLike