Aenigma

25 Feb, 2023

I came across the following puzzle this morning:

A 10-story building has 10 rooms per floor, all facing forward. A single lamp illuminates each room. A switchboard in a rental office near the building has 100 switches to control the 100 lights. The lights start in the 'all off' state, but 100 people walk through the rental office and tamper with the switches. The first person toggles every 1st switch (thus turning all lights on). The second person toggles every 2nd switch (this turning half the lights off). The third person toggles every 3rd switch. The fourth person toggles every 4th switch. And so on for all 100 persons. Which lights are now on, and which are off?

Let's reason about the puzzle and see if we can grab some intuition before actually writing some code:

Let L be a list of 100 elements representing the following states:

• L_i = 1 if the i-th light is on
• L_i = 0 if the i-th light is off.

Initially, L is a list of 100 zeros: L = [0,0,...0], i.e all the lights are off. Per the puzzle, every person will individually toggle the switches.

We can represent this with a for loop as follows:

for i in range(1, 101):

In our case, each one of them will toggle the j-th switch if j is a multiple of i. We can represent this operation using the XOR operator (^)[PS] as follows:

L_j = L_j ^ (j % i == 0)

The XOR operator toggles the j-th light if j is a multiple of i.

We iterate through all the togglers w/ the following for-loop:

for j in range(i-1, 100, i): L_j = L_j ^ 1

At the end of this process, we'll get the following results:

• the lights that are on are those with an odd number of toggles
• the lights that are off are those with an even number of toggles.

Now, we can simply represent the state of each light using the parity of its number of toggles:

L_j = 1 if the number of toggles of the i-th light is odd
L_j = 0 if the number of toggles of the i-th light is even

Then we compute the parity of the number of toggles using the modulo operator (%) w/ 2 since there are only two states (on | off):

L_j = sum((j % i == 0) for j in range(1, 101)) % 2

The final state of the lights can be represented as a list of 100 elements L = [L₁, L₂, ..., L₁₀₀], where the following is true:

• L_j = 1 if the i-th light is on and
• L_j = 0 if the i-th light is off.

Here's the code

Happy hacking!

#logic #puzzles #python