The puzzler about 20000 lights seemed to have a setup without an actual problem/puzzle to answer. Can anyone fix it or tell me what it’s supposed to say or explain what the question is?
same here. i was like what on earth is the question
I was going to ask the same question of what was the question??
Seems that geoffhazel beat me by 6 minutes.
I found it. Rerun of a puzzle from 2011:
When that happens, some lights will be on, and some will be off. Can you predict which lights will be on?
this part was on the new one when I went and checked, so someone must have figured out they left it off. 
It’s the puzzler on the most recent podcast, 2.9.19.
https://www.cartalk.com/puzzler/hall-20000-lights
This is how the question ends …
"Now, a third person comes along and pulls the cord on every third light. That is, lights number 3, 6, 9, 12, 15, et cetera. 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 ones will be on?"
Anytime the puzzler is a non-automotive question I just ignore it.
Like if a train leaves Chicago traveling at 30 MPH, how many pancakes does it take to shingle a roof?
Purple!
2 Likes
This is sort of an interesting puzzler for math-types, which Ray and Tom tend toward. The answer must be closely related to the ancient Eratosthenes Sieve algorithm, so the answer likely has to do with prime numbers. They have a sculpture at nearby (to me) Stanford University, a huge Eratosthenes Sieve, which I enjoy visiting whenever I go there for a walk-a-bout.
I don’t think it relates to prime numbers. Write out the numbers from 1 to 36 and mark a 1 under the number of each light when it is turned on and 0 each time it is turned off. You will see what is happening.
You can read the sol’n now, it’s recently been posted to the puzzler section. Definitely has a prime number aspect. It’s a question of how many factors a number has, a factor could be prime or non-prime. But it is easier to figure out how many by starting with the prime factorization. The “sol’n” Ray gives is sort of a hand-waving argument. I think the proof for all possible numbers is probably quite complicated. But here’s how I think about it.
Any small perfect square number (4, 9, 25 , 36 … ) has a prime factorization of p^n * q^m where both n and m are even numbers. For example 36 = 2^2 * 3^2. 36 has these 3 groups of factors
group A: 2^1, 2^2
group B: 3^1, 3^2
So there’s 2 + 2 = 4 factors total for A and B
group C is all the cross terms of A * B (e.g. 2^1 * 3^2, etc), for which there are 2 * 2 factors = another 4 from C, totally 8 total factors for the number 36. [I’m ignoring 1 as a factor.]
In general for a number of the form p^n * q^m
there are n+m + n*m total unique factors (by the reasoning above)
If n & m are both even, then n+ m is even, and n*m is even, and the sum of two even numbers is even, so there are always an even number of factors for perfect squares.
If either n or m is an odd number, then n+m is an odd number (e.g. 3+4 = 7), and n * m is an even number (e.g. 3 * 4 =12). An odd number plus an even number is always an odd number (e.g. 7+12 = 19), so all numbers with a single odd exponent will have an odd number of factors. It’s easy to show this is the case if both exponents are odd too.
It becomes more complicated for numbers of the form p^n * q^m * r^o b/c there are now three groups of the first type, and therefore two types of cross products to consider. But it is still pretty easy to see why they’ll be an even number of factors if all three of n, m, and o are even. It starts to become complicated however for the odd factor cases. And showing this is true for any number at all must require some tricks I don’t have in my maths bag.
@George_San_Jose1. I didn’t take “Theory of Numbers” in my math major curriculum. I am sure there is a formal proof. I like your analysis. I just wrote out the integers from 1 to 100 and realized the lights that remained on were numbered with perfect squares. I remembered solving this puzzler when Tom and Ray originally presented it.
I liked this puzzler.
1 Like