Help me with math problem

[wiredspider]

Extra credit for class I can't seem to get quite right

Starts out like this, there are 10,000 cells, there are 10,000 workers too
What happens each day is that worker #1 goes and turns on all the cells (state 1).
Then worker #2 changes the state of all the even numbered cells to off (state 0), so it would do 2,4,6,8 until 10,000
Then worker #3 would change the state of all the cells divisible evenly by 3 (so if in state 1, it would go to state 0 and vice versa).
This basically happens all the way up to worker #10,000 (so after 5001, only one cell state would change).

At the end of the day, the cells are emptied, but the professor is looking for how many cells would be in state 1 at the end of the day, after worker #10,000 has done his thing, but the cells have not been emptied.

There is probably some pattern I'm missing too, I tried doing the problem with a smaller number of workers (like 100) and then scaling it to 10,000, but it didn't work out to well.

 

[Anubis]

42

 

[Leros]

do you need to show work? If not, just write a little program to do it.

 

[Syringer]

The most common usage of this problem generally involves lockers..

http://forums.xkcd.com/viewtopic.php?t=315

Check out penguin's response..

 

[wiredspider]

We can use a program to do it, but I suck at programming

I never learned about "arrays" so I think the best I can do is print out 10,000 spaces/characters.

Though thanks for the xkcd link, I think it'll help some when I read it later.

 

[Turkey22]

If they rotate the 3 jobs worker 10,000 would be turning them all back on. I'm not sure why you say after 5001 only one state is changing. It's possible I'm not getting it, but if they rotate and worker 1's job is in the rotation then they are all on.

 

[Ilmater]

Originally posted by: Turkey22
If they rotate the 3 jobs worker 10,000 would be turning them all back on. I'm not sure why you say after 5001 only one state is changing. It's possible I'm not getting it, but if they rotate and worker 1's job is in the rotation then they are all on.

No...

Worker #1 turns all cells divisible by 1 to the opposite state (in this case, all on).
Worker #2 turns all cells divisible by 2 to the opposite state
Worker #3 turns all cells divisible by 3 to the opposite state
Worker #4 turns all cells divisible by 4 to the opposite state
Worker #5 turns all cells divisible by 5 to the opposite state
Worker #6 turns all cells divisible by 6 to the opposite state
...
Worker #5000 turns all cells divisible by 5000 to the opposite state (ie. cells 5000 and 10000)
Worker #5001 turns all cells divisible by 5001 to the opposite state (ie. only cell 5001)

 

[QED]

When you did the problem for just 100 workers and 100 cells, did you notice a pattern? You should have...

Instead of asking what cells are in state 1 (i.e, is ON) at the end, simply consider a single cell-- say the cell numbered M: how many times does it get toggled from on to off or vice-versa? The answer is pretty simple: it will get toggled one time for each multiplicative factor of M.

For example, cell #7 will only be turned on by worker #1, and turned off by worker #7 because 1 and 7 are the only factors of 7. Cell #12 will be turned on by worker #1, turned off by worker #2, turned on by worker #3, turned off by worker #4, turned on by worker #6, and turned off by worker #12.

Hence, it's fairly easy to see that a cell number with an even number of positive factors will always be in the OFF position at the end and a cell number with an odd number of positive factors will always be in the ON position at the end.

So now the problem is reduced to finding out which numbers have an even number of positive factors, and which numbers have an odd number of positive factors... Here's a final hint: if p is a positive factor of cell number M, then so is M/p-- so positive factors can ALMOST always be paired up...

 

[puffff]

Originally posted by: QED
When you did the problem for just 100 workers and 100 cells, did you notice a pattern? You should have...

Instead of asking what cells are in state 1 (i.e, is ON) at the end, simply consider a single cell-- say the cell numbered M: how many times does it get toggled from on to off or vice-versa? The answer is pretty simple: it will get toggled one time for each multiplicative factor of M.

For example, cell #7 will only be turned on by worker #1, and turned off by worker #7 because 1 and 7 are the only factors of 7. Cell #12 will be turned on by worker #1, turned off by worker #2, turned on by worker #3, turned off by worker #4, turned on by worker #6, and turned off by worker #12.

Hence, it's fairly easy to see that a cell number with an even number of positive factors will always be in the OFF position at the end and a cell number with an odd number of positive factors will always be in the ON position at the end.

So now the problem is reduced to finding out which numbers have an even number of positive factors, and which numbers have an odd number of positive factors... Here's a final hint: if p is a positive factor of cell number M, then so is M/p-- so positive factors can ALMOST always be paired up...

To spell it out:

Only numbers that are perfect squares will have an odd number of factors.

And so there you have it, how many numbers from 1 to 10000 are perfect squares? Well, 100x100 = 10000, so the answer is 100

 

[QED]

Originally posted by: puffff

Originally posted by: QED
When you did the problem for just 100 workers and 100 cells, did you notice a pattern? You should have...

Instead of asking what cells are in state 1 (i.e, is ON) at the end, simply consider a single cell-- say the cell numbered M: how many times does it get toggled from on to off or vice-versa? The answer is pretty simple: it will get toggled one time for each multiplicative factor of M.

For example, cell #7 will only be turned on by worker #1, and turned off by worker #7 because 1 and 7 are the only factors of 7. Cell #12 will be turned on by worker #1, turned off by worker #2, turned on by worker #3, turned off by worker #4, turned on by worker #6, and turned off by worker #12.

Hence, it's fairly easy to see that a cell number with an even number of positive factors will always be in the OFF position at the end and a cell number with an odd number of positive factors will always be in the ON position at the end.

