[VA] SRC #012a - Then and Now: Probability

[Werner]

We're going about this the wrong way, I'm sure, and as usual, Valentin has given us a few clues.
The first being that he has a simple program that can calculate the desired answer for any number of rows and steps, quickly. So our (exponential) approach of summing up all point probabilities in each step is correct, but not feasible on our vintage calculators, for lack of speed or memory, or both.
The second being the test case for R=5 and S=4, with the number of steps just enough to reach the last row. Now, this probability is a lot easier to calculate as each successive row probability only depends on the previous row, and there's no need to keep the whole triangle.
And, the third that the sum of probabilities over the triangle necessarily has to be 1.
So, we have to ask ourselves: how does the last-row probability for R rows and R-1 steps change if we take an extra step?
The new last-row probability is the sum of
- the probability of staying in the last row, which is easy, as it is half of the total probability of being in the row at step R-1
and
- the probability of coming down from row R-1
and here I'm stuck, as that is not easy.. or I'm missing the obvious.
Coming down from the edge has a probability of 1/2 and coming down from any middle point has a probability of 1/3, but you'd still need to know all the point probabilities as well.

Hope it gave someone else an idea..
Cheers, Werner