# Two-Dimensional Gobbling Algorithm

Let (m,n) be an ordered pair of positive integers. While m>0 and n>0, let k_1 be a random positive integer between 1 and m and k_2 a random positive integer between 1 and n. Output (k_1,k_2). Let m=m-k_1 and n=n-k_2. What is the expected number of outputs?

Note that in the one-dimensional version of the problem, starting with a single integer n, the expected number of outputs is the nth harmonic number 1+1/2+1/3+...+1/n.

-
People on MO typically like to see some background or motivation for questions, an explanation as to why you're interested in the answer. All the questions you've asked recently are somewhat lacking in this regard. – Keenan Kidwell Jun 26 '10 at 13:03
They all seem to be from here: www2.truman.edu/~erickson/openproblems.html – j.c. Jun 26 '10 at 14:03
Thank you for your kind responses. I had noticed that the one-dimensional case is answered very simply (the formula is given by the nth harmonic number), and wondered whether one could solve the two-dimensional version of the problem. We can derive a recurrence relation. Let e(m,n) be the expected number of outputs. Then e(m,n)=1+(1/(mn))Sum[e(m,n),{j,1,m-1},{k,1,n-1}], for m,n>1, and e(m,1)=1, e(1,n)=1. I wonder whether there is an explicit formula for e(m,n). – Martin Erickson Jun 28 '10 at 16:28