Three buckets have marbles. You are allowed to double the number of marbles in a bucket by borrowing from one of the other two buckets. Prove that it is possible to produce an empty bucket with a series of such operations.
This is from https://gurmeet.net/puzzles/empty-the-bucket/index.html
My approach: I started by a1,a2 and a3 marbles and wrote out some operations. But I didn't get what to do after that. Please help.
Deliberately NOT a complete answer
It's helpful to try a few examples to start. Let's look at $(12, 7, 3)$.
You should do a few more yourself. Once you're done, let's suppose that the total number of marbles is $M$. Then any "legal" situation is defined by a triple $(a, b, c)$ of integers where $a, b, c \ge 0$ and $a + b + c = M$.
If we think of real numbers instead of integers, this set forms a triangle in 3-space, one with vertices at $(M, 0, 0), (0, M, 0)$ and $(0, 0, M)$.
On this triangle we can draw lines parallel to the sides, spaced one unit apart, making kind of a triangular graph paper. The "crossings" of this graph paper will be all the integer points. What does the "operation" of moving stuff from one bucket to double the stuff in another bucket look like? It looks like $$ (a, b, c) \mapsto (a-c, b, c + c) $$ but is only allowed when $a > c$. (There are five other operations, defined similarly.) On our graph paper, this amounts to taking a point and moving it parallel to one of the three sides of the triangle so that it becomes twice as far (along that direction) from one of the adjacent sides (see diagram).
What we're asking is whether, after enough moves of this kind, we can always reach one of the sides of the triangle.
Often problems like this are solved by a "potential function" approach. You find some function $(a, b, c) \mapsto f(a, b, c) \in \mathbb N$ with the property that when you do some selected operation (or sequence of operations!), the value of $f$ at the resulting point is lower than the value at the starting point. (An example of such an $f$ might be "the smallest of $a, b, $ and $c$", although that doesn't work well here for single moves.) You then argue that you can decrease $f$ by the right moves, but the value of $f$ is a nonnegative integer, so it'll eventually have to become zero.
An alternative approach is to ask how you might reach the triangle boundary. If you're at a point $(p, q, q)$, then changing it to $(p, q-q, q+q)$ gets you to the boundary, for instance. So you could ask "Among all points of the triangle's interior, which ones reach the boundary in one (well-chosen) operation?" And then you can ask which reach it in 2 operations, and so on, and if you're lucky, you can show that everything reaches the boundary after some number of operations
I don't know how to carry out either of these for this problem, but let me give you a closely-analogous problem for which the first (the 'potential' method) actually does work:
You have a 3-person economy, where each person has an integer amount of dollars, and the total of the 3 people's wealth is some positive integer $T$. At the end of each day, one of two things happens:
All three people have a positive amount of money, and no one gives any money to anyone else. The economy is called "stable"
One person has a negative amount of money, and the other two feel so bad about this that they each give this person enough money to cancel this debt. So if the amounts are (10, 4, -6), then the first two folks each give $6$ dollars to the third, and the new situation is $(4, -2, 6)$. Of course, now person $2$ is in debt, so the next day persons 1 and 3 will each give money to person 2.
This second option leads to some questions: what if TWO people are in debt? In that case, money flows to the person who is more in debt. So $(10, -1, -5)$ becomes $(5, -6, 5)$, for instance. And what if two people are equally in debt? Then we flip a coin to decide which gets their debt erased by the generous mechanism of step 2. So $(10, -2, -2)$ could become $(8, -4, 2)$ or $(8, 2, -4)$.
The problem is to show that such an economy always becomes stable.
The trick is this: look at the largest amount that anyone is in debt. For $(8, -5, -3)$, that'd be $-5$, for instance.
After one step of shuffling around money, this "worst debt" might increase, which seems bad. But after two steps, this "worst debt" always decreases (which requires proof, but working through a few examples will convince you, assuming I've stated this right). And now you can say that 'worst debt' is a number that increases every two steps, but can never be larger than zero, hence must eventually reach zero.
I hope this example gives you a way to think about the current problem that turns out to be useful.