Imagine two players, Alice and Bob, competing on a square grid with n rows and n columns. Each cell in the grid contains a light bulb, which can be either off or on.
Alice goes first. Her role is to choose the grid's initial configuration: how many bulbs are lit and where they are located. Bob has access to switches at the end of every row and column (so there are 2n switches altogether). Flipping one of them reverses the states of the bulbs in the corresponding row or column: bulbs that were on go off, and those that were off come on. Bob may operate any of these switches, in any order, for as long as he wishes.
Bob's goal is to end the game with as few bulbs lit as possible—in other words, he seeks to minimize the number of lit bulbs in the final configuration. Alice, conversely, wants as many bulbs as possible to remain lit at the end of the game: she seeks to maximize the minimum number of lit bulbs Bob can achieve after any number of switch operations.
A bright little game
--------------
To get a better feel for the game, let us warm up with a grid of side length n = 3. Suppose Alice gives Bob the initial configuration shown opposite, where white circles represent bulbs that are off and black circles bulbs that are on.
