Ball Drop

Place pins at the corners of all the squares on an 4x4 checkerboard. Now cut the board in half across a main diagonal. Then lift the board to hold one corner at the top and the long diagonal across the bottom.  Drop a ball at the top pin.  When it bounces, it has a 50% chance of heading left or right to the next lower pin, where it again has a 50%^ M chance of a left or right move, and so on until it exits the board. 
  1. There are 6 different locations the ball could exit the board (the four diagonal squares, and outside the board on either side.)  What are the probabilities of exiting from each of them?
  2. Now replace the other half of the board.  In how many different locations could the ball exit the board, and what are the probabilities of exiting from each of them?
  3. Can you generalize this for an NxN checkerboard?
Source: Original.
Solutions were received from Samantha Levin, John Hewson, and Al Zimmermann.
  1. Solving the generic case first, for the triangle, the solutions follow the pattern of Pascal's Triangle. For a size N board, the (N+1) row of Pascal's Triangle represents the number of different ways to exit at each location. The probability of any path in the triangle is 1/2^(N+1). So the probability of exiting at a particular location A (0<=A<=N+1) is:
    (N+1 Choose A)/2^(N+1) = (N+1)! / [A! (N+1-A)! 2^(N+1)]

    So for the 4x4 triangle, we find the probabilities are:
    1/32, 5/32, 10/32, 10/32, 5/32, 1/32

  2. For the full NxN square, there are 2N+2 different exits (to the left of N+1 pins on the left side, and to the right of N+1 pins on the right side.) The number of ways to reach an exit pin can again be provided by Pascal's Triangle, and the probability of each path is 1/2^k, where k is the depth of the pin in the grid.

    For example, there is one path to the far left pin, and its probability is 1/2^N. The probability of exiting when at that pin is (1/2), so the total probability of exiting at the far left pin is 1/2^(N+1).

    To reach the next lower pin, there are (N+1 Choose 1) = N+1 paths, each with a probability of 1/2^(N+1). To exit from there is a probability of 1/2, for a total probability of (N+1)/2^(N+2).

    If we number the exits from 0 to 2N+1, the probability of exiting at each location A (0<=A<=N) is

    (N+A Choose A)/2^(N+A+1) = (N+A)!/[N! A! 2^(N+A+1)]
    and simply the opposite for N+1<=A<=2N+1.

    For the 4x4 square, there are 10 exits, and their respective probabilities are:
    1/32, 5/64, 15/128, 35/256, 70/512, 70/512, 35/256, 15/128, 5/64, 1/32
    With the same denominator of 256, those numerators are:
    8, 20, 30, 35, 35, 35, 35, 30, 20, 8

    An interesting note is that the four central probabilities will always be the same for any size square.

Mail to Ken