Really horrid math problem

Turpentine · April 25, 2000, 3:18pm

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?”

KarmaComa · April 25, 2000, 3:22pm

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.

Boris_B · April 25, 2000, 3:24pm

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.

Cabbage · April 26, 2000, 1:24am

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)

RM_Mentock · April 26, 2000, 1:28am

Whoa. Too many numbers!

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

rocks

Splat · April 26, 2000, 11:29am

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.

Splat · April 26, 2000, 12:05pm

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 &lt; 100; i++)
	switches* = 1;
// now second and subsequent people
for (j = 1; j &lt; 100; j++)
	for(i = j; i &lt; 100; i += j + 1)
		switches* = !switches*;
for (i = 0; i &lt; 100; i++)
	cout &lt;&lt; "Switch " &lt;&lt; (i + 1) &lt;&lt; ": " &lt;&lt; (switches* ? "ON" : "OFF") &lt;&lt; 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

C_K_Dexter_Haven · April 27, 2000, 5:35am

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.

Boris_B · April 27, 2000, 5:57am

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.

BELASCO · April 26, 2000, 6:25pm

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!

C_K_Dexter_Haven · April 26, 2000, 9:11pm

<< 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?

rowrrbazzle · May 22, 2000, 4:08am

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.

Cabbage · May 22, 2000, 8:38am

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

C_K_Dexter_Haven · May 22, 2000, 12:18pm

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.

Cabbage · May 22, 2000, 10:21pm

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