4
$\begingroup$

The question states:

In every square of an $n × n$ board there is a lamp. Initially all the lamps are turned off. Touching a lamp changes the state of all the lamps in its row and its column (including the lamp that was touched). Prove that we can always turn on all the lamps and find the minimum number of lamps we have to touch to do this.

How do I complete the proof for the even case below?

My attempt:

If we spit the problem into odd $n \times n$ cases and even $n \times n$ cases we see the following:

Odd: We can turn every lamp on in a board by simply touching every lamp in one column. Suppose we sequentially touch every lamp in column $C1$. This turns on all lamps in each row (and since they are not affected by consequent moves remain on). The lamps in the column will eventually all be on too because they are affected an odd number of times.

Thus we have a strategy taking $n$ moves. We cannot affect all the lamps in fewer moves and this must be the best strategy for an odd $n$.

Even:

I present a strategy for turning on all lamps:

We can split any $n \times n$ board into blocks of $2\times 2$. For each $2 \times 2$ if we touch each lamp in a clockwise fashion, we turn on all the lamps in that block without affecting all other lamps. We can thus use this strategy for all blocks and turn on all lamps in $n^2$ moves.

Now I have a feeling we cannot beat this strategy (I get this sense because I cannot beat it in the 2x2 case) but am not sure how to prove this strategy cannot be beaten in a more general fashion.

$\endgroup$
1
  • 1
    $\begingroup$ What is the full form for OIM? $\endgroup$ Oct 8 '18 at 1:47
1
$\begingroup$

Your intuition is right.

My arguments can be wrapped up more concisely with the machinery of linear algebra, but let us not use it.

Assume that $n$ is even. Suppose we press the $(i,j)$-th light bulb $a_{ij}$ times. We know that double pressing a bulb does no difference from not pressing it at all, so, to guarantee minimal pressing, we assume $a_{ij}$ is in $\{0,1\}$ for all $(i, j) \in \{1, \cdots, n\}^2$.

Under this restriction there are $2^{n^2}$ combinations of pressing the light bulbs, and there are also $2^{n^2}$ configurations of the status of the light bulbs. Therefore, if we can justify that all configurations of the status can be attained, we can guarantee that the only way to light all bulbs on is to press all the light bulbs.

In particular, it suffices to show that we can light up exactly one light bulb on the board.

  1. If we press the $(1,1)$-bulb, $2n-1$ bulbs will light up: everything on the first column and the first row.
  2. If we press the $n$ bulbs on the first row, all the light bulbs except the first row will be on.
  3. If we press the $n$ bulbs on the first column, all the light bulbs except the first column will be on.

So, if we do the steps 1, 2, and 3 altogether, then...

$\endgroup$
3
  • $\begingroup$ If you press the $n$ bulbs in the first row (column), the result depends on whether $n$ is odd or even. What you describe is only correct when $n$ is even. $\endgroup$
    – Steve Kass
    Oct 8 '18 at 16:58
  • 1
    $\begingroup$ Oh, I think the OP already solved the odd case :) I am only doing it for the even case. $\endgroup$
    – Hw Chu
    Oct 8 '18 at 17:01
  • 1
    $\begingroup$ And by the way, lighting up a single bulb in the odd case is impossible. $\endgroup$
    – Hw Chu
    Oct 8 '18 at 17:06
1
$\begingroup$

Suppose $n$ is even. You have shown that you can light up all $n^2$ bulbs by pressing each one. You want to show that there is no solution requiring fewer than $n^2$ presses.

It is easy to see that no minimal-number-of-presses solution involves pressing a bulb more than once, so your goal is to show that there is no solution where one or more bulbs is never pressed.

Denote a solution as a $0,1$ $n\times n$ matrix $P$ with $1$ indicating “pressed” and $0$ indicating “not pressed.” Suppose there is a solution where the bulb at position $i,j$ was not pressed, that is, a solution matrix $P$ has $P_{ij}=0$ for some particular $i$ and $j$. Then for bulb $ij$ to be on, there must be an odd number of $1$s in row $i$ and column $j$ combined. Consequently, in $P$, the row sum of row $i$ and column sum of column $j$ are of opposite parity and one of them is odd. Without loss of generality (you can transpose the grid and matrix), assume the $i$-th row sum is odd. For this to be true, row $i$ must contain an odd number of $1$s and an odd number of $0$s.

Now, with $i$ the row mentioned above (with row sum odd), consider the column sums of $P$. In a column $k$ where $p_{ik}=0$, there must be an even number of $1$s (think about how never-pressed bulb $(i,k)$ can be on). In a column $\ell$ where $p_{i\ell}=1$, there must be an odd number of ones.

Altogether, there must be an odd number of columns that contain an odd number of $1$s — one through each of the $0$s in row $i$. Thus the total number of $1$s in the entire matrix $P$ must be odd.

Now, each bulb press changes the parity of $2n-1$ bulbs, an odd number, so the assumed solution accomplishes an odd number of parity changes. However, the total change in parity from “all off” to “all on” must turn an even number of bulbs from off to on, which requires an even number of parity changes. This is a contradiction, so no bulb can be unpressed in a solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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