3
$\begingroup$

William has eight boxes numbered $1$ to $8$ lined up in a row next to an empty bag. Initially each box contains one token. At each stage either of the following types of moves are permitted.

There are two moves:

For a non-empty box $i$ with $i < 8$, remove a token from box $i$ and add two tokens to box $i + 1$. (Call this move MOVE1)

For non-empty boxes $i$ and $i + 1$, remove a token from each box and add one token to the bag. (Call this move MOVE2)

What is the maximum number of tokens that William can get into the bag?

I tried assigning each box's weight as $\frac{1}{2^i}$, but I'm now stuck.

Thank you!

$\endgroup$
2
  • $\begingroup$ The problem with your weight is that it is not conserved with MOVE2. When you put the token in the bag you lose track of which boxes were used to get it. Can you convince yourself that you only want to use MOVE2 on boxes with high numbers? $\endgroup$ Nov 21, 2021 at 4:17
  • $\begingroup$ Yes, I can see that logically, it is the most effective way. $\endgroup$ Nov 21, 2021 at 4:30

1 Answer 1

5
$\begingroup$

As you observed, by assigning weight $2^{-i}$ to box $i$, we know that the sum of the weights of all boxes are constant when MOVE1 is executed. Moreover, the sum decreases when MOVE2 is executed. More precisely, the sum will decrease by at least $2^{-8} + 2^{-7} = 3 \cdot 2^{-8}$. Since the sum of the weights originally is $$2^{-1} + 2^{-2} + 2^{-3} + \dots + 2^{-8} = 255 \cdot 2^{-8},$$ we know that we can do MOVE2 at most $\dfrac{255 \cdot 2^{-8}}{3 \cdot 2^{-8}} = 85$ times, i.e., the maximum number of tokens in the bag cannot exceed $85$.


Next, we prove that we can indeed get $85$ tokens in the bag.

Simply do MOVE1 on every box until it is empty, starting from box $1$ to box $6$. We can compute that we will have $127$ tokens in box $7$ and $1$ token in box $8$ (and $0$ tokens in the other six boxes) after those series of steps.

Now, do MOVE1 $42$ times on box $7$. We will then have $85$ tokens in box $7$ and $85$ tokens in box $8$. We can then do MOVE2 $85$ times on these two bags to get $85$ tokens in the bag.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .