### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,183)
- misc (2)
- project euler (2)
- puzzle (46)
- site news (46)
- tantalizer (49)
- teaser (3)

### Site Stats

- 184,820 hits

Advertisements

Programming Enigma Puzzles

1 December 2014

Posted by on **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

%d bloggers like this:

This Python program runs in 46ms.

Solution:The probability of George finishing where he started is 46189/262144 (about 0.1762).George is planning to walk for 20 days.

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:

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

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:

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.