How to solve this math problem?

[CC]

Whats the formula or trick to use?

******

Can anyone solve it ? ( I can’t …… )



To celebrate the 2009 Math Festival, a teacher set up 2009 numbered lights in a row

The lights are originally switched off

The first student went up to all the lights that are multiples of 1 and switched them on

The next student then went to switch off all the lights that are multiples of 2

The third student then went up to the lights that are multiples of 3, and switch them on if they are off, or switch them off if they are already on

This process continued until the 2009th student, who then switched on or off the last light

The teacher then asked another student to count the number of lights they remain switched on

Q : How many lights did he count ?

[yittz]

Spoilers below
.
.
.
.
.
.
.
.
.
.
.
.
.
.

click to show/hide spoilers

How many square numbers are there below 2009?

Only square numbers have an odd number of factorials (is that what they are called?). All other numbers have even number of factorials (say 24 is 1, 24, 2, 12, 3, 8, 4, 6; whereas 25 is 1, 25, 5).

Odd number of factorials result in lights being switched on. Even number of factorials result in lights being switched off.

[remember_Cedric]

Interesting math problem. I prefer reverse engineering to the problem. I think Yittzie's solution seems logical to the insolvent.

[dictionary]

Spoilers below

click to show/hide spoilers

How many square numbers are there below 2009?

Only square numbers have an odd number of factorials (is that what they are called?).

No, they are called factors. Hehe. Factorial is this, for example, factorial of 4: 1x2x3x4=24.

[jiang bao]

sounds like a job for a computer program LOL.

In terms of math, I guess the key may be common multiples.

I think after the 2nd guy, there may be 1005 on and 1004, then after 3rd guy, there may be 1005 off and 1004 on.

don't have the time or interest to go further.

[Felix]

To celebrate the 2009 Math Festival, a teacher set up 2009 numbered lights in a row

The lights are originally switched off

The first student went up to all the lights that are multiples of 1 and switched them on

The next student then went to switch off all the lights that are multiples of 2

The third student then went up to the lights that are multiples of 3, and switch them on if they are off, or switch them off if they are already on

This process continued until the 2009th student, who then switched on or off the last light

The teacher then asked another student to count the number of lights they remain switched on

Q : How many lights did he count ?

click to show/hide spoilers

44 lights it looks like. Based on yittz "tactic". 1936 is the largest square below 2009. And 44 is the square root of 1936.

[jiang bao]

I do agree that the solution probably has to do with the number of factors a certain number have. For example, after the 1st student goes, the 6th light will be flipped on or off thrice more, because it’s also a multiple of 2, 3 and 6, so it should be off at the end. Similarly the 11th light would be flipped just one more time so it should be off.

I don’t know how to put it in formula. I haven’t studied math since HS, but in words, the rules should be as follows;

If N is an odd number and N has an odd number of factors excluding 1 (e.g. 11), then that light should be off at the end.

If N is an odd number but has an even number of factors excluding 1 (eg: 9—3 and 9), then that light should be on at the end.

Apply same reasoning to even number N. It’s not necessary to exclude 1 as a factor I think, but it’s just easier for me.

The answer is definitely not 44. It’s probably closer to the mid-point of 1004/1005.

[yittz]

What's wrong with if N has even number of factors it's going to be off, and N has odd number of factors it's going to be on. N with odd numbers of factors must be a square number and all square numbers have odd number of factors, hence must be on. The number of square numbers under 2009 is 44. 44 lights will be on.

1 - 1 *
2 - 1, 2
3 - 1, 3
4 - 1, 2, 4 *
5 - 1, 5
6 - 1, 2, 3, 6
7 - 1, 7
8 - 1, 2, 4, 8
9 - 1, 3, 9 *

[seventhfairy]

Whats the formula or trick to use?

******

Can anyone solve it ? ( I can’t …… )



To celebrate the 2009 Math Festival, a teacher set up 2009 numbered lights in a row

The lights are originally switched off

The first student went up to all the lights that are multiples of 1 and switched them on

The next student then went to switch off all the lights that are multiples of 2

The third student then went up to the lights that are multiples of 3, and switch them on if they are off, or switch them off if they are already on

This process continued until the 2009th student, who then switched on or off the last light

The teacher then asked another student to count the number of lights they remain switched on

Q : How many lights did he count ?

I have seen these kind of problems before and I can't solve it either! Sorry

[Nefertari]

The answer is definitely not 44. It’s probably closer to the mid-point of 1004/1005.

Actually 44 seems close to the actual answer, but I don't think the logic behind is square numbers.

I'm thinking the answer is around 41, probably less. It's definitely not 1003/1004, the median. That's because it's a continuous process of switching on and off.

If you try to work out a large enough number, say 50 or 100 on paper (try the process?), you'll probably find a pattern in the left-over number of lights on. As the multiples move on, most numbers (notably the number itself) will be switched off, with only a few numbers smaller than that multiple 'on'. Beyond 1005th student, most lights will eventually be off right, assuming those lights are turned on/untouched. Factors bigger than 1005 will all be off. Hence the answer will not be as big a number as we'd expect it to be, right?

Maybe, someone should work this out, heh like ancient Greeks? It's better than counting Avogadro's number or the decimals of pi, IMO.

[Lifeburner]

