## May 2023

—————————

In the Math Corner of my May 2023 Diary I offered the following brainteaser.

There are 100 light bulbs lined up in a row in a long room. Each bulb has its own switch and is currently switched off. The room has an entry door and an exit door. There are 100 people lined up outside the entry door. Each bulb is numbered consecutively from 1 to 100. So is each person.

Person No. 1 enters the room, switches on every bulb, and exits. Person No. 2 enters and flips the switch on every second bulb (turning off bulbs 2, 4, 6,...). Person No. 3 enters and flips the switch on every third bulb (changing the state on bulbs 3, 6, 9...). This continues until all 100 people have passed through the room.

How many of the light bulbs are illuminated after the 100th person has passed through the room?

—————————

**• Solution**

Obviously a bulb will be illuminated after the 100th person has passed through the room iff (sorry: math shorthand for "if and only
if"), in the passage of those 100 people, its switch was flipped an *odd* number of times: 1 time, 3 times, 5 times, …, 99
times.

Now the number of times any particular bulb — say bulb number *n* — has its switch flipped is just the number
of different factors *n* has. Person number *x* flips switch number *n* iff *x* divides exactly into *n*.

The factors of 28, for example, are 1, 2, 4, 7, 14, and 28. That's six factors, and six is an *even* number, so bulb number 28
*won't* be illuminated after the 100th person has passed through the room. It got flipped six times.

Those factors go in pairs. 1 times 28 is 28; 2 times 14 is 28; 4 times 7 is 28.

So … what numbers *don't* have an even number of different factors? What numbers' factors *can't* be arranged in
pairs like that?

Answer: perfect squares. Consider 36, for example, which is the square of 6. Factors: 1, 2, 3, 4, 6, 9, 12, 18, 36. The number of
*different* factors is odd because to pair them off you'd have to include 6 times 6; but person number 6 only gets one opportunity to flip
the switch for bulb number 36.

So after the 100th person has passed through the room the only lights illuminated are the ones whose numbers are perfect squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.