Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a combinatorics-probability question, best stated however in "recreational" terms. Imagine a $N\times N$ city, meaning that we have $N$ horizontal streets, and $N$ vertical streets. At each crossroads there is a street light.

When evening comes, some of the lights are switched on, namely those corresponding to a certain given subset $E\subset(1,\ldots,N)\times(1,\ldots,N)$.

Now assume that $2N$ kids come at night and start randomly playing with the switches: there is one such on/off switch at the end of each of the $2N$ streets.

Problem: for each of the $4^N$ overall choices for the various switches, we count the number $K$ of street lights that are switched on. What is the law of this random variable $K$, as a probability measure on $(1,2,\ldots,N^2)$, depending on the initial set $E$?

[Edit, Jan 20. As signaled by Joseph O'Rourke in his answer below, computing the upper edge of the support of the measure $\mu_E$ in my problem is known as the Gale-Berlekamp game, a difficult question (details can be found via Google search). So I realise that my problem is probably extremely difficult, adding the "open-problem" tag. I'd be interested however in the case where $E$ is an Hadamard matrix, cf. discussion with Gerhard Paseman in the comments below. Is there anything known about this measure $\mu_E$? (I mean, not only about its support.)

Btw here is the only non-trivial complete computation that I have so far: concerns the case $N=4$, where there are exactly $|E|=4$ street lights, positioned on the main diagonal of the city. Here $\mu_E=\frac{1}{32}(\delta_4+12\delta_6+6\delta_8+12\delta_{10}+\delta_{12})$. Plus an experimental remark, that I'm not able to prove abstractly: the support of $\mu_E$ seems always to be an arithmetic progression.]

share|cite|improve this question
This vaguely reminds me of a calculation I thought about a few months ago... unfortunately I don't recall getting further than the formulation and some attempts at calculating moments. –  Yemon Choi Jan 19 '13 at 18:52
In my opinion, the switch behaviour is underspecified. You will get different distributions depending on whether the switches toggle, force an on, or force an off. This is similar to counting equivalence class sizes for 0-1 matrices, see a 2005 arXiv paper of Miodrag Zivkovic for n less than 10. Gerhard "Ask Me About Determinant Spectra" Paseman, 2013.01.19 –  Gerhard Paseman Jan 19 '13 at 19:54
I am not sure I would be so happy to be thanked in a paper by Berlusconi (unless your name actually happens to be Berlusconi, in which case I apologize for the joke). –  Angelo Jan 19 '13 at 19:57
Perhaps Gerhard meant the paper, "Classification of small $(0,1)$ matrices" arXiv:math/0511636 –  Joseph O'Rourke Jan 19 '13 at 23:04
Berlusconi, I invite you to find my registered MathOverflow user page and figure out my email address (alternatively, kindly ask Will Jagy for a redirect). I am quite willing to elaborate over email. Also, the file is not immediately reachable: it is part of a URL-indexed archive affectionately called "The Wayback Machine", from an old cartoon of Mr. Peabody and his pet boy Sherman. Gerhard "Is It On DVD Yet?" Paseman, 2013.01.19 –  Gerhard Paseman Jan 19 '13 at 23:34

1 Answer 1

up vote 12 down vote accepted

This paper by P. C. Fishburn and N. J. A. Sloane seems quite related:

"The Solution to Berlekamp’s Switching Game." (PDF download)

Abstract. Berlekamp’s game consists of a $10 \times 10$ array of light-bulbs, with $100$ switches at the back, one for each bulb, and $20$ switches at the front that can complement any row or column of bulbs. For any initial set $S$ of bulbs turned on using the back switches, let $f(S)$ be the minimal number of lights that can be achieved by throwing any combination of row and column switches. The problem is to find the maximum of $f(S)$ over all choices of $S$. We show that the answer is $34$. We also determine the solution for $n \times n$ arrays with $1 \le n \le 9$.

           (Image from this link.)

share|cite|improve this answer
Notice that the authors of the paper claim that the paper mentioned gives an incorrect answer... –  Ilya Bogdanov Sep 22 at 10:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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