Unbalancing Lights aka Gale-Berlekamp Switch Game

Posted: September 12, 2010 in Lectures, Probabilistic method

Image from gizmodo.com

This post is a short excerpt from lecture 3 and 4.

Let us consider the above “chessboard”-like switchboard. U see that there are switches on both sides. Each switch control its corresponding row or column… Should be quite clear from the diagram. So if u hit the switch, then all the “off” lights in the row/column will turn “on” and the “on” lights in the row/column will turn “off”. The goal is to: maximise the number of lights on, or minimise the lights off, or to maximise the difference between the lights on and off… all almost equivalent objectives…

Well… the game is also known as the Gale-Berlekamp game (named after two famous combinatorial game theorists from UC Berkeley). n the game can be turned into a two player game with some variations.

I. Player A and B hit the switches in alternating turns. Player A will hit only the rows and Player B hit the columns. The player who cannot increase the number of lights on wins.

II. Player A sets the initial state of the lightbulbs and presents to Player B.  Player B will then try to maximise the number of lightbulbs to be switched on.

I found Variation I from this site, which reported on Microsoft ‘s Techfest in 2009. Havent really considered the solution.

Variation II was given as Homework II and interestingly uses Hadamard matrices.

Let us reformulate the problem. Consider the n\times n matrix A=(a_{ij}) with a_{ij}=\pm 1.  Also consider the following numbers x_1,\ldots ,x_n,y_1,\ldots ,y_n=\pm 1.

Then A is the initial state of the chessboard, where 1 indicates that the light is on and -1 indicates the light is off. If x_i=-1, then the switch for row i is hit. Similarly, if y_i=-1, then the switch for column i is hit.

So, the sum \sum a_{ij}x_iy_j (we now call \Delta) is the difference between lights on and lights off. ie the quantity which we or Player B hopes to maximise.

Ok. Suppose a Hadamard matrix exist for n. So Player A will set the initial state of the chessboard accordingly and pass it to Player B. And… no matter what Player B do, \Delta\le n^{\frac{3}{2}}.

I’ll attempt to sketch a proof. So let A be the chessboard / Hadamard matrix Player A pass to Player B.

First, we let Player B decide x_1,\ldots, x_n, y_1, \ldots, y_n and then we consider the matrix X=(x_{ij}) where X is a diagonal matrix with x_{ii}=x_i and Y is defined similarly. Then it’s not difficult to see that XAY is the end state after the switches and that the resulting matrix is still a Hadamard matrix.

So, we just need to show that the sum of the entries of a Hadamard matrix does not exceed n^{\frac{3}{2}}. Well, let c=(1,\ldots,1) and then \Delta=cXc^T. Then, using Cauchy Schwarz inequality and the fact that Hadamard matrices are orthogonal, we obtain our result (hands waving furiously…)

Anyway, the last para also gives a sketch of the proof of the Lindsey’s Lemma, which states that if we pick a a\times b submatrix from a n\times n Hadamard matrix, then the sum of the submatrix entries is \le \sqrt{abn}.

———————————–

Now… what can Player B hope to achieve? Well, if Player A just pass me a n\times n matrix A (need not be Hadamard), it turns out that Player B can always achieve \Delta\ge (\sqrt{\frac{2}{\pi}}+o(1))n^{\frac{3}{2}}.

Let Player B randomly choose y_1,\ldots, y_n=\pm and let R_i=\sum a_{ij}y_j and R=\sum |R_i|.

First, E(|R_i|)=(\sqrt{\frac{2}{\pi}}+o(1))\sqrt{n}, as it is a one-dimensional random walk (waving hands…)…

Then, E(R)= E(|R_1|)+\ldots E(|R_n|)=(\sqrt{\frac{2}{\pi}}+o(1))n^{\frac{3}{2}}

So, there exists y_1,\ldots,y_n such that R=|R_1|+\ldots+|R_n|\ge (\sqrt{\frac{2}{\pi}}+o(1))n^{\frac{3}{2}}. So so so, we pick x_i to have the same sign as R_i, ie |R_i|=x_iR_i. Then \Delta=R and we are done.

Well, as the proof was poorly explained by me, it looks simple. But to come up with the y_i to achieve the lower bound is not simple.

Here, we have a flash version of the game and it’s a 10\times 10 version of it. (Note: the goal is to MINIMISE the lights ON…)

So, by the theorem / proposition, we can make sure less than 30 lights are on (less than 3 per row). Pls try and tell me a nice algorithm to achieve this…

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s