Ahmed and Beth have respectively p and q marbles, with p > q. Starting with Ahmed, each in turn give to the other as many marbles as the other already possesss. It is found that after 2n such transfers, Ahmed has q marbles and Beth has p marbles. Find ^p /_q in terms of n.

I got stuck trying to find the nth term of a sequence which seemed necessary.

Peter

By induction, after 2n swaps the number of marbles Ahmed and Beth have are:

(p/3 - 2q/3)4ⁿ + (2p/3 + 2q/3)

and

(-p/3 + 2q/3)4ⁿ + (p/3 + q/3)

respectively. We simply need to solve for the first expression equal to q. This would give p/q as:

(2 x 4ⁿ + 1)/(4ⁿ + 2)

I think this is consistent with James' answer. It is also worth mentioning that, in general, the number of marbles Ahmed or Beth have could go negative. If we set p/q to what I wrote then there is no danger of this, at least not up till the point at which Ahmed has q and Beth has p.

I would proceed by writing out four recurrence relations. I think they amount to:

A_2n = -2A_2n-1
B_2n+1 = 2B_2n
B_2n = B_2n-1 -A_2n-1
A_2n+1 = A_2n -B_2n

but could be wrong.

Eliminate all terms except those of the form A_2m for m some integer. You can then put A_2n = g²ⁿ for some n and solve the resulting polynomial equation. Using the initial conditions for n=0 and n=1 you can get a general solution for p after 2n iterations. Then since p+q is constant you have done it.

Ah! (Xⁿ - 1) = (X - 1)(X^n-1 + ... + X + 1) for all X, so with X = 4 we get

(1/3)(4ⁿ - 1) = 4^n-1 + ... + 4 + 1,

which simplifies my answer considerably, to what you get Michael. That's rather reassuring. Is this obvious from some other line of thought?

James.