Pop the Last Bubble

Question

Having bested the silly clown, you go to your packaging job. It is a slow day, so you decide to teach the game you learned to one of your coworkers. There are no balloons around, so you use bubble wrap instead.

This two player game is played with a huge roll of bubble wrap, which has sixteen million bubbles. Players take turns popping some nonzero number of bubbles. The only restrictions are:

• On the first turn, the current player can't pop all the bubbles.
• On later turns, a player can't pop more bubbles than their opponent just popped.

Whoever pops the last bubble wins.

Your friend has had lots of practice popping bubble wrap: he is so confident of his ability that he bets $100 he can win, and even lets you choose who goes first.

Should you go first or second? How can you guarantee victory?

---

^{This is the same game as before, but starting with 16,000,000 things instead of 99. This makes the puzzle much less trivial.}

Answer 1

The most simple strategy I can think of:

Go first. During each of your turns write the nubmer of remaining bubbles as a binary number (for $16,000,000_{10}$ this would be $111101000010010000000000_2$). During your turn pop a number of bubbles equal to the value of the lowes bit set (this would be $10000000000_2 = 1024_{10}$ at the beginning). Repeat until you get all bubbles in the last turn.

This is guaranteed to work because:

$1.$ The starting position is not a power of $2$ allowing the algorithm to work during the first turn (otherwise let the opponent go first).
$2.$ During each of your turns you pop either all bubbles (winning the game) or less than a half of them (preventing the opponent to win in next turn).
$3.$ After each of your turns the $x$ lowest bits are all $0$, where $x$ is the number of bits in the number of bubbles you popped.
$4.$ Your opponent will set at least one of the lowest $x$ bits to $1$ during his move, which enables you to repeat the procedure in the next move.

Answer 2

Go first.

Theorem: a player facing a $2^i$ bubbles, where $i$ is a positive integer, and who cannot pop them all immediately, is guaranteed to lose.

Proving the theorem by induction.

For $i=0$, it is impossible, as you can't face 1 bubbles and not be able to pop it.

For $i=1$, you face 2 bubbles, and cannot pop both. You must pop one, and thus lose.

For $i=2$, you face 4 bubbles. If you pop 2 or 3, your opponent pops the rest, and you lose. If you pop 1, then you alternate popping 1 until he wins.

The next step is to assume the theorem is true for all $i \leq N$.

If you face $2^{N+1}$ bubbles and pops $2^N$ or more, your opponent will immediately pop the rest and win.

If you pop fewer than $2^N$, your opponent adopts a strategy that guarantees you will face $2^N$ bubbles, eventually. This strategy is the exact same strategy the opponent would use if you faced $2^N$ bubbles initially. Since the theorem holds for $i \leq N$, such a strategy must exist. Thus your opponent can force you to end up facing $2^N$ bubbles, which we have already proven is a lose condition.

QED, by induction the theorem is proven. Anyone facing a number of bubbles that is a power of 2, but who cannot win immediately, must lose.

To win, you force your opponent to face $2^i$ bubbles. You start with 16 million, and the next power of 2 is $2^{23}$. So you pop $16000000 - 2^{23} = 7611392$ bubbles.

Your opponent faces $2^{23}$ bubbles. From there on, the strategy is to keep forcing your opponent to face powers of two balloons, until you can win.

Update: As some comments have pointed out, proving that a winning strategy exists is not exactly the same as providing a strategy.

Strategy for winning if your opponent faces $2^N$ bubbles: If your opponent pops $x$ bubbles, find $i$ such t hat $2^{i-1} \le x < 2^{i}$, then pop $2^{i} - x$ bubbles.

Why this works:

First, since $x \ge 2^{i-1}$, it flollows that $2^{i} - x \le 2^{i} - 2^{i-1} = 2^{i-1} \le x$, so it is always possible to pop that number of bubbles.

Second, if $i = N$, then you have just won.

Otherwise, you have ensured that your opponent is facing $2^{N} - 2^{i} = 2^{N-1} + A 2^{i}$ bubbles, and cannot pop more than $2^{i-1}$. By continuing this strategy, you can peel off each group of $2^i$ bubbles until your opponent faces $2^{N-1}$.

Answer 3

I feel like there is a way easier solution to this, but I'll just post the one I found:

Let the friend start

The friend will obviously start with a number < 16,000,000 / 2, or else he would lose because you would be allowed to pop all the remaining bubble wraps.

If the number he picked is even:

Now calculate in some kind of loop if the number he picked is dividable by 4. If no, you will pop the same amount of bubble wraps / 2. If yes, then do the same with the previous number * 2, and so on. Just stop when it's not dividable anymore, and pick that number.

Of course, when the number he picked is odd, just pick 1, then he will lose certainly.

Example:

He picked 24.
Dividable by 2? (=Even?) - true
Dividable by 4? - true
Dividable by 8? - true
Dividable by 16? - false.

So pick 8