From Car Talk.

RAY:This puzzler is from my “ceiling light” series. Imagine, if you will, that you have a long, long corridor that stretches out as far as the eye can see. In that corridor, attached to the ceiling are lights that are operated with a pull cord.There are gazillions of them, as far as the eye can see. Let’s say there are 20,000 lights in a row.

They’re all off. Somebody comes along and pulls on each of the chains, turning on each one of the lights. Another person comes right behind, and pulls the chain on every second light.

TOM:Thereby turning off lights 2, 4, 6, 8 and so on.

RAY:Right. Now, a third person comes along and pulls the cord on every third light. That is, lights number 3, 6, 9, 12, 15, etcetera. Another person comes along and pulls the cord on lights number 4, 8, 12, 16 and so on. Of course, each person is turning on some lights and turning other lights off.If there are 20,000 lights, at some point someone is going to come skipping along and pull every 20,000th chain.

When that happens, some lights will be on, and some will be off. Can you predict which lights will be on?

I created a Python program that prints the lights that are on (I got stumped trying to figure it out, and for some reason this method was easier for me). Found here.

I like this problem a lot because you can get stumped holding onto the on/off value of 20,000 lights, or you can focus on the underlying patterns. This is the sort of problem that’s accessible for students of any age (depending on how it’s structured), and even a pretty sweet college level problem to prove.

It’s all about the # of divisors. A light will be turned on by one of it’s divisors and off by the other (for example, 15 would be changed by 1 and again by 15). With that in mind, it comes down to those numbers with an odd number of divisors, aka. the perfect squares.