Alice and Bob play a game with an 8×8 grid of lights, all initially on. They take turns choosing a light which is on and turning it off, with Alice going first. However, the grid is rigged such that choosing a light toggles the entire 3×3 square to its bottom and left. Therefore, nine lights are toggled each turn, unless the selected light is close to the bottom or left border. If a player turns off all the lights, they lose.

Does this game favor Alice or Bob?
What is the optimal strategy of the winning player?

  • 1
    $\begingroup$ So the light is never toggled back on if it is on the leftmost column or lowest row? $\endgroup$ – micsthepick Mar 10 '17 at 5:12
  • $\begingroup$ @mics No, the 3x3 square includes the square chosen, as shown in the picture. $\endgroup$ – boboquack Mar 10 '17 at 5:49

The winner is


The winning strategy

is anything, every path leads to victory.

To see this,

note the $9$ lights at coordinates with residues $(0,0)$ modulo $3$, where $(0,0)$ is the bottom left. oooooooo XooXooXo oooooooo oooooooo XooXooXo oooooooo oooooooo XooXooXo
Every move toggles exactly one of these lights. So, after Alice's moves, an even number of them are on, and after Bob's move, an odd number are on. Since none are on when the game ends, Alice must have just moved and lost.
For completeness, we show the game must end. Assign the light at $(x,y)$ a weight of $100^{x+y}$. Each move decreases the total weight of on lights because a light turns off, and any changes in lights to its bottom and left are much too small to offset the decrease. So, the game must terminate.

  • 1
    $\begingroup$ Very nice! I had been thinking that this was essentially a kind of Nim game, and trying to find which positions are safe (i.e. have Sprague-Grundy number zero - if you leave this position then any move the opponent does loses), but not getting very far. Your answer cuts through all of that. $\endgroup$ – Jaap Scherphuis Mar 10 '17 at 13:12
  • $\begingroup$ Wait, after Alice moves, shouldn't there by an odd number of said lights on? $\endgroup$ – greenturtle3141 Mar 10 '17 at 20:36
  • $\begingroup$ @greenturtle3141 We start with all 9 of them on, then Alice moves first and flips one, now 8 of them are on. $\endgroup$ – xnor Mar 10 '17 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.