Enigmatic Code

Programming Enigma Puzzles

Tantalizer 480: Pitter patter

From New Scientist #1031, 16th December 1976 [link]

When the Olympic games were last held in Patagonia, the Famous torch entered the country at a point exactly 35.27 km from its pedestal in the Olympic stadium. The honour of transporting it from the frontier fell to two Patagonian athletes, Pita and Pata, who were to carry it in turns for the 35.27 km. By presidential decree each was to carry it at each turn any distance he pleased not less than 1 km and not more than 2 km.

Each secretly resolved that he would be the one to carry it the final awesome metre. Since there was nothing in the decree to forbid a different choice of distance at each turn much calculation went on before Pita and Pata tossed for the privilege of having the first turn. In fact Pita won the toss and chose second turn.

Did he chose right?



One response to “Tantalizer 480: Pitter patter

  1. Jim Randell 7 June 2017 at 7:03 pm

    This Python program implements a strategy where, for a given distance, each runner has to run between 1000m and 2000m in increments of 10m.

    For a distance of 35,270m the program executes in 134ms.

    from enigma import irange, cached, arg, printf
    # possible distances to run
    distances = list(irange(1000, 2000, step=10))
    # winner at distance d
    # 0 = no-one
    # 1 = current runner
    # 2 = other runner
    def win(d):
      # less than 1 km remaining
      # no one wins
      if d < 1000: return 0
      # between 1 km and 2 km remaining
      # the current runner wins
      if not(d > 2000): return 1
      # more than 2 km remaining
      # consider possible distances for current runner
      best = 0
      for x in distances:
        # result for the remaining distance
        r = win(d - x)
        # if no one wins then see if there's a better option
        if r == 0: continue
        # if it's a win for the current runner, do that    
        elif r == 2: return 1
        # if it's a win for the other runner, remember it
        elif not best: best = 2
      # if we get this far, the current runner hasn't won, so return the best option
      return best
    d = arg(35270, 0, int)
    r = win(d)
    printf("distance = {d}, winner = runner {r}")

    Solution: Yes – Pita was right to choose to run second. For a distance of 35.27km the second runner can always finish with the torch, regardless of how far the first runner runs on each leg.

    A strategy for B (the second runner) is to always finish his distance at a multiple of 3km. So if A (the first runner) runs 1km then B runs 2km, and if A runs 2km then B runs 1km. In general B runs (3 – A) km. So after 11 A+B legs the torch has travelled 33km, and has 2.27km to go. A cannot finish on his turn, as he must run between 1km and 2km, and in order to leave B a run between 1km and 2km, he has to run between 1km and 1.27km, leaving B to run the remaining (2.27 – A) km.

    This works because the residue of 35.27 mod 3 is 2.27. Which is more than 2, so by ensuring each A+B pair is exactly 3 km, this residue remains on the final leg, and A must reduce it by at least 1km, which brings it into the scope of B. So the same strategy would work for any distance with a residue in the interval (2, 3]. (Treating a residue of 0 as 3).

    However if the residue is in the interval (0, 2] then the first runner can always finish with the torch. So if the runners have to choose without knowing the distance beforehand, it would be better to choose to go first, as the first runner can always finish with the torch 2/3 of the time, and the second runner finishes with the torch only 1/3 of the time.

    If the first runner realises that the second runner is going to use this strategy, they can get away with only running 1km on each leg. So in total the first runner only needs to run 12km, while the second runner has to run the remaining 23.27km (almost twice as far).

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: