Problem of the Week 1092Burnout/SupernovaAlice 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_{1}), S(n_{2}), . . . , 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:
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. |