High order thinking question

Question

We have 2 urns with arbitrary no of balls.Now we can do two types of operations

1. Taking out equal balls from both urns .

2. Doubling ball in any urn.

Show that both the urns can be made empty by repeating operations finitely

I did it as

Let urns have m&n balls & m

Take out m-1 balls from both urns

Now double the remaining 1 ball.

Take out 1 ball from both urns.

Double the remaining 1 ball.....

When both urn came to situation where both urns have 1,1 ball.take out the balls & we are done.

But it is a guess method .I want a pure mathematical solution.

Thanks in advance.

Answer 1

Your method works just fine!

To make it into a rigorous mathematical proof you can use Induction to show that for any $n \geq 1$ if one urn has 1 ball left, and the other $n$, then you can solve the problem:

Base: $n=1$ now both urns have 1 ball, so empty both. Solved!

Step: If one urn has 1 ball and the other $n+1$, then double the 1 ball, and then remove 1 ball from both, so you end up with 1 ball in one urn, and $n$ in the other. By inductive hypothesis we can solve that problem, so we can therefore also solve the $(1,n+1)$ problem.

That completes the induction. So now we can prove that the problem is solvable for any $(m,n)$:

If $m=n$ then remove $m=n$ balls from both urns. Solved!

Otherwise $m>n$ or $n<m$. By symmetry we just have to show one case, so suppose $m>n$. Then $m=n+k$ for some non-zero $k$. Then remove $n-1$ balls from both urns, so you end up with $(k+1,1)$, which we earlier showed to be solvable.

So yes, this follows the exact method you did, but spelled out a bit more rigorously, so it is more acceptable as a proof.

Answer 2

Another straightforward proof could go as follows:

1. Double the smaller urn until it is at least half of the bigger urn (not needed if it is already the case at start).
2. Now the smaller urn has $n$ balls and the bigger has $n+k$ balls (with $k \leq n$). Remove from both urns $n-k$ balls. Now, the bigger urn has exactly $2k$ balls and the smaller one has exactly $k$ balls.
3. Double the smaller urn one last time so that the urns contain the same number of balls and you can empty both urns with one last move.

In the end if urns had originally $m$ and $n$ balls with $m \geq n$, it requires $3 + \lceil\log(\frac{m}{2n})\rceil$ operations.