Problem of the Week 1092

Burnout/Supernova Solution

MacPOW Home || Math Forum POWs || Search MacPOW

Solution

Burnout/Supernova is an example of a combinatorial game. It can be shown that this impartial game is equivalent to Nim. One can use the corresponding machinery (nimbers, etc.) to analyze Burnout/Supernova, but the solution we include here is self-contained. Correct solutions were submitted by John Guilford, Aaron Dunigan AtLee, Joe DeVincentis and Piotr Zielinski.

If there is one star, then Alice wins via a supernova.

Let's call a star even or odd, depending on the number of radial nodes. If there are multiple stars, then Bob (the second player) wins if there are even numbers of both even and odd stars. Otherwise Alice wins. Basically, if you start with an even number of both types, the other player can guarantee that you continue to see an even number of both types on every turn.

• If there is an even number of both even stars and odd stars, then a Supernova changes the parity either the even or odd stars. A Burnout changes the parity of both to odd.
• If one type of star occurs with odd parity, then a Supernova on a star of that type leaves an even number of both types.
• If both types occur with odd parity, then a Burnout on an even star leaves an even number of both types.

Clearly, if you never see an odd number of stars of one type or another, you cannot be the person to remove the final star.

[Back to Problem 1092]

© Copyright 2008 Stan Wagon. Reproduced with permission.