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].