Is it possible to have $2^{2015}$ balls in a box according to these rules?

Question

I have the following exercise, about counting, especially.

Exercise Deeds has a big sack of balls and three empty boxes, $A$, $B$ & $C$. He will put the balls on the boxes according to the next rules (in any order, and how many times he wants):

• (a) He can take out a certain amount of balls of box $A$, and add the same amount of balls, squared, on box $B$.

• (b) He can take out a certain amount of balls of box $B$ and add the double of the amount on the box $C$

• (c) He can take out all the balls on box $C$ and add that amount on box $A$ and box $B$ (Example, if he had $9$ balls on $C$, he will add $9$ to $A$ and $9$ to $B$, and will remain $0$ on $C$

Initially he has $1$ ball, and he can put it in any box:

A) Is it possible to get $2^{2015}$ balls in box $C$, and that the other two boxes remain empty?

B) And if the target were $2^{2014}$ balls?

What I have so far

-It doesn't matter where do you put the first ball, you will always have a pair numbers of balls in box $C$ at second movement.

-if we start from the end, the penultimate movement will be $2^{2014}$ on $B$.

Next to that you should find a way, i'd appreciate any help! Thanks!

Answer 1

It is always possible to make a power of $2$ count of balls in $C$ with the other boxes empty, ignoring time constraints, as follows:

For even powers of $2$, start with the ball in box $B$ and move to box $C$ to get $2$ balls there. For odd powers of $2$, start with the single ball in box $C$. Then proceed as follows:

• $M1$: Undertake move (c) $\qquad [A \leftarrow C, B \leftarrow C, C \leftarrow 0]$
• $M2$: Undertake move (a) $\color{blue}{\text{with }1\text{ ball}}$ repeatedly until box A is empty, effectively moving the contents of box A into box B $ \qquad k[A \leftarrow A-1, B \leftarrow B+1^2]$
• $M3$: Undertake move (b) $\qquad [C \leftarrow 2B, B \leftarrow 0]$

At this point the contents of $C$ have been multiplied by 4 compared to the start of the process. Repeat these steps until the desired number is reached.

Of course this is a grossly inefficient process, and numerous shortcuts for any given target number could no doubt be found.

---

Step $M2$ can be modified to provide an accelerated passage through the powers of $2$, once the number of balls in $A$ at the start of the step gets big enough.

As the first example, if the initial number of balls in $A$, $n\ge 8$, then we can take groups of $4$ for half of $n$, then groups of $2$ for the remainder. This gives $$|B| = n + 4\frac n2 + 2\frac n2 = n+2n+n = 4n$$ instead of $|B|=2n$ as it would otherwise be. As $|A|$ gets larger, more acceleration is possible:

for $n=|A|\ge 64$ we can take groups of $16,8,2$ for $$|B| = n + 16\frac n4+ 8\frac n4 + 2\frac n2 = n+ 4n+2n+n = 8n$$

for $n=|A|\ge 128$ we can take groups of $32,16,8,4$ for $$|B| = n + 32\frac n4 + 16\frac n4+ 8\frac n4 + 4\frac n4 = n+8n +4n+2n+n = 16n$$

for $n=|A|\ge 1024$ we can take groups of $128,64,16,8,4$ for $$|B| = n + 128\frac n8 + 64\frac n8+ 16\frac n4 + 8\frac n4 + 4\frac n4 = n+16n +8n +4n+2n+n = 32n$$

and so on

This also means that it is not necessary to adjust the start of the process to the parity of the power of two targetted.