# Really horrid math problem **URL:** \ **Category:** Factual Questions\ **Created:** [April 25, 2000, 3:18pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133 "2000-04-25T15:18:00Z")\ **Posts on this page:** 15\ **Page:** 1
**Author:** ![Turpentine](https://avatars.discourse-cdn.com/v4/letter/t/ecd19e/32.png) [@Turpentine](https://boards.straightdope.com/u/Turpentine)\ **Post date:** [April 25, 2000, 3:18pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/1 "2000-04-25T15:18:00Z")
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?” ---
**Author:** ![KarmaComa](https://avatars.discourse-cdn.com/v4/letter/k/e36b37/32.png) [@KarmaComa](https://boards.straightdope.com/u/KarmaComa)\ **Post date:** [April 25, 2000, 3:22pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/2 "2000-04-25T15:22:00Z")
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. ---
**Author:** ![Boris\_B](https://avatars.discourse-cdn.com/v4/letter/b/fbc32d/32.png) [@Boris\_B](https://boards.straightdope.com/u/Boris_B)\ **Post date:** [April 25, 2000, 3:24pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/3 "2000-04-25T15:24:00Z")
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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [April 26, 2000, 1:24am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/4 "2000-04-26T01:24:00Z")
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) ---
**Author:** ![RM\_Mentock](https://avatars.discourse-cdn.com/v4/letter/r/e274bd/32.png) [@RM\_Mentock](https://boards.straightdope.com/u/RM_Mentock)\ **Post date:** [April 26, 2000, 1:28am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/5 "2000-04-26T01:28:00Z")
> [@](#): > > Originally posted by Boris B: > \*\*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. \*\* Whoa. Too many numbers! But it’s easy to figure out: only perfect squares have an odd number of factors. * * * rocks ---
**Author:** ![Splat](https://avatars.discourse-cdn.com/v4/letter/s/c37758/32.png) [@Splat](https://boards.straightdope.com/u/Splat)\ **Post date:** [April 26, 2000, 11:29am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/6 "2000-04-26T11:29:00Z")
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 1. on 2. off (second person got it) 3. off (third person got it) 4. off (second person got it) 5. on 6. 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. ---
**Author:** ![Splat](https://avatars.discourse-cdn.com/v4/letter/s/c37758/32.png) [@Splat](https://boards.straightdope.com/u/Splat)\ **Post date:** [April 26, 2000, 12:05pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/7 "2000-04-26T12:05:00Z")
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 \ 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 ---
**Author:** ![C\_K\_Dexter\_Haven](https://avatars.discourse-cdn.com/v4/letter/c/b2d939/32.png) [@C\_K\_Dexter\_Haven](https://boards.straightdope.com/u/C_K_Dexter_Haven)\ **Post date:** [April 27, 2000, 5:35am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/8 "2000-04-27T05:35:00Z")
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. ---
**Author:** ![Boris\_B](https://avatars.discourse-cdn.com/v4/letter/b/fbc32d/32.png) [@Boris\_B](https://boards.straightdope.com/u/Boris_B)\ **Post date:** [April 27, 2000, 5:57am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/9 "2000-04-27T05:57:00Z")
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. ---
**Author:** ![BELASCO](https://avatars.discourse-cdn.com/v4/letter/b/34f0e0/32.png) [@BELASCO](https://boards.straightdope.com/u/BELASCO)\ **Post date:** [April 26, 2000, 6:25pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/10 "2000-04-26T18:25:00Z")
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! ---
**Author:** ![C\_K\_Dexter\_Haven](https://avatars.discourse-cdn.com/v4/letter/c/b2d939/32.png) [@C\_K\_Dexter\_Haven](https://boards.straightdope.com/u/C_K_Dexter_Haven)\ **Post date:** [April 26, 2000, 9:11pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/11 "2000-04-26T21:11:00Z")
\<\< 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? ---
**Author:** ![rowrrbazzle](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/rowrrbazzle/32/414_2.png) [@rowrrbazzle](https://boards.straightdope.com/u/rowrrbazzle)\ **Post date:** [May 22, 2000, 4:08am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/12 "2000-05-22T04:08:32Z")
I was websurfing and I just happened to notice that this problem is question #1 on the [Mathcamp 2000 Application Quiz](http://www.mathcamp.org/quiz-new.htm). (And it’s one of the easier ones.) Hmmm, interesting coincidence. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [May 22, 2000, 8:38am UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/13 "2000-05-22T08:38:18Z")
It’s actually a fairly common “math quiz” question, I’ve seen it several times. ---
**Author:** ![C\_K\_Dexter\_Haven](https://avatars.discourse-cdn.com/v4/letter/c/b2d939/32.png) [@C\_K\_Dexter\_Haven](https://boards.straightdope.com/u/C_K_Dexter_Haven)\ **Post date:** [May 22, 2000, 12:18pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/14 "2000-05-22T12:18:26Z")
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. ---
**Author:** ![Cabbage](https://avatars.discourse-cdn.com/v4/letter/c/f07891/32.png) [@Cabbage](https://boards.straightdope.com/u/Cabbage)\ **Post date:** [May 22, 2000, 10:21pm UTC](https://boards.straightdope.com/t/really-horrid-math-problem/11133/15 "2000-05-22T22:21:40Z")
Thanks, and, yeah, it did occur to me that it’s just circular. Still, it just sounds cooler this way. 😉