OT Last week's CarTalk puzzler

[Jim Hurley]

For those of you who find beauty in mathematics.

Below is this week's CarTalk puzzle. (A National Public Radio program 
on cars and car repair, hence this beautiful puzzle in number 
theory--don't ask.)

At first I didn't believe Ray theorem (below), so I used Run Rev to 
at least confirm his hypothesis: All numbers with an odd number of 
factors is a perfect square, i.e. the square of an integer, 1, 4, 9 
16, etc. As an example: 16 has as factors, 1, 2, 4, 8 and 16. There 
are 5 factors, an odd number. This implies that the 16'th bulb will 
be switch an odd number of times and therefore will be off if 
initially on, and on if initially off.

Sure enough a little repeat loop shows that the theorem is true. To 
prove it you may find the fundamental theorem of arithmetic helpful, 
i.e. Every integer may be uniquely represented as a product of prime 
numbers.

(20,000 is just an arbitrarily large number.)

Jim


PUZZLER: The Hall of 20,000 Ceiling Lights
There are 20,000 lights on. A person comes through and pulls the cord 
on every second light. A third person comes along and pulls the cord 
on every third light, etc. When someone comes who pulls every 
20,000th chain, which lights are on?

Their solution(?):

The Hall of 20,000 Ceiling Lights
RAY: Let's number all the lights and pick one at random.

TOM: How about 26?

RAY: OK, let's look at light number 26 and figure out if it's going 
to be on or off. All we need to know are the factors of the number 
26. Well what's a factor? A factor is a whole number that will divide 
evenly into another number, with nothing leftover.

So, the factors of 26 are 1, 26, 13 and 2.

Here's why that's important. It tells us that light number 26 is 
going to get its chain pulled four times.

TOM: How did you figure that out?

RAY: Well, when every cord gets pulled it gets turned on, right? 
Light number 26 gets its cord pulled again at 2, which is a factor of 
26.

When every 13th chain gets pulled, light number 26 gets turned on 
again. And it doesn't get touched again until 26, when it gets turned 
off forever.

Now it's pretty obvious then that every bulb that has an even number 
of factors will eventually get turned off for good.

So, which lamps remain on? All those represented by a number with an 
odd number of factors. And those are, are you ready for this? Light 
bulbs 1, 4, 9, 16, 25, 36, etc.

All those numbers are called perfect squares. And only they have an 
odd number of factors, because one of the factors is the square root 
of the number in question. For example, nine has three factors, 1 and 
9 and 3.  [I confess, I can't see how this follows. Jim]

Do we have a winner?

TOM: We do have a winner and the winner this week is Laurie Warner 
from Greer, South Carolina. And for having her answer selected at 
random from among all the correct answers that we got Laurie gets a 
26 dollar gift certificate to the Shameless Commerce Division at Car 
Talk.com, with which she can pick up our new best and second best of 
Car Talk CD pack.