Problem of the Week 1092
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(n1), S(n2), . . . , S(nk) 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:
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:
Source: M. Albert, R. Nowakowski, D. Wolfe, Lessons in Play, AK Peters, 2007.
© Copyright 2008 Andrew Beveridge and Stan Wagon. Reproduced with permission.