BMO2 2001 Question 1 Recurrence Relation

Question

Ahmed and Beth have respectively $p$ and $q$ marbles, with $p > q$. Starting with Ahmed, each in turn gives to the other as many marbles as the other already possesses. It is found that after $2n$ such transfers, Ahmed has $q$ marbles and Beth has $p$ marbles. Find $\frac{p}{q}$ in terms of $n$.

The number of marbles each person has seems to follow a pattern, for example: Ahmed initially has $p$ marbles then $p-q$ and then $2p-2q$, with the coefficient of $p$ initially $1$ and the coefficient of $q$ initially $0$, they follow the pattern that $a_{m+1}=2a_{m}$ if $m$ is odd and $a_{m+1}=2a_{m}-1$ if $m$ is even (where $m$ is the number of exchanges), a similar result is true for Beth. I though if I could find a formula for $a_{m}$ in terms of $n$ the I could set it equal to $q$ in Ahmed's case and find $\frac{p}{q}$ in terms of $n$, but I can't find of way of doing this. I've also considered trig substitution, but I don't really know what to substitute.

If anyone could come up with an answer, that would be greatly appreciated.

Answer 1

You already have a good answer, this is just another way to solve the recurrence. Let $p+q = S$ and denote $a(n)$ the marbles Ahmed has. Clearly $a(0) = p$.

So let $a(2k)$ denote the marbles Ahmed has after $2k$ transfers. Then Beth must have $S-a(2k)$ marbles by the Law of Conservation of Marbles. next transfer must then lead to $a(2k+1) = a(2k)-(S-a(2k))= 2a(2k)-S$, and after that we have $a(2k+2) = 4a(2k)-2S$.

We may now define $f(k) = a(2k)$ to simplify things, and get the recursion $$f(k+1) = 4f(k)-2S$$
with $f(0)=p$. Solving this would give $$f(k) = \frac13\left((4^k+2)p-2(4^k-1)q \right)$$

Setting $f(n)=q$, we have $3q = (4^k+2)p-2(4k-1)q \implies \dfrac{p}q = \dfrac{2\cdot4^n+1}{4^n+2}$...

Answer 2

A linear algebra approach.

Let $(p_k,q_k)$ be the pair after $2k$ transfers. So $(p_0,q_0)=(p,q)$.

Then after $2n+1$ transfers, they have $(p_k-q_k,2q_k)$. After $2k+2$ transfers, you have: $$(p_{k+1},q_{k+1})=(2p_k-2q_k, 3q_k-p_k)$$

So $$\begin{pmatrix}q\\p\end{pmatrix}=\begin{pmatrix}p_{n}\\q_{n}\end{pmatrix}= \begin{pmatrix}2&-2\\-1&3\end{pmatrix} \begin{pmatrix}p_{n-1}\\q_{n-1}\end{pmatrix} = \begin{pmatrix}2&-2\\-1&3\end{pmatrix}^{n} \begin{pmatrix}p\\q\end{pmatrix} $$

So, you want to analyze $A=\begin{pmatrix}2&-2\\-1&3\end{pmatrix}$.

The characteristic polynomial of $A$ is $(x-2)(x-3)-1\cdot2=x^2-5x+4=(x-1)(x-4)$. An eigenvector for eigenvalue $1$ is $v_1=(2,1)^T$, an eigenvector for eigenvalue $4$ is $v_4=(1,-1)^T$. So $$\begin{pmatrix}p\\q\end{pmatrix}=\frac{p+q}{3}v_1 + \frac{p-2q}{3}v_4$$ and thus:

$$\begin{align}A^n \begin{pmatrix}p\\q\end{pmatrix} &= \frac{p+q}{3}v_1 + 4^n\frac{p-2q}{3}v_4\\ &=\begin{pmatrix}2\frac{p+q}{3}+4^n\frac{p-2q}{3}\\ \frac{p+q}{3} - 4^n\frac{p-2q}{3} \end{pmatrix} \end{align}$$

So you need $$3q=(4^n+2)p+2(1-4^n)q\\3p=(1-4^n)p +(1+2\cdot4^n)q$$

