17
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Yemon Choi
    Jan 19, 2013 at 18:52
  • 4
    $\begingroup$ 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 $\endgroup$ Jan 19, 2013 at 19:54
  • 3
    $\begingroup$ 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). $\endgroup$
    – Angelo
    Jan 19, 2013 at 19:57
  • $\begingroup$ Perhaps Gerhard meant the paper, "Classification of small $(0,1)$ matrices" arXiv:math/0511636 arxiv.org/abs/math/0511636 $\endgroup$ Jan 19, 2013 at 23:04
  • 1
    $\begingroup$ 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 $\endgroup$ Jan 19, 2013 at 23:34

1 Answer 1

15
$\begingroup$

This paper by Fishburn and Sloane seems quite related:

Fishburn, Peter C., and N. J. A. Sloane. "The solution to Berlekamp's switching game." Discrete Mathematics 74.3 (1989): 263-290. (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$.


           Berlekamps
           (Image from this link.)

$\endgroup$
1

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.