Thank your Lucky Stars
A star is placed in the bottom right hand corner of a grid. You toss a coin and
- if it is heads you move the star one square up
- if it is tails you move the star one square to the left
If after tossing the coin the star would move off the grid you stop.
What is the probability that you end up in the top left-hand corner of the grid for 2 x 2, 3 x 3, 4 x 4 and n x n grids?
Start with the simple problem, where you need to flip the coin twice:
Which moves are possible?
Which moves lead you to the target?
Move to the hardest problem...
Thank you for this solution Andrei (Andrei Lazanu, School 205 Bucharest) and for the link to the useful site:
For a 2x2 grid I need to
make 2 moves.
There are 4 possible paths:
left, up
up, left
up, up
Only 2 of these take me to the top left-hand corner of the grid, so the probability of getting to the opposite corner is: $$ {{1 \over{2^2}}\times2} = {2 \over4} = {1 \over2} $$
For a 3x3 grid I need to
make 4 moves.
There are 16 possible paths.
Only 6 of these take me to the top left-hand corner of the grid, so
the probability of getting to the opposite corner is: $$ {{1
\over{2^4}}\times6} = {6 \over16} = {3 \over8} $$
For a 4x4 grid I need to make 6 moves.
There are 64 possible paths.
Only 20 of these take me to the top left-hand corner of the grid, so the probability of getting to the opposite corner is: $$ {{1 \over{2^6}}\times20} = {20 \over64} = {5 \over16} $$
I found on the Internet, at the Math Forum, the formula together
with the explanation.
The address is: http://mathforum.org/library/drmath/view/54218.html
The formula generating the number of ways to go from one corner to
another is: $$ {[2(n-1)]!} \over{[(n-1)!]^2} $$
The formula generating the probability of landing in the opposite corner in a n x n grid is: $$ {{1 \over{2^{2(n-1)}}}} \times{{[2(n-1)]!} \over{[(n-1)!]^2}}. $$
I verified my results and they worked for n = 2, 3 and 4.This problem offers an interesting context in which to think about permutations in a systematic way.
It can lead to an appreciation of Pascal's triangle.
There is an Excel spreadsheet available to download here where you can experiment with this problem.