Solve. I get $$\frac{p}{q}=\frac{1+2\cdot 4^n}{4^n+2}=2-\frac{3}{4^n+2}$$

Since $4^n+2$ is divisible by $3$, we can let $q=\frac{4^n+2}{3}$ and let $p=2q-1$.

Not sure about all my arithmetic steps, so let's try some examples.

It gives the right result for $n=1$, $q=2,p=3$. It also works for $n=0$ - $q=1,p=1$.

For $n=2$, $q=6,p=11$. Then $$(11,6)\to (5,12)\to (10,7)\to (3,14)\to (6,11).$$

Seems to work.

If each person at each turn give $\alpha$ times the number that the other person holds, the same approach works, with the eigenvalues $1,(\alpha+1)^2$, and the value:

$$\frac{p}{q}=\frac{(\alpha+1)^{2n+1}+1}{(\alpha+1)^{2n}+\alpha+1}$$

So, for example, with $\alpha=2$ and $n=3$ then $\frac{p}{q}=\frac{3^7+1}{3^6+3}=\frac{547}{183}$.

$$(547,183) \to (181,549) \to (543,187) \to (169,561) \to (507,223) \to (61,669) \to (183,547) $$

When $\alpha=\frac{1}{2}$ and $n=2$ you get $(p,q)=(55,42)$ and: $$(55,42) \to (34,63) \to (51,46) \to (28,69) \to (42,55) $$

Interestingly, if you play the game with three people rotating, and each player at his turn doubles both other player's money, then to get from $(p,q,r)$ to $(r,q,p)$ in $3n$ turns, you'd have to start with some multiple of $(4\cdot8^n+1,2\cdot 8^n + 2,8^n+4)$. For instance, the sequence when $n=2$ is:

$$\begin{align}(257,130,68) &\to(59,260,136) &\to(118,65,272) &\to(236,130,89)\\ &\to(17,260,178) &\to(34,65,356) &\to(68,130,257)\\ \end{align} $$

The seems to work with $k$ players and $n$ turns. If $(p_1,p_2,\dots,p_k)$ are the starting positions so that after $kn$ turns, you reach position $(p_k,p_{k-1},\dots,p_1)$ then:

$$p_i=2^{(n+1)k-i} + 2^{i-1}$$

is a general solution. I have no explanation for that...

Answer 3

One approach might be to explore for a solution.

For example it is easy to find that for $n=1$ the solution is $\frac{p}{q}=\frac{3}{2}$ and not difficult to find that for $n=2$ the solution is $\frac{p}{q}=\frac{11}{6}$. So you might guess that in general $p=q+1$. This leads quite quickly to finding for $n=3$ that $\frac{p}{q}=\frac{43}{22}$ with a pattern that looks like:

43  22
21  44
42  23
19  46
38  27
11  54
22  43

Now consider the changes after each pair for Ahmed in having $43, 42, 38, 22$, which are reductions of $1,4,16$, looking like powers of $4$, and as an geometric series they add up to $p-q = (4^n-1)/3$ which you can combine with $p=2q-1$ to give $q=(4^n+2)/3$ and $p=(2\times4^n+1)/3$ and so a ratio of $\dfrac{p}{q}=\dfrac{2\times4^n+1}{4^n+2}$ to answer the question.

You still need to prove this works. But the only difficult part is to show that if after $k$ pairs of swaps Ahmed has $\dfrac{2\times4^n+1}{3} - \dfrac{4^k-1}{3}$ and Beth has $\dfrac{4^n+2}{3} + \dfrac{4^k-1}{3}$, then after the next swap Ahmed has $\dfrac{4^n-1}{3} - 2\times \dfrac{4^k-1}{3}$ and after the following swap $\dfrac{2\times4^n-1}{3} - 4\times \dfrac{4^k-1}{3} = \dfrac{2\times4^n+1}{3} - \dfrac{4^{k+1}-1}{3}$, and so Beth has the rest, namely $\dfrac{4^n+2}{3} + \dfrac{4^{k+1}-1}{3}$, and the proof will follow by induction. As a further point, Ahmed's and Beth's marbles can be multiplied by a common integer without affecting the ratios.