Teaser 3270: Tunnel vision
From The Sunday Times, 25th May 2025 [link] [link]
Four ramblers came to a tunnel that they all had to travel through. The tunnel was too dangerous to travel through without a torch, and unfortunately they only had one torch. It was also too narrow to walk through more than two at a time. The maximum walking speed of each of the walkers was such that they could walk through the tunnel in an exact number of minutes, less than ten, which was different for each walker. When two walkers walked together, they would walk at the speed of the slower one.
They all managed to get through the tunnel and in the quickest possible time, this time being five sixths of the total of their individual crossing times.
In ascending order, what are their four four individual crossing times?
[teaser3270]
Frits are discussing. 
Ruud and 
Pete Good are discussing. 
S2T2 
Jim Randell 7:34 am on 25 May 2025 Permalink |
See also: Enigma 981, [@wikipedia].
This Python program runs in 63ms. (Internal runtime is 1.8ms).
from enigma import (Accumulator, irange, subsets, div, cache, printf) # find minimum total crossing times for individual times <ts> (all different) # where <xs> is the times of the participants on the far side @cache def _time(ts, xs): # 1 or 2 people take the max of the times if len(ts) < 3: return max(ts) # otherwise, find minimal time for 2 to cross (x, y) and 1 to return (z) r = Accumulator(fn=min) for xy in subsets(ts, size=2): for z in xs.union(xy): # minimise the remaining scenario t = _time(ts.difference(xy).union({z}), xs.union(xy).difference({z})) r.accumulate(max(xy) + z + t) return r.value time = lambda ts, xs=(): _time(frozenset(ts), frozenset(xs)) # choose 4 individual crossing times; all different and <10 minutes for ts in subsets(irange(1, 9), size=4): # target time is 5/6 the sum of the individual times t = div(5 * sum(ts), 6) if t is None or time(ts) != t: continue # output solution printf("{ts} -> {t}")Solution: The individual crossing times are: 1, 2, 7, 8 minutes.
The total of the individual crossing times is 18 minutes.
And the minimum crossing time is 15 minutes (15 = 18 × 5/6), for example:
LikeLike
Jim Randell 1:48 pm on 27 May 2025 Permalink |
I experimented further with this puzzle.
Here is a modified version of my program which will produce a minimal sequence of crossings, and is also modified to use [[
multiset]] instead of [[set]], which allows individual crossing times to be repeated:from enigma import (Accumulator, multiset, irange, subsets, div, printf) # find minimum total crossing times for individual times <ts> # where <xs> is the times of the participants on the far side def _time(ts, xs, ss): # 1 or 2 people take the max of the times if ts.size() < 3: return (ts.max(), ss + [list(ts.sorted())]) # otherwise, find minimal time for 2 to cross (x, y) and 1 to return (z) r = Accumulator(fn=min) for xy in ts.subsets(size=2): for z in xs.combine(xy): # minimise the remaining scenario (t, ss_) = _time(ts.difference(xy).add(z), xs.combine(xy).remove(z), ss + [list(xy.sorted()), [z]]) r.accumulate_data(xy.max() + z + t, ss_) return (r.value, r.data) time = lambda ts, xs=(): _time(multiset(ts), multiset(xs), list()) # choose 4 individual crossing times for ts in subsets(irange(1, 9), size=4, select='C'): # target time is 5/6 the sum of the individual times t = div(5 * sum(ts), 6) if t is None: continue (t_, ss) = time(ts) if t_ != t: continue # output solution printf("{ts} -> {t} {ss}")We find there are 2 further solutions if repeated individual crossing times are allowed.
And the program can also be used to find solutions for other variations of the puzzle, for example, where there are 5 participants, all with different crossing times less than 12.
[Solutions below.]
If repeated crossing times are allowed in the original puzzle (use [[
select='R'in line 19), the following scenarios are also solutions to the puzzle:And if we extend the puzzle to 5 participants (with different individual crossing times less than 12 minutes):
LikeLike
Frits 2:49 pm on 26 May 2025 Permalink |
Only using analysis for the multiple of 6.
from itertools import combinations # decompose the integer <t> into <k> increasing # numbers between mn and mx (inclusive) def decompose(t, k=4, mn=1, mx=9, vs=[]): if k == 1: if vs[-1] < t <= mx: yield set(vs + [t]) else: for n in range(mn, mx + 1): if 2 * k * n + k * (k - 1) > 2 * t: break yield from decompose(t - n, k - 1, n + 1, mx, vs + [n]) # get all four ramblers through the tunnel from a to b def solve(a, b=set(), e=0, ss=[], t=0): global quickest if len(a) == 2 and not e: # penultimate stage quickest = min(quickest, t + max(a)) else: if e: # we are at the end of the tunnel for c in combinations(b, 1): if (t_ := t + c[0]) < quickest: solve(a | set(c), b.difference(c), 0, ss + [c], t_) else: # we are at the start of the tunnel for c in combinations(a, 2): if (t_ := t + max(c)) < quickest: solve(a.difference(c), b | set(c), 1, ss + [c], t_) # total of their individual crossing times <ti> must be a multiple of 6 # to get to five sixths for ti in range(12, 31, 6): # choose times for the four ramblers (with sum <ti>) for t4 in decompose(ti): quickest = 999 # get the quickest possible time for these four times solve(t4) # five sixths? if 6 * quickest == 5 * ti: print(f"answer: {sorted(t4)}")or faster
from itertools import combinations, permutations from collections import defaultdict # assume a and e are walking back times (may have same value) # b, c, d and f must have different values # 1: (a, b) 2: a 3: (c, d) 4: e 5: (e, f) dct = defaultdict(lambda: 45) # default value 45 dgts = set(range(1, 10)) for c, d in combinations(range(1, 10), 2): for b, f in permutations(dgts - {c, d}, 2): # total of their individual crossing times must be # a multiple of 6 to get to five sixths if (b + c + d + f) % 6 == 0: # go for quickest possible time a, e = min(c, f), min(b, c) # store the quickest possible time t = max(a, b) + a + d + e + max(e, f) t4 = tuple(sorted([b, c, d, f])) dct[t4] = min(dct[t4], t) for k, v in dct.items(): # five sixths of the total of their individual crossing times if 5 * sum(k) == 6 * v: print(f"answer: {k}")LikeLike