Puzzling Probability Part 3

This is part 3 of a series in which I am exploring some interesting probability puzzles.

As someone who loves to walk, probability puzzles that involve considering different routes to the same destination are interesting to me. However, this puzzle requires a warm up. Consider the following:

How many ways are there to walk from A to B (assuming no back tracking)?

path-1

At first, I tried to draw all the possible paths:

path-1-5

Then I realized that it was going to take far too long and I could never be sure that I didn’t miss a path. I needed another approach. Instead of trying to figure out how many ways there were to get from A to B, I asked a simpler question: How many ways to get from A to C?

path-1-75

Clearly, we can only get to C in only 1 way. We place a number 1 at the intersection. Similarly, we only have 1 way to get to each intersection point along the top and along the left side. Next, we need to determine how many ways to get to point D.

path-3

Since there is 1 way to get to the point above D and 1 way to get to the point left of D, we add these and obtain 2 ways to get to D. Continuing like this with each intersection point on the grid, we have:

path-4

Thus, there are 20 different ways to walk from A to B.

Now we can answer the actual question. What is the probability that a random walk from A to B (assuming no back tracking) passes through the middle of the grid below?

path-5

Using the above method, we find that there are 70 ways of walking from A to B. To count the number of ways through the middle, we simply redraw the gird to force us through the middle as follows:

path-6

Again, using the above method, we find that there are 36 ways of walking through middle.

Hence, the probability is 36/70. If you try this exercise for a 6 by 6 grid, you will find that the probability is 4900/12870.

This was counter intuitive to me. In a very large gird, if you were to randomly walk from one end to the other, it seemed to me very unlikely you would pass exactly through the center. The above solution shows that even for a 6 by 6 grid, the probability of walking through the exact center is 38%. As an extension, what do you think happens to this probably as the grid grows larger? Does it approach a specific value? Or does the probability eventually tend to zero?

Advertisements

Leave a comment

Filed under Uncategorized

Leave a Reply

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