11
$\begingroup$

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?

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

1 Answer 1

Reset to default
13
$\begingroup$

The winner is

Bob

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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Mar 10, 2017 at 13:12
  • $\begingroup$ Wait, after Alice moves, shouldn't there by an odd number of said lights on? $\endgroup$
    – greenturtle3141
    Commented Mar 10, 2017 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
    Commented Mar 10, 2017 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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