Enigmatic Code

Programming Enigma Puzzles

Enigma 1274: Going for a walk

From New Scientist #2432, 31st January 2004

George is planning a walking holiday on a long distance footpath that runs generally north-south. He will start at a village near the middle and toss a coin to decide whether to walk north or south. He will then walk in that direction to the next village and check in at the local inn.

Each morning he will toss his coin to decide whether to walk north or south and, as on the first day, walk in that direction to the next village.

Fred commented that George might see the same scenery several times, and might finish anywhere after his planned number of days.

“Well, not quite anywhere, but there are quite a number of possibilities. I might finish where I started.”

“What is the chance of that happening?”

“Exactly 95 per cent of what it would have been if my holiday had of been two days shorter.”

What, as a fraction in its lowest terms, is the probability of George finishing where he started?

[enigma1274]

Advertisements

2 responses to “Enigma 1274: Going for a walk

  1. Jim Randell 1 December 2014 at 8:28 am

    This Python program runs in 46ms.

    from itertools import count
    from fractions import Fraction as F
    from enigma import C, printf
    
    # remember the previous probability
    p0 = 1
    
    for i in count(1):
      n = 2 * i
    
      # total number of itineries
      t = 2 ** n
    
      # how many have equal numbers of Ns and Ss
      r = C(n, i)
    
      # probability of a return
      p = F(r, t)
    
      # ratio with the previous probability
      q = F(p, p0)
    
      printf("[n={n} t={t} r={r} p={p} ({f:.4g}) q={q}]", f=float(p))
    
      # is it 95% of the previous probability?
      if q == F(95, 100):
        printf("n={n} p={p}")
        break
    
      p0 = p
    

    Solution: The probability of George finishing where he started is 46189/262144 (about 0.1762).

    George is planning to walk for 20 days.

  2. Jim Randell 1 December 2014 at 8:29 am

    Here’s an analytical solution.

    For a trip of 2k days there are 2^(2k) different itineraries (the (2k)-length sequences with elements chosen from (N, S)).

    For a trip to return to the same spot there must be k Ns and k Ss in the sequence. We can choose the k Ns (and the rest must be Ss). There are C(2k, k) of these.

    So the probability of a trip returning to the start is:

    P(k) = C(2k, k) / 2^(2k)

    We’re interested in the ratio of probabilities for a trip of length 2k + 2 and a trip of length 2k:

    P(k + 1) / P(k)
    = (C(2k + 2, k + 1) × 2^(2k)) / (C(2k, k) × 2^(2k + 2))
    = C(2k + 2, k + 1) / (C(2k, k) × 4)
    = ((2k + 2)! × k! × k!) / ((k + 1)! × (k + 1)! × (2k)! × 4)
    = ((2k + 2)(2k + 1)(2k)! × k! × k!) / ((k + 1)k! × (k + 1)k! × (2k)! × 4)
    = ((2k + 2)(2k + 1)) / ((k + 1) × (k + 1) × 4)
    = (2(k + 1)(2k + 1)) / (4(k + 1)(k + 1))
    = (2k + 1) / (2(k + 1))
    = (2k + 1) / (2k + 2)

    So for n = 2k + 2 the ratio of the probabilities for a trip of length n days and a trip of length (n – 2) days is:

    (n – 1) / n

    We’re interested in when this ratio is 19 / 20. Which is when the trip is 20 days long.

    The probability of returning to the start is P(10) = 184756 / 1048576 = 46189 / 262144 (≈ 0.1762).

    If the trip was 18 days long the probability would be P(9) = 48620 / 262144 = 12155 / 65536 (≈ 0.1855).

    And P(10) / P(9) = 19 / 20 = 95% as required.

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: