Is there a formula for this?

“Imagine a corridor with 100 light switches.

100 people walk through the corridor one after another. The first person flips on every switch, the second person flips every other switch (starting with the second), the third person flips every third switch (starting with the third), etc.

At the end, which switches are on and which are off?”

The first switch would be on. All the other switches with an even number of factors (including 1) would be off. All the switches with an odd number of factors (including 1) would be on.

I don’t know if it’s a formula, really, but here goes. By the way, the problem’s inventors were very nice to have the second person start with the second door, rather than the first, before flipping ever other switch.

Just figure out how many numbers each number is divisible by. If the number is even, the light should be off. If the number is odd, it should be on. Assuming the lights were all off to begin with.

So, each prime number is off; 1 is on; 4 will be on since the first, second, and fourth people toggled it, etc. I think the problem is just a way of making you figure out how many factors each number has.

And to add to what the others have said, what actually happens is that the perfect squares (1,4,9,16,…) will be left on, all the others will be off.

…ebius sig. This is a moebius sig. This is a mo…

(sig line courtesy of WallyM7)

Whoa. Too many numbers!

But it’s easy to figure out: only perfect squares have an odd number of factors.

rocks

Think about it this way:

All we really need to know is what happens to the first six switches. After that everyone starts over with switch seven-- the first person still turns everything on, the second person still flips every other switch starting with the second, and the third person still flips every third switch starting with the third.

So we have

- on
- off (second person got it)
- off (third person got it)
- off (second person got it)
- on
- on (second and third people got it, flip it twice and it’s on again)

For the rest of the switches all we need to know is the switch number mod 6. If it’s 1, 5, or 0 (6 mod 6) then the switch is on, otherwise it’s off.

Some damn fool didn’t read the OP correctly and missed the etc…

So the number of factors theory is correct. Since I no longer have confidence in my ability to think clearly this morning:

#include <iostream.h>

int main(int argc, char **argv)

{

int i,j;

int switches[100];

```
// first person
for (i = 0; i < 100; i++)
switches* = 1;
// now second and subsequent people
for (j = 1; j < 100; j++)
for(i = j; i < 100; i += j + 1)
switches* = !switches*;
for (i = 0; i < 100; i++)
cout << "Switch " << (i + 1) << ": " << (switches* ? "ON" : "OFF") << endl;
return 0;
```

}

results in

Switch 1: ON

Switch 2: OFF

Switch 3: OFF

Switch 4: ON

Switch 5: OFF

Switch 6: OFF

Switch 7: OFF

Switch 8: OFF

Switch 9: ON

Switch 10: OFF

Switch 11: OFF

Switch 12: OFF

Switch 13: OFF

Switch 14: OFF

Switch 15: OFF

Switch 16: ON

Switch 17: OFF

Switch 18: OFF

Switch 19: OFF

Switch 20: OFF

Switch 21: OFF

Switch 22: OFF

Switch 23: OFF

Switch 24: OFF

Switch 25: ON

Switch 26: OFF

Switch 27: OFF

Switch 28: OFF

Switch 29: OFF

Switch 30: OFF

Switch 31: OFF

Switch 32: OFF

Switch 33: OFF

Switch 34: OFF

Switch 35: OFF

Switch 36: ON

Switch 37: OFF

Switch 38: OFF

Switch 39: OFF

Switch 40: OFF

Switch 41: OFF

Switch 42: OFF

Switch 43: OFF

Switch 44: OFF

Switch 45: OFF

Switch 46: OFF

Switch 47: OFF

Switch 48: OFF

Switch 49: ON

Switch 50: OFF

Switch 51: OFF

Switch 52: OFF

Switch 53: OFF

Switch 54: OFF

Switch 55: OFF

Switch 56: OFF

Switch 57: OFF

Switch 58: OFF

Switch 59: OFF

Switch 60: OFF

Switch 61: OFF

Switch 62: OFF

Switch 63: OFF

Switch 64: ON

Switch 65: OFF

Switch 66: OFF

Switch 67: OFF

Switch 68: OFF

Switch 69: OFF

Switch 70: OFF

Switch 71: OFF

Switch 72: OFF

Switch 73: OFF

Switch 74: OFF

Switch 75: OFF

Switch 76: OFF

Switch 77: OFF

Switch 78: OFF

Switch 79: OFF

Switch 80: OFF

Switch 81: ON

Switch 82: OFF

Switch 83: OFF

Switch 84: OFF

Switch 85: OFF

Switch 86: OFF

Switch 87: OFF

Switch 88: OFF

Switch 89: OFF

Switch 90: OFF

Switch 91: OFF

Switch 92: OFF

Switch 93: OFF

Switch 94: OFF

Switch 95: OFF

Switch 96: OFF

Switch 97: OFF

Switch 98: OFF

Switch 99: OFF

Switch 100: ON

OK, Splat, glad you caught yourself…

<< 1) on

2) off (second person got it)

3) off (third person got it)

4) off (second person got it) >>

Note that this is incorrect, since switch 4 would have been turned OFF by person 2 but back ON by person 4.

The correct answer is that the perfect squares are the ones ON and everything else is OFF.

Splat does a computer simulation that makes it clear, but others beat him to the answer.

The logic is as follows:

They all start off. For each integer n, set out all its factors, including 1 and n. Here, m is a factor of n if n/m is integer. For every factor of n, there is a person who flips the switch labelled n. So, for example, for the number 12, you’d have: 1, 2, 3, 4, 6, and 12. (Note this is not prime factorization, you list each factor only once).

If the number of such factors is even, then the switch winds up OFF; it started OFF and it is switched by an even number of people, so it winds up OFF.

If the number of factors is odd, then the switch winds up ON. It started OFF and it is switched by an odd number of people, so it winds up ON.

Now, how can a number have an ODD number of factors?

For every n, suppose m is a factor. Then there is another integer (n/m) that is also a factor (the “pair” of m) that appears in the list.

So, the question becomes, for what numbers is the list of factors odd? … for if there are an odd number of factors, then there are an odd number of people flipping the switches, and the resultant light will be ON.

The only way that a factor has no “pair” is if the “pair” is EQUAL to the factor. Thus, I write the factors of 9 as 1, 3 and 9… an odd number, because if m = 3, then n/m = 3 and the number appears only once in the list.

How about a multiple of a perfect square, you ask? Well, try one: 18 factors into 1, 2, 3, 6, 9, and 18. Notice that, although 3 appears as a factor, when I divide 18/3 = 6, that’s another factor that appears in the list. The only way to get an odd number of factors, is if the number itself is a perfect square.

QED.

Whoa, only perfect squares have an odd number of factors! What a great fact!

I’ll bet I knew that once, and totally forgot it. It’s a good fact to throw out at cocktail parties. I’m just amused at how obvious that seems now, and how I completely missed it the first time around.

Well let’s see. Now You requested a formula yet there seems to be no true formula which could easily be applied to such an equasion; Due to the nature of my loquatious habbits i shall attempt to expidite my reply with as little frustration as possible and remain compleatly pertinant to the given subject. the first switch is definantly on, so allow us to assume the number 1 to be a part of the equasion yet to be recognised. There are one hundred pople and one hundread swithces and each person turns a switch off and not on, am i correct? if this is so then the multiple of the number of each person must be expressed and comply with each of the other persons numbers and still maintain a common factor with the number one hundred. Take this number and devide it by the number of switches to be tampered with and this is the formula. 1–100

“100{f}___[E!]/100”

#1-100/c+ --> ([E!]/100)

If this Makes no sence then apply it to your future carear as a Math Problom creator.

Your welcome!

<< There are one hundred pople and one hundread swithces and each person turns a switch off and not on, am i correct? >>

No, you ain’t correct. Each person flips the switch on the appropriate toggle. If it was off, he flips it on; if it was on, he flips it off.

Thus, First Person turns all the switches ON.

Second Person turns 2, 4, 6, 8 … OFF.

At this point, the odd numbers are all ON, the even numbers OFF.

Third person turns every third switch: 3 was ON, so he turns it OFF; but 6 was OFF (from person 2) so now Third Person turns it ON… etc.

Got it?

I was websurfing and I just happened to notice that this problem is question #1 on the Mathcamp 2000 Application Quiz. (And it’s one of the easier ones.)

Hmmm, interesting coincidence.

It’s actually a fairly common “math quiz” question, I’ve seen it several times.

Cabbage, I love your sig line <<…ebius sig. This is a moebius sig. This is a mo… >>

…but unfortunately, as you well know, it’s not Moebius, it’s merely circular. If it were Moebius, it would be left/right reversed when it came around again.

Thanks, and, yeah, it did occur to me that it’s just circular. Still, it just sounds cooler this way.