You Are Standing On The First Step Of An Infinitely Long Numbered Path

How likely will you step on step 25?

Math Puzzle | An Infinitely Long Numbered Path

You have a fair coin which has the number 1 written on one side and the number 2 on the other. You throw the coin, and if it comes up N, you would then take N steps to the right.
For example, if you throw the coin and it comes up 2, you take 2 steps to the right to land on step number 3.
You now repeat the exercise, throwing the coin again and walking the number of steps that comes up on the coin. If you throw the coin 24 times, you are certain to have landed on, or past, step number 25.

What is the probability that at some point you will land on step number 25?

In this article, I will present two approaches. One involves a counting approach, which is a bit long-winded. The other is a clever analytic method. Can you think of other ways too?

---

Solution 1: Combinatorics

We are starting with a fair coin that has number 1 on one side and number 2 on the other. Let’s introduce the following notation for the coin tosses.

where an refers to the value of the nth toss of the coin.
Say we simplify the problem by considering the probability it reaches numbers 2, 3 and 4 by throwing the die once, twice and three times.

---

Reaching number 2

To reach number two, we only need to toss the coin once. The die either comes up 1 or 2.

Here there’s only one way that reaches the number 2 out of 2¹ = 2 possible ways. The probability is therefore 1/2¹ = 1/2.

---

Reaching number 3

To reach number 3, we can throw the coin twice. There are in total 2² = 4 ways to throw the coin twice. Of these, only the following leads to the number 3.

We throw the coin twice here, and one way leads to number 3.

We throw the coin once. And only when we throw a 2 do we get to the number 3. So the probability is 1/2² + 1/2 = 3/4.

---

Reaching number 4

Reaching number 4 is a bit more nuanced. We can either get the 1 on the coin three times, or get 1 one time and 2 the other time.

We throw the coin three times, and only one way leads to number 4.

We throw the coin two times, and there are 2C1 = 2 ways to get to number 4. Notice that (1, 2) and (2, 1) count as two possible ways. The probability is therefore 1/2³ + 2/2² = 5/8 = 0.625.

---

Reaching Number 25

We now apply the reasoning above to the number 25. Since we start at number 1, what we are really interested in is how to add up to number 24 with only 1s and 2s. We can take a look at the following table:

The first equation tells us that we throw the coin 24 times. And of those 24 times, getting all 24 throws as 1s on the coin is the only way we can reach 25. Now for the second equation, we throw the coin 22 + 1 = 23 times, and of those 23 times, as long as we have twenty two 1s and one 2, we will reach 25.

The idea is to sum up all these individual probabilities to get to our answer. Mathematically, we use the combination operator:

And that’s one way to get to the answer. Let’s get onto the analytic method.