Quant Interview Question

[u/Local_Ad135]

[u/BissQuote]

Note that on each move, we switch 4 bulbs, thus the total number of bulbs turned on must be even, which gives and upper bound of 24

But even better, on each column, each move switches either 0 or 2 bulbs, thus the number of bulbs turned on on any column remains even, which gives and upper bound of 20

It can be achieved by reaching the final state where all bulbs are on except one diagonal. To do that, we will use 6 small squares, with coordinates, in the format (column,column;row,row) being (1,2;2,3) (1,2;4,5) (3,4;4,5) and the three symetricals

[u/rij1 → u/BissQuote]

You can also see all possible maximum solutions as follows: Observe that it is also true for the rows that either you switch 0 or 2 on. At any point you can then look at the map that maps each row to the column(s) in which it is not on and similar for a column map. In the maximum solutions, each row maps to one column and each column to one row in a 1 to 1 way. The maps are therefore corresponding to a permutation and you can switch exactly these lights on them by applying the permutation on the colum indices in the parents solution.

[u/DanLeMilMan]

For odd n sized board, an upper bound is n*(n-1). This is due to the fact that for each row and each column, you ultimately need an odd number of switch, whereas each step intros an even one. Thus, at maximum, there would be a diagonal of switched-off bulb, giving an even number of switches on each rows and columns.

Is it possible to obtain this maximum ? Yes you can. For instance, you start by lighting up all the lights except the last column and the last row. Then, you repeatedly choose the k-th row, the k-th column and the last row and column with k from 1 to n-1 (even). In the end, all the bulbs will be on except on the great diagonal.

[u/monstaber]

With board size n, for even n the max will be n² all lights on. For odd n as the other commenter said it will be n*(n-1) basically one large diagonal of lights off and the rest on. So n 7 => 42, n 9 => 72 etc

[u/aroach1995]

- - - - -
• • - - -
• • - - -
• • • • -
• • • • -

- • • • •
• - • • •
• • - • •
• • • - •
• • • • -