Welcome to NRICH.

 
Swapping marbles
This question comes from the 2001 British Maths Olympiad second round competition. For the whole paper, see here.
By Peter Conlon (P2714) on Wednesday, February 28, 2001 - 06:36 pm:

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 Michael Doré (Md285) on Wednesday, February 28, 2001 - 10:19 pm:

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

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

and

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

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

(2×4n + 1)/(4n + 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.

By Anonymous on Wednesday, February 28, 2001 - 10:35 pm:

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

A2n = -2A2n-1
B2n+1 = 2B2n
B2n = B2n-1-A2n-1
A2n+1 = A2n-B2n

but could be wrong.

Eliminate all terms except those of the form A2m for m some integer. You can then put A2n = g2n 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.

By James Lingard (Jchl2) on Wednesday, February 28, 2001 - 10:44 pm:

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

(1/3)(4n - 1) = 4n-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.