# Pop the Last Bubble

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. • Assuming an average pop action (pop + verification) takes 1/4 of a second, this game would take more than 46 days with no sleep if you started with one bubble. – Ian MacDonald Dec 15 '15 at 18:54 ## 3 Answers 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. • Hm... If you pop 1024 bubbles during the first turn, and the opponent does the same, you are left with 111101000001100000000000 bubbles (or so..), and the lowest bit goes to 1024*2, which is more than the amount popped by your opponent, correct? – Bojidar Marinov Dec 17 '15 at 20:28 • @BojidarMarinov If I and my opponent pop each 1024 bubbles, the remaining number will be 111101000001110000000000, and the value of lowest bit is 1024 again. This is equivalent to the odd number case from the original question, but with bigger numbers. Both can keep popping 1024 bubbles until the first player wins. – Sleafar Dec 17 '15 at 20:50 • Something is wrong with my binary subtraction then... my bad.. – Bojidar Marinov Dec 17 '15 at 20:56 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}$. • I think you neglected the point that your opponent might pop less than a quarter of the remaining bubbles, which could then imply that you would be unable to drop the number of remaining bubbles to the next power of two. I'd suggest proving a slightly stronger theorem. – supercat Dec 14 '15 at 22:36 • I did say "eventually", not immediately. – user3294068 Dec 14 '15 at 22:41 • @supercat, the point is that the second player can use the$2^N$strategy during the$2^{N+1}$game to force the situation where the first player has to chose from$2^N$, which is a known win for the 2nd player. – Dr Xorile Dec 14 '15 at 22:53 • In summary, if you start with$2^n$, go second. Otherwise go first and pick as many as required to leave behind$2^i$for$i\$ as large as possible! Excellent solution! – Dr Xorile Dec 15 '15 at 0:53
• Update to provide detailed strategy. – user3294068 Dec 15 '15 at 17:47

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

• What do you do if your friend pops any odd multiple of 1024 up to 7,998,464 (7,811 times 1024)? – supercat Dec 15 '15 at 15:28
• Maybe base your response on how many bubbles are left. I had this idea a few days ago, but I didn't have enough time to flesh the whole thing out. – mmking Dec 17 '15 at 2:18
• @mmking: If the player who goes first pops any odd multiple of 1024 (assuming the starting number is an odd multiple of 1024 (16,000,000 is 1024x15625) and plays optimally thereafter, the player who goes second cannot win. – supercat Dec 17 '15 at 22:35