14
$\begingroup$

This is a modification to the usual 100 lightbulbs in a room puzzle.

  • Like before, the first person flips the switch of every lightbulb.

  • However, while the second person also starts from the first bulb and flips the switch of every second lightbulb, they do not stop at the 100th lightbulb. Rather, after the $100^\text{th}$ bulb, they continue on to the $[100+2\pmod{100}]^\text{th}$ (i.e. second) and keeps flipping every second bulb still until the total number of bulbs they have flipped is 100.

  • Similarly, the third person flips the switch of every third lightbulb, but does not stop at the $99^\text{th}$ bulb, they continue to the $[99+3\pmod{100}]^\text{th}$ (i.e. second again) bulb and continues until the total number of bulbs they have flipped is 100.

  • The general rule is that the $n^\text{th}$ ($1\leq n\leq 100$) person flips the $[kn\pmod{100}]^\text{th}$ for $1\leq k\leq 100$.

This carries on until all 100 people have flipped 100 bulbs each. The task is to find the bulbs which are switched on at the end.

I've written a script that determines which ones are:

arr = [0 for _ in range(100)]
for i in range(1,101):
    for j in range(1,101):
        bulb = i*j
        bulb = bulb%100
        arr[bulb-1] += 1
        arr[bulb-1] = arr[bulb-1]%2
print(arr)

and get that no bulbs are left switched on at the end. However, I find it hard to think of a way to answer this problem logically, and also generalise to say $N$ bulbs. How should I approach this question?

New contributor
Ice Tea is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • 1
    $\begingroup$ Is there a bug in the Python code? bulb = bulb%100 can return 0, and then arr[-1] is accessed. $\endgroup$
    – nanoman
    Oct 14 at 5:21
  • 2
    $\begingroup$ @nanoman in Python arr[-1] refers to the last element. And if bulb%100=0 we indeed want to access the 100th bulb. $\endgroup$
    – justhalf
    Oct 14 at 10:45
  • $\begingroup$ Does ( 100+2 ) mean going back to the start to make Bulb 1 stand for Bulb 101, or what? In either the original puzzle or this variant, does Person 1 flipping every switch serve any purpose other keeping the instructions clear and consistent? $\endgroup$ 2 days ago
23
$\begingroup$

In general:

Let's say there are $B$ bulbs. Since $B-n ≡ -n$ modulo $B$, person $B-n$ will perform exactly the same flips as person $n$, but in a different order.

So the only people without partners will be person $B$, and person $B/2$ (if they exist). Person $B$ flips the last bulb $B$ times, and person $B/2$ flips both the $B/2$th bulb and the last bulb $B/2$ times. So the result depends on the value of $B$ modulo 4:

If $B≡0$: Both people flip their bulbs an even number of times, so all bulbs are off.
If $B≡2$: Person $B$ flips the last bulb an even number of times, so they do nothing. Person $B/2$ flips their two bulbs an odd number of times, so bulbs $B$ and $B/2$ are on.
If $B≡1$ or $B≡3$: The second person doesn't exist, and the first person flips their bulb an odd number of times, so only the last bulb is on.

$\endgroup$
3
$\begingroup$

With 100 bulbs:

For every number 1-49, there is a number that flips all of the same bulbs, but in reverse. For example, person 1 flips every bulb from 1 to 100. Person 99 flips every bulb starting at 99, working down to 1, then ending, as every person will, at bulb 100. This means that for 1-49 and 51-99, no bulbs will be left on. The only people left are 50 and 100. 100 flips the last bulb 100 times, leaving it off, and 50 flips 50 and 100 repeatedly. This results in 59 times for each bulb, and they both remain off. Therefore, after every person has gone, all the bulbs will be off.

For $n$ bulbs:

If $n$ is even, similar logic to above can be used. For odd prime numbers, the last bulb will be the only one remaining lit, with each person except the last flipping every bulb in some order.

$\endgroup$
1
  • 1
    $\begingroup$ It doesn't matter if the number is prime or composite - the result is the same either way. $\endgroup$
    – Deusovi
    Oct 12 at 23:00

Your Answer

Ice Tea is a new contributor. Be nice, and check out our Code of Conduct.

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.