##
Solution

I received solutions to various aspects of the problem from John Sullivan,
Bruce Torrence, Rob Pratt, John Snyder, Lee Gao, Joseph DeVincentis, Sam
Vandervelde, Wei Chen, and Barry Cox.

Let p(a, b) be the probability of reaching a, b (we assume here a is nonnegative).

Let g be the golden ratio; F(n) be the Fibonacci numbers; and L be (3 − √5)/2.

Then:

p(n, 0) = 1/g^{2n} = L^{n} = F(2n)L − F(2n − 2)

p(0, 1) = 3/5

p(1, 1) = 2/5

p(n, 1) = 1/5(2nF(2n) − 3(n + 1)F(2n − 2)) − L(3(n − 1) F(2n) − 2nF(2n − 2))

Complete solution notes, including a formula for the general case p(a, b), can be found at s1201_1.pdf.

An additional file — the investigation by Snyder — is posted at s1201_2.pdf.

It appears that, for fixed y, p(n, y) is a combination of polynomials of
degree y and the Fibonacci numbers F(2n) and F(2n − 2) and L.

[Back to Problem 1201]

© Copyright 2015 Stan Wagon. Reproduced with permission.