I found this great puzzle hidden in an app aimed at children.
There are 300 lightbulbs in a row, labelled 1 to 300, each with an on/off switch. We count from 1 to 300 and flick the switches as follows: on “1” all lightbulbs are switched on. On “2” lightbulbs 2, 4, 6, 8 etc. and switched (turning them off). On “3” lightbulbs 3, 6, 9 etc. are switched. If a lightbulb is on when switched it goes off (and vice versa). How many lightbulbs are on by the time we get to “300”?
Skip to the solution.
If you want to work it out, don’t scroll down!
Some blurb as a digression so that you don’t see the solution immediately
The funny thing about this puzzle was that it was far too difficult for a child’s game. The question prompted the user to click on something for help, which in turn advertised a service that sells solutions for maths homework (such is the way of things). So it needed to be complicated enough to get users clicking. However the puzzle is easily solvable, without resorting to a brute force approach.
The method of solving was as interesting to me as the puzzle itself. My first thoughts were is it a simple solution: is it 0, 1 or 300? Well, no, no and no. Since we know that lightbulb 1 stays lit, 2 and 3 are off and 4 is on by the time we have got to the “4” switching. This thought was enough to find the solution…
The solution
There are 17 lightbulbs lit after all the switching.
The answer comes from a simple observation: for a lightbulb to be lit, it needs to have been switched an odd number of times. Bulbs that are off will have been switched an even number of times. The switching process (all the 1s, all the 2s and so on) represents factorisation. For example, lightbulb 8 is switched on by “1”, off by “2”, on by “4” and off by “8”. The factors of 8 are 1,8,2,4. All numbers have an even number of factors, except square numbers. So the question becomes how many square numbers are there between 1 and 300? 17 x 17 = 289 and so the answer is 17 lightbulbs are lit.
—
The post title comes from “Puzzles Like You” from the album of the same name by Mojave 3.