So now the problem is reduced to finding out which numbers have an even number of positive factors, and which numbers have an odd number of positive factors... Here's a final hint: if p is a positive factor of cell number M, then so is M/p-- so positive factors can ALMOST always be paired up...

To spell it out:

Only numbers that are perfect squares will have an odd number of factors.

And so there you have it, how many numbers from 1 to 10000 are perfect squares? Well, 100x100 = 10000, so the answer is 100

Well, I was hoping the OP could take the final deductive step of reasoning himself... but oh well...

 

[sygyzy]

pufff - I get the perfect squares thing but how did yo know there are 100 perfect squares in 10,000?

 

[QED]

Originally posted by: sygyzy
pufff - I get the perfect squares thing but how did yo know there are 100 perfect squares in 10,000?

The n'th perfect square is simple n*n... so the 100th perfect square is 10,000-- in other words, there are 100 perfect squares less than or equal to 10,000.

 

[imported_stev]

Originally posted by: wiredspider
We can use a program to do it, but I suck at programming

No time like the present to learn. If you don't already have a language of choice and you want to learn something for math problems, try out MATLAB or IDL.

There's probably a way to reason it without the brute-force method of coding it up, but it's not a bad idea to develop both analytical and computational skills when it comes to math.

EDIT: I see it's probably already been solved. Does ATOT get your extra credit now?

 

[wiredspider]

I did get it and figured out it was the perfect squares left. The other part of the extra credit problem was to find it for other number of cells like 100,000 or like 10 million. The answer was to find the square roots of those number and drop off the decimals.

And I actually did make a program in C++ that would find the square root on a number like 2 years ago (for class), but a calculator was easier than trying to figure out my code from 2 years ago.

 

[BrownTown]

I woulda just written the program to solve this, but the logic used by "penguin" is very well conceived. That having been said the program to solve this little problem would only take 1-2 minutes to write, so its alot more of a sure thing to just do the program and see than to try to reason it out.

 

[Syringer]

Originally posted by: QED

Originally posted by: sygyzy
pufff - I get the perfect squares thing but how did yo know there are 100 perfect squares in 10,000?

The n'th perfect square is simple n*n... so the 100th perfect square is 10,000-- in other words, there are 100 perfect squares less than or equal to 10,000.

Yup..up to the last number, you'll have, 1 * 1, 2 * 2, ..., 10 * 10,.,,, 100 * 100,...x * x.

100 numbers.

 

[puffff]

Originally posted by: BrownTown
I woulda just written the program to solve this, but the logic used by "penguin" is very well conceived. That having been said the program to solve this little problem would only take 1-2 minutes to write, so its alot more of a sure thing to just do the program and see than to try to reason it out.

it helps to train your thinking for these brain teasers and recognize different math concepts that could help, like factorization, modular arithmatic, etc. many prestigious tech companies ask these types of questions in interviews now, you want to become good at solving them if you're aiming for those jobs.

this problem wouldve been easy to code up, but it also shouldnt have taken more than a couple minutes to reason out as well.

 

[BrownTown]

Yeah like I said, I probably could have reasoned it up eventually but the coding way is alot more of a sure thing since its pretty straightforward code wheraa its easy to make a mistake in reasoning. I hear alot about companies asking questions of this type for interviews, but so far I have not had that experience, perhaps its just programming companies and stuff, the electrical engineering companies I've applied to all just wanted to know about my skills in terms of knowing how to do different real life tasks as opposed to brain teasers. The reasoning skills for this problem are something that WOULD deffintely help you be a good programmer since you can develop a much more efficient algorithm than the "brute force" method, however those same skills don't nesecarrily apply as well to other profressions, with what I do its alot about being able to visualize schematics and blueprints into physical objects, so they ask questions like that instead.

 

[imported_quasi]

If anyone is interested, I wrote this out in Python in a few minutes:

cells = [True for i in range(10001)]
cells[0] = False

for i in range(2, 10001):
for j in range(i, 10001, i):
if cells[j] == False:
cells[j] = True
else:
cells[j] = False

print len(filter(lambda x: x == True, cells))

Edit: Fusetalk messes up the indentation, which is required for Python (a good thing, imo).

 

[KLin]

Public Function perfectsquare()
Dim dbl As Double
For dbl = 1 To 100000
If Sqr(dbl) - Fix(Sqr(dbl)) = 0 Then
DoCmd.SetWarnings False
DoCmd.RunSQL ("INSERT INTO tblLocker(Locker) VALUES (" & dbl & ")")
DoCmd.SetWarnings True
End If
Next dbl

End Function

Same thing in a vba module in access, inserting the value into a table.

I also did a brute force based on workers/cells but that takes longer to run. for 10000 each about 10 seconds, for 100000 each about 14 minutes.

 

[KLin]

100 10
1000 31
10000 100
100000 316
1000000 1000
10000000 3162
100000000 10000
1000000000 31622

Interesting pattern.

 

[Gunslinger08]

It's all the perfect squares.

 

[puffff]

Originally posted by: quasi
If anyone is interested, I wrote this out in Python in a few minutes:

cells = [True for i in range(10001)]
cells[0] = False

for i in range(2, 10001):
for j in range(i, 10001, i):
if cells[j] == False:
cells[j] = True
else:
cells[j] = False

print len(filter(lambda x: x == True, cells))

Edit: Fusetalk messes up the indentation, which is required for Python (a good thing, imo).

the problem with this solution is that it is O(n^2). suppose his professor asked the question for 123456789 * 987654321 instead of 10000? your program might take a while to complete. whereas if you spent a minute to see the squares pattern, you could write a program that completes in linear time.