I agree that any number above 1005 would be left untouched. But can you explain why you're so sure that they'd be off?

[Nefertari]

I agree that any number above 1005 would be left untouched. But can you explain why you're so sure that they'd be off?

No, I don't mean ANY number above 1005 would be left untouched.

I mean by the time we progressed to beyond say 1004th student, some lights beyond this point will have been switched off and then on at least once, most will experienced this just once, and factors beyond this point will be on. My guess is that the off lights at this point will be a lot less than the on lights. So, keeping this in mind, as the multiples keep progressing, the majority of the lights which are previously on will in the end be off.

For example, say from 1010 to 1020, if 1011, 1013, 1014, 1015, 1017, 1019, 1020 are still on by then, they will all be off eventually as the 1010th to 1020th students will switch them off. Conversely, 1012, 1016 and 1018 will be turned on. So, we can see, the proportion of 'off' lights are much more than 'on' lights. The answer can't be 1005, but I'm not sure how many. But I guess it'd be reasonable to say, the answer would be between 30 and 150?

Also, all factors (2,3,5,7 .....) will eventually be off. The first light will always be on.

[yittz]

No, I don't mean ANY number above 1005 would be left untouched.

I mean by the time we progressed to beyond say 1004th student, some lights beyond this point will have been switched off and then on at least once, most will experienced this just once, and factors beyond this point will be on. My guess is that the off lights at this point will be a lot less than the on lights. So, keeping this in mind, as the multiples keep progressing, the majority of the lights which are previously on will in the end be off.

For example, say from 1010 to 1020, if 1011, 1013, 1014, 1015, 1017, 1019, 1020 are still on by then, they will all be off eventually as the 1010th to 1020th students will switch them off. Conversely, 1012, 1016 and 1018 will be turned on. So, we can see, the proportion of 'off' lights are much more than 'on' lights. The answer can't be 1005, but I'm not sure how many. But I guess it'd be reasonable to say, the answer would be between 30 and 150?

Also, all factors (2,3,5,7 .....) will eventually be off. The first light will always be on.

So what's wrong with square numbers? I thought the explanation was clear enough on its own, let alone me listing the first 3 open lights in numbers less than 10. Pick my answer apart, before questioning it. The answer doesn't feel right is insufficient.

Why are there only a few lights from 1005 and beyond? Because there are only a few square numbers in between - 13 lights on between 2009 and 1005, but 31 below 1005.

[Nefertari]

So what's wrong with square numbers? I thought the explanation was clear enough on its own, let alone me listing the first 3 open lights in numbers less than 10. Pick my answer apart, before questioning it. The answer doesn't feel right is insufficient.

Why are there only a few lights from 1005 and beyond? Because there are only a few square numbers in between - 13 lights on between 2009 and 1005, but 31 below 1005.

There's nothing wrong with square numbers. You're right on the answer.
It's just that I didn't quite understand what you wrote at first, because you started your sentence with 'What's wrong with.....' I don't understand what you mean. I read your logic the other way round.

I was thinking along the lines of factors at that time, like 2 and 3 would definitely be off, since they're factors.

I see that you're listing lights on and counting 1 as a factor and I didn't quite get it, since I didn't see 1 as a factor of anything. So, I can't see the odd number of factors. I saw it the other way round.

Sorry about that. I know the answer would be around 40. You're definitely right with the answer being 44.

[Nefertari]

Minor correction to the answer guys.

Answer is 45. We forgot to count 1 in previously. 44 + 1 = 45 lights should be on.

[yittz]

Why would you add one to the answer. 44 lights includes 1 already. 45 squared is 2025, there are only 44 square numbers under 2009 and that includes 1.

[Nefertari]

Why would you add one to the answer. 44 lights includes 1 already. 45 squared is 2025, there are only 44 square numbers under 2009 and that includes 1.

Thanks!

I keep forgetting that 1 is also a square number itself. I always start with 4 and then 9, coz 1 is simply too simple. Thanks for reminding yittz.

[IcyFox]

OK this problem is difficult - mainly because there isn't a simple algebraic form of the series, meaning that it's very hard to solve it with algebra. (Or that I don't know of any efficient method of doing it.)

The big issue here is that each person must turn on/off the lights in multiples of his/her assigned number. Here are the 1st few cases:


X ~ On ; O ~ Off

1. XXX ... (2009)
2. OOO ... (2008, X)
3. XXX ... O X (2007, O, X)
4. OOO ... XXX O X (2004, 3X, O, X)
5. XXX ... OOOO XXX O X (2000, 4O, 3X, O, X)

ETC ETC ETC...


If the lights are NOT multiples of the person's number, they CANNOT be touched.

It's pretty obvious that the number of lights still ON at the end of this whole meaningless exercise is kinda difficult to count by hand. So, I think the best way to solve it is of course by computer. (Unless you have lots of spare time and waste paper...)

[IcyFox]

As mentioned previously, I solved the problem using a computer with a program written in C++. (The final answer actually converged in less than 100 iterations.)


LIGHTS ON : 1019


Attached are both the C++ source code and the output text file.

An assumption I made in order to simplify the computation was that the remaining lights were grouped in numbers less than multiples of the person's assigned number.

Actually this is quite obvious and requires no proof to see why it is so. If you spot any flaw in my method, please explain mathematically or work it out for yourself on paper to convince yourself.