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…
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 matrix with . Also consider the following numbers .
Then is the initial state of the chessboard, where 1 indicates that the light is on and -1 indicates the light is off. If , then the switch for row is hit. Similarly, if , then the switch for column is hit.
So, the sum (we now call ) 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 . 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, .
I’ll attempt to sketch a proof. So let be the chessboard / Hadamard matrix Player A pass to Player B.
First, we let Player B decide and then we consider the matrix where is a diagonal matrix with and is defined similarly. Then it’s not difficult to see that 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 . Well, let and then . 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 submatrix from a Hadamard matrix, then the sum of the submatrix entries is .
Now… what can Player B hope to achieve? Well, if Player A just pass me a matrix (need not be Hadamard), it turns out that Player B can always achieve .
Let Player B randomly choose and let and .
First, , as it is a one-dimensional random walk (waving hands…)…
So, there exists such that . So so so, we pick to have the same sign as , ie . Then and we are done.
Well, as the proof was poorly explained by me, it looks simple. But to come up with the to achieve the lower bound is not simple.
Here, we have a flash version of the game and it’s a 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…