Problem of the Week 1092

Burnout/Supernova

Alice and Bob decide to play a game called Burnout/Supernova. Alice goes first.

A star graph consists of a single central vertex, some number of radial vertices, and one edge between the the central vertex and each radial vertex. Let's denote a star with n radial nodes by S(n) and think of n as the size of the star.

Here is a picture of stars S(1) through S(6):

Burnout/Supernova starts with a set of disjoint star graphs S(n₁), S(n₂), . . . , S(n_k) all of size at least 1. This means that each star has at least one radial vertex along with its central vertex. A turn consists of removing a single vertex, along with any edges incident to the removed vertex.

On each such star, there are two types of moves:

• Burnout: Remove a radial vertex, decreasing the size of the star by 1.
• Supernova: remove the central vertex, leaving a set of isolated vertices on which no further moves are possible. (These isolated vertices are discarded.)

The winner is the person who makes the last move.

Note that on S(1), you can only perform a Supernova.

Who wins Burnout/Supernova when the game consists of:

1. one star S(n)?
2. two stars S(n₁) and S(n₂)?
3. k stars S(n₁), S(n₂), ... , S(n_k)?

Source: M. Albert, R. Nowakowski, D. Wolfe, Lessons in Play, AK Peters, 2007.

© Copyright 2008 Andrew Beveridge and Stan Wagon. Reproduced with permission.