Getting The Lights Turned On

Step 1: There are no redundancies.

First, any two flicks of a switch is equivalent to nothing. So in total there are $2^4$ possible switches positions (each switch has $2$ positions and there are $4$ switches).

Next, since we can toggle each lightbulb individually somehow, by combining the operations we can toggle any subset of lightbulbs. (Switch operations are commutative and additive.) For example, from the problem, since we can toggle $L_2$ with $S_1, S_2$ and $L_3$ with $S_2, S_3$ , then we can toggle $L_2, L_3$ by $S_1, S_2, S_2, S_3$ , or as we can remove doubles, simply $S_1, S_3$ .

This means we can toggle all $2^4$ possible states: each lightbulb can be in $2$ states and there are $4$ lightbulbs. So we need each possible lightbulbs states to be generated by exactly one switches position. In other words, there are no redundancies.

Step 2: Count.

First, $a_{4,i} = 1$ for all $i$ since $S_4$ toggles everything. Now exactly one of $a_{3,i} = 0$ , since $S_3$ toggles three lightbulbs. There are $4$ ways to determine the one that is $0$ ; now assume $a_{3,4} = 0$ .

$a_{1,4}$ cannot be $1$ . If it is, then $S_1, S_3$ toggles all the lamps, and so as $S_4$ , creating a redundancy. Among the remaining $a_{1,1}, a_{1,2}, a_{1,3}$ , there are $3$ ways to determine the one that is $1$ ; now assume $a_{1,1} = 1$ .

Note that $S_1, S_3$ generates $L_2, L_3$ , and $S_1, S_3, S_4$ generates $L_1, L_4$ . So $S_2$ cannot toggle these two possibilities, else there are redundancies. However, among the remaining four ( $(L_1, L_2), (L_1, L_3), (L_2, L_4), (L_3, L_4)$ ), it can be verified that they all work (generate all possibilities). So there are $4 \times 3 \times 4 = \boxed{48}$ tables we can form.

Consider the table as a matrix, and observe that the $n$ th row has $n$ ones, and the rest of the elements in the row are zeroes. Observe that the condition that each lightbulb has a combination of switches that result in only it being open is equivalent to the condition that a row of 1 0 0 0, 0 1 0 0, 0 0 1 0, and 0 0 0 1 can be obtained through row operations on the matrix, taken modulo 2. One might be tempted to say that this means that as long as a matrix has a nonzero determinant (i.e., can achieve reduced-row echelon formation without any rows of zeroes), that the condition is fulfilled. However, because of how the problem is formed, a row of 2 0 0 0 can not be changed under ordinary matrix row operations to become 1 0 0 0, since 2 0 0 0 is actually 0 0 0 0.

This leads us to consider prohibiting multiplication/division on a row itself. Every other row operation is ok with the problem. Notice how multiplication/division on a row is the only row operation that changes the determinant, while other row operations preserve the determinant. Although switching the rows multiplies the determinant by -1, the matrix is in modulo 2, and essentially, multiplying the determinant by -1 is multiplying the determinant by 1. Since the final determinant (the determinant of $\left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right)$ ) is 1, we wish to consider matrices with a determinant of 1. In this problem, a matrix will satisfy the given condition of the problem iff the determinant of the matrix is 1.

Observe that the fourth row will always be 1 1 1 1. Because of symmetry, we only have to consider when the first row is only 1 0 0 0, and then multiply the number of possible tables by four.

Thus, we have $\left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ a_{21} & a_{22} & a_{23} & a_{24} \\ a_{31} & a_{32} & a_{33} & a_{34} \\ 1 & 1 & 1 & 1 \end{array} \right)$ , where there are two ones in the second row and three ones in the third row. Using the cofactor method to find the determinant, it is clear that the determinant of this matrix is the determinant of $\left(\begin{array}{ccc} a_{22} & a_{23} & a_{24} \\ a_{32} & a_{33} & a_{34} \\ 1 & 1 & 1 \end{array} \right)$ . Using the cofactor method again leads us to find that the determinant is equal to $a_{22}(a_{33}-a_{34})+a_{23}(a_{34}-a_{32})+a_{24}(a_{32}-a_{33}) = 1$ .

Observe that at exactly two of $a_{32}, a_{33},$ and $a_{34}$ must be one. Clearly, at least two of them must be one in order for the third row to have three ones, and three of them cannot be ones, since the determinant then always becomes 0. We can then do simple casework on this third row, and substitute in values into the equation. There are four possible cases of the second row for each case of the third row, and there are three cases of the third row. This then leads to twelve matrices for each possible case of the first row, which there are four of. Thus, there are $4 \cdot 12 = \boxed{48}$ possible tables.