S2T2

Jim Randell 4:12 pm on 25 November 2022 Permalink Reply
Tags: by: Howard Williams ( 26 )   

• 

  Jim Randell 4:58 pm on 25 November 2022 Permalink | Reply

  (Curiously this week’s New Scientist back page puzzle is a simpler variation on the problem [link]).

  If the friends just walked from pub to the stadium it would take 2.32 hours.

  If the barman ferried each of them individually between the pub and the stadium it would take 3.29 hours.

  But we can do better.

  If the barman takes the first friend on his motorbike, and the rest of the friends start walking towards the stadium. Then the barman drops the first friend off to walk the remainder of the distance to the stadium and returns to the group (now a short distance from the pub) and ferries the next friend to join the first friend, and so on until he collects the final friend and drops him off at the stadium at the same time that all the other friends arrive, then we can achieve a minimum overall time.

  The only thing to work out is how far before the stadium to drop the first friend, then it is just a matter of ferrying friends from the trailing to the leading group.

  If each of the k friends walks a distance x at velocity w, and travels by motorbike a distance (d − x) at a velocity v, then each journey takes:

  t = x/w + (d − x)/v

  And the total time taken for the barman to ferry them all is:

  t = [(2k − 1)d − 2kx]/v

  Everyone arrives at the stadium at the same time, so:

  x/w + (d − x)/v = [(2k − 1)d − 2kx]/v
  vx + (d − x)w = [(2k − 1)d − 2kx]w
  vx + dw − xw = (2k − 1)dw − 2kxw
  x(v + w(2k − 1)) = dw(2k − 2)
  x = 2dw(k − 1) / (v + w(2k − 1))

  or:

  n = 2k − 1
  x = dw(n − 1) / (v + wn)
  t = d(w + vn) / v(v + wn)

  The answer can then be calculated directly.

  Run: [ @replit ]

  from enigma import (fdiv, printf)
  
  k = 9    # number of people in the group
  d = 5.8  # distance between pub and stadium
  w = 2.5  # walking speed
  v = 30   # motorbike speed
  
  # calculate amount of walking per person
  n = 2 * k - 1
  x = fdiv(d * w * (n - 1), v + w * n)
  
  # calculate time taken
  t = fdiv(x, w) + fdiv(d - x, v)
  
  # output solution
  printf("t={t:g} hours (= {m:g} min) [x={x:g} miles]", m=t * 60)
  

  Solution: The minimum travelling time is 82 minutes.

  We calculate:

  x = 16/5 = 32/10
  t = 32/25 + 13/150 = 41/30 = 82/60

  So the first friend is dropped off 3.2 miles from the stadium (and walks the remainder of the way).

  Each friend walks for 76.8 minutes and is on the motorbike for 5.2 minutes. Giving each a total journey time of 82 minutes.

  LikeLike

  • 

    Jim Randell 10:56 pm on 30 November 2022 Permalink | Reply

    (See also: Enigma 977).

    Here is a numerical approach, based on the barman dropping the first friend off after a distance x (from the pub) while the remaining friends set off on foot.

    The barman then returns to the trailing group and ferries a single friend from the trailing to the leading group until everyone has been transferred to the leading group. And we record the maximal journey time for the friends to give us a total time to get all the friends to the stadium.

    We then use the [[ find_min() ]] function from the enigma.py library to determine at what distance x the shortest total journey time occurs.

    Unsurprisingly this gives us the same answer as the analytical approach above (but with considerably more effort). But it does show that the logic used in the analysis does indeed produce the minimum time.

    Run: [ @replit ]

    from enigma import (irange, fdiv, find_min, printf)
    
    k = 9    # number of people in the group
    d = 5.8  # distance between pub and stadium
    w = 2.5  # walking speed
    v = 30   # motorbike speed
    
    # if: A starts at a, velocity v; B starts at b, velocity w
    # return: (<position>, <time>) of meeting
    def meet(a, v, b, w, t0=0):
      t = fdiv(b - a, v - w)
      return (b + t * w, t0 + t)
    
    # run a scenario where the first person is dropped off at distance x
    # return the time taken for everyone to arrive
    def run(x):
      ts = list()
      # ferry friend 1 to x and let them walk the remaining distance (d - x)
      d1 = x
      t1 = fdiv(x, v)
      # and so the total time for the first friend is ...
      ts.append(t1 + fdiv(d - d1, w))
    
      # the position of the trailing group at time t is:
      tr = lambda t: min(t * w, d)
      # the position of the leading group at time t >= t1 is:
      ld = lambda t, t1=t1: min(x + (t - t1) * w, d)
    
      # ferry the remaining friends ...
      for _ in irange(2, k):
        # we return from d1 to the trailing group
        (d2, t2) = meet(d1, -v, tr(t1), w, t1)
        # and then back to the leading group
        (d3, t3) = meet(d2, +v, ld(t2), w, t2)
        if d3 < d:
          # they walk the remaining distance
          ts.append(t3 + fdiv(d - d3, w))
        else:
          # they are dropped off at the stadium
          (d3, t3) = (d, t2 + fdiv(d - d2, v))
          ts.append(t3)
        (d1, t1) = (d3, t3)
      # return the maximum time
      return max(ts)
    
    # find the minimal time
    r = find_min(run, 0, d)
    (t, x) = (r.fv, r.v)
    printf("min time = {t:g} hours (= {m:g} min) [drop 1 at {x:g} miles]", m=t * 60)
    

    Here is a graph of the total journey time against the distance x that the first friend is taken from the pub. We see that the minimum time is achieved when x = 2.6 miles.

    

    LikeLike

  • 

    NigelR 4:29 pm on 1 December 2022 Permalink | Reply

    Hi Jim. I very much enjoyed this puzzle (more for the logic than the Python content!) but I’m intrigued to know how you got to the term 2kx in your second equation. I got to it indirectly by looking at the vector sum of all the motorbike journeys out: [(k)(d-x)] +back: [(k)(d-x)-d] given that he finishes up a distance d from where he started. That then reduces to:
    [(2k-1)d -2kx] but is there a more intuitive way of getting to the second term?

    LikeLike

    • 

      Jim Randell 10:50 pm on 1 December 2022 Permalink | Reply

      @Nigel: The way I thought of it the barman makes a journey towards the stadium for each of the k friends. And in between friends he has to make (k − 1) return journeys towards the pub.

      If he made complete journeys between the pub and the stadium this would be (2k − 1) journeys of distance d for a total of (2k − 1)d.

      But if he made complete journeys he would be travelling over the ground that each friend walks, in both directions, so this amount is overcounting the barmans distance by 2x for each of the k friends.

      So the actual overall distance travelled by the barman is:

      (2k − 1)d − 2kx

      And this actual distance is travelled at velocity v, so we can determine the total time taken for the barman.

      LikeLike

      • 

        NigelR 9:31 am on 3 December 2022 Permalink | Reply

        Thanks Jim. It was the ‘in both directions’ that I was struggling to get my head around. This week’s puzzle is trivial by comparison!

        LikeLike

• 

  Hugh Casement 9:45 am on 4 December 2022 Permalink | Reply

  There were some early Brain-Teasers of a similar kind by Brigadier A.G.H. Brousson (who died in 1976), involving the Smart brothers who took part in races with one bicycle between them.
  Numbers 640, 663, 686, 722, 741, and 792 would presumably yield to a variant of Jim’s analysis as given here. 792 (at least) is flawed because it doesn’t specify that they all arrived together — nor, for that matter, whether riding pillion on the rear carrier is permitted (I know from experience that it seriously upsets the balance and steering!).

  LikeLike

  • 

    Jim Randell 10:53 am on 8 December 2022 Permalink | Reply

    @Hugh: Thanks. I’ll have a look at those. None of them are in the published books I’m working from, so it would have been a while before I got round to looking at them.

    LikeLike