Pop the Last Balloon

A clown approaches you, holding 99 red balloons. He proposes a game where the two of you will take turns popping some nonzero number of balloons. The only restrictions are:

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

Whoever pops the last balloon wins.

The clown gives you the choice of going first or second. Which do you choose, and how do you win?

• If you start and pop one baloon at the time? – Carl Löndahl Dec 14 '15 at 19:00
• wow, yep, I messed that up! – Mike Earnest Dec 14 '15 at 19:33
• Why a clown? Can't Nena do it? – corsiKa Dec 14 '15 at 20:27
• It's too late now, but the question is much more interesting when you start with 96 balloons. – Mike Earnest Dec 14 '15 at 20:36
• @MikeEarnest: I have a strategy for 100. Not sure about 96. – supercat Dec 14 '15 at 21:16

A strategy is:

Go first.
Pop one balloon.

Because

There must be a non-zero number of balloons popped and neither player can pop more than one balloon per turn $\implies$ exactly one balloon is popped each turn, and the odd-numbered player (first player) wins.

• +1 for spoiler tags. Those are a must as long as the site refuses to hide answers automatically. – Almo Dec 14 '15 at 20:34
• @Almo Welcome to Puzzling SE. Spoilers are very common on this site, so please don't upvote solely on the basis of a spoiler being used. Excess usage of spoilers, however, is not recommended, which is why the site does not do it automatically. – ghosts_in_the_code Dec 17 '15 at 9:24
• It was a great answer though. +1 means "thanks" not just the upvote. I just disagree with how this site is structured; I've talked about it on meta before. – Almo Dec 17 '15 at 13:18

For the general case of N balloons, if it's not possible to pop all the balloons, a winning move is...

...pop the largest power-of-two factor of N, if one can do so. This will leave the opponent with a number whose largest power-of-two factor is twice as big, and thus cannot be popped.

If that move is unavailable...

...the player is doomed because any move the player makes will leave a remaining number of balloons whose largest power-of-two factor will be no greater than the number of balloons just popped (thus leaving the other player a winning move).

To understand why this is so...

If the number of balloons was $2^N(2K+1)$ for some integers K and N, and one pops $2^N$, the resulting number of balloons will be $2^{N+1}K$, which will of course be a multiple of a power of two which is too large for the opponent to pop.

Conversely...

If the number of balloons is $2^N(2K+1)$ for some integers K and N, but one cannot pop $2^N$, then one must pop $2^M(2L+1)$ for integers L and M such that $M<N$. That will leave $2^M[2(2^{N-M-1}(2K+1)-(L+1))+1]$ balloons, for the opponent, which would clearly be of the winning form $2^N(2K+1)$ after substituting $M$ for $N$ and $2^{N-M-1}(2K+1)-(L+1)$ for $K$.

• can you give an example? – njzk2 Dec 14 '15 at 22:37
• Not quite a general case. When N is a power of 2, the largest power of 2 that can be popped in the first move is N/2, leaving your opponent the ability to pop N/2 balloons and win. – Ian MacDonald Dec 15 '15 at 15:06
• @IanMacDonald: In that scenario, the largest power-of-two factor of N is too large to pop, so you lose. If you arrive at a power of two in a situation where you are allowed to pop all the balloons, you win. – supercat Dec 15 '15 at 15:10
• Oh, I see what you're saying. Pop the actual largest power of 2 factor, but if you can't, you lose. Got it. – Ian MacDonald Dec 15 '15 at 15:28
• You should structure your answer better. Claim: if you can pop a power of 2 factor of the remaining balloons, you win. Proof: 1. if you do so you opponent cannot do so, 2. if your opponent doesn't do so, you can do so, 3. the one who pops the last balloon does so. (and of course, the number of balloons is finite) – Florian F Dec 15 '15 at 23:01

Spoiler

You go 1st and pop one balloon. You will now always be popping odd balloons, as your partner can only pop 1 (they can't pop more than you) they will always be popping even balloons. You win as you want to pop the last (odd number) balloon.

As previously stated, the strategy for this game is to

go first

and

pop one balloon.

You will win, because

Your opponent's only move is to pop a single balloon. Repeat, and you will eventually pop the last.

General Strategy

This is not correct BTW - but I will leave it as an exercise to the reader as to why. Cheaters can look at the comments!

$N$ is odd

Use the same strategy as the $99$ balloon case: go first and pop one balloon.

$N$ is even

In this case, you must

go second.

On the clown's turn, he will do one of the following:

1. Pop half or more balloons.
2. Pop an odd number of balloons less than half
3. Pop an even number of balloons less than half.

Pops half or more

You win easily by popping the rest.

Pops an odd number of balloons

It is now your turn in an "$N$ is odd" case. So, pop 1 and let the game play out.

Pops an even number of balloons

On your turn, simply pop $2$ balloons.

You win because the clown again has an even number of balloons and he is in the same prediciment as before. Only now his options are limited to popping $2$ (and leaving it even) or $1$ (and making it odd). The moment he pops $1$ you win. Otherwise, you will eventually be left with the last $2$ balloons and get to pop them both to win.

• Start with 14 balloons. Clown pops 2, leaving six pairs of balloons. If nobody ever pops 1, you're on the wrong side of the even-number case. If you pop 1, you'll put yourself on the wrong side of the even-number case. Either way, you lose. – supercat Dec 16 '15 at 16:39
• For a more complex situation, start with 96. Clown pops 32 leaving two groups of 32. No matter what you do, the clown will leave you with an even multiple of however many balloons he pops. – supercat Dec 16 '15 at 17:00
• @supercat Well there goes that theory... Seemed too easy. – Trenin Dec 16 '15 at 18:30