Geometric Variants of the Gale--Berlekamp Switching Game

The Gale–Berlekamp switching game is played on the following device: Formula: see text is an Formula: see text array of lights controlled by Formula: see text switches, one for each row or column. Given an (arbitrary) initial configuration of the board, the objective is to have as many lights on as possible. Denoting the maximum difference (discrepancy) between the number of lights that are on minus the number of lights that are off by Formula: see text, it is known (Brown and Spencer, 1971) that Formula: see text, and more precisely, that Formula: see text. Here we extend the game to other playing boards. For example: (i) For any constant Formula: see text, if Formula: see text switches are conveniently chosen, then the maximum discrepancy for the square board is Formula: see text. From the other direction, suppose we fix any set of Formula: see text column switches, Formula: see text row switches, where Formula: see text and Formula: see text. Then the maximum discrepancy is at most Formula: see text. (ii) For a board Formula: see text, let Formula: see text and Formula: see text. Given a board Formula: see text with Formula: see text lights, for some constant Formula: see text, we show that the maximum discrepancy is Formula: see text. This is a generalization of the Brown and Spencer result for the original game. (iii) If Formula: see text consists of the elements of Formula: see text below the hyperbola Formula: see text, then its maximum discrepancy is Formula: see text and Formula: see text.