RMO 1991 question 4

Question

There are two urns each containing an arbitrary number of balls. Both are non-empty to begin
with. We are allowed two types of operations:
$(a)$ remove an equal number of balls simultaneously from the urns, and
$(b)$ double the number of balls in any one of them.
Show that after performing these operations finitely many times, both the urns can be made
empty.

This question has been asked atleast $3$ times [1][2][3], but none of them seem to use the approach I am using. Now I am not sure whether my approach is correct or not, but I want to verify it.

My Approach:

Let $A$ be the number of balls in urn $1$ and $B$ be the number of balls in urn $2$ at any given time.

Let the urns contain $x_1$ and $y_1$ balls respectively initially. ($x_1<y_1$ without loss of generaity of course)

Subtract $x_1-1$ balls from both urns thus giving $(1,y_1-x_1+1)$ as the new configuration.

Keep doubling the lower number until $|A-B|$ reach the lowest value possible.

Suppoe the lowest value of $|A-B|$ is reached at configuration $(x_2,y_2)$. Subtracting one less than the lower number of $x_2,y_2$ (suppose $x_2$) gives $(1,y_2-x_2+1)$ as the new configuration.

It can be clearly seen that $|y_2-x_2|\leq|y_1-x_1|$. Thus continuing this process will result in continuous reduction in the value of $|A-B|$ until it reaches its lowest value, ie $0$.

At that stage, we would have $A=B$. Thus taking $A$ balls out of both urns would empty both urns.

$\therefore $ Both urns can be emptied in finite number of operations.

I know that simpler approaches are possible for this question, but I want to check whether my approach is also correct or not. Please check my approach and provide suggestions. Also sorry for I couldn't think of a better title.

THANKS

Answer 1

Suppose we have $x_1,y_1$ balls in urns $A,B$ respectively. We can take the following cases:

Case 1: $x_1=y_1 \implies$ we remove $x_1$ balls from both urns emptying both of them. We are done!

Case 2: Without loss of generality, let $1<x_1<y_1$. We remove $x_1-1$ balls from both urns, giving us $$1\text{ ball in } A, \qquad y_1-x_1+1 \text{ balls in } B $$ let $y_2=y_1-x_1+1<y_1 \ (\because x_1-1>0)$, so that now we have $1,y_2$ balls respectively in urns $A,B$ respectively.
If $y_2=1$, go to Case 1,
else double the number of balls in urn $A$ repeatedly, till there are $x_2=2^k$ balls in urn $A$, so that $$x_2=2^k\le y_2<2^{k+1}$$ so now we have $$x_2=2^k\text{ balls in } A, \qquad y_2 \text{ balls in } B$$ (Note that $x_2\le y_2$), so if $x_2=y_2$ go to Case 1 $\qquad \qquad \qquad (*)$
else go back to the beginning of Case 2 and repeat the steps with $x_2,y_2$ in place of $x_1,y_1$. (So, next we will have $$1\text{ ball in } A, \qquad y_2-x_2+1 \text{ balls in } B $$ where $y_3=y_2-x_2+1<y_2$ since $x_2>1$,
(because $x_2=1\implies 2^k=1\le y_2 < 2^{k+1}=2\implies y_2=1=x_2$ which should have already appeared in $(*)$))

Our process will definitely end because $y_1>y_2>\cdots$ is a strictly decreasing sequence of positive integers and we cannot have an infinite strictly decreasing sequence of positive integers. So at some step, we will end up at $x_n=y_n$ when we will empty both the urns (this is precisely the case mentioned in the last line of Case 2 above).