A Number Theory Puzzle
How many lights remain on?
You have a numbered string of 1,000 light bulbs. You begin by flicking them each on.
You go through the string a second time. Now, you flick (off) the switches of all the even-numbered lights.
The odd-numbered lights are shining. The even-numbered lights are dark.
You go through the string a third time, again flicking select switches. However, now it’s lights #3, #6, #9 — all the multiples of three. The on/off pattern of lights becomes a little more complicated.
You can see where this is going.
On your fourth run through the lights, you flick the switch of every fourth light. If a light was on, it’s now off. A light that was off is now on.
You continue in this fashion until you’ve gone through the string a thousand times. On your fifth go, you flick every fifth switch; on the sixth go, it’s every sixth switch, and so forth. On your thousandth (and final) run, you flick only the switch numbered 1,000.
How many lights in the string are left burning?
Have a go at it. Then compare your approach to the solution below.
Solution
This is a variation on a problem from the course on number theory by Brilliant.org [affiliate link]. Their problem features 100 doors, opening and closing. In that version you could conceivably work the problem out by brute force.
That’s not a bad place to start. Let’s see what happens in a few sample positions near the beginning of the string.
Bulb #1 goes on and stays on. We never touch it again.
Bulb #2 goes on during our first pass, when he switch on all the lights. Then, in the second pass, we shut it off, along with the other even-numbered bulbs.
As we experiment, we may notice a pattern. If a bulb has a prime number, we turn it on at the beginning (as with all bulbs). But we only touch it once more, to shut it off. All the prime-numbered light bulbs will finish in the off position.
Consider bulb #12. We hit it on the first go, the second go, the third, fourth, sixth and twelfth goes. That’s six times — an even number. Bulb #12 finishes in the off position.
The numbers 1, 2, 3, 4, 6 and 12 all divide the number 12. These are 12’s only factors. Note that its factors occur in pairs.
Can we pair off the factors of all natural numbers? The answer is a resounding sort of.
We can pair off the factors of 16, but the number 4, in the centre, pairs off with itself. Thus, 16 has an odd number of distinct factors.
This property — having an odd number of factors — is shared by all perfect squares. And only perfect squares.
So, the question of how many lights remain burning amounts to this:
How many perfect squares can we find between 1 and 1,000?
A little number-crunching leads us to this fact:
There exist exactly 31 perfect squares less than 1,000. Thus, 31 lights will remain burning.
Bob’s yer uncle!
Read Medium articles until the cows come home with a Medium membership. (If you use my referral link, I get a piece of the pie.)
