Please explain this simple math

[lee_chongeu]

There is 1000 doors (label 1,2,3...,999,1000) and 1000 peoples. First person close all doors, 2nd people open doors with label multiple of 2, 3rd person open doors with label multiple of 3 and so on. If the doors is open, he will close it. After 1000 people do that, how many doors are CLOSED? I has the answer, but I'm not understand it. Can someone explain how to do this simple math? Thanks...

 

[arildno]

I don't see why this can be made any simpler than just making a listing.

Have a table of the 1000 first numbers in front of you.

Put a cross on each number that is divisible with 2.

Repeat the process for all primes between 1 and 1000

Those numbers where there are an odd number of crosses at will be open, those with an even number closed.

 

[lee_chongeu]

Lets have the example.

Let consider for 10 doors and 10 persons. That is the list. Now can you understand my question? Making a list isn't easy, but there is mathematical solution to this answer. The number for the closed door is 3. That is sqrt(10)=3.162=approx=3. Why?

 

[Trail_Builder]

im a super noob at math and havnt gone too far above standard 16 year old level but I am guessing you might have to throw mod 2 somewhere in the mix?

 

[Werg22]

This problem involves knowing all primes between 1 and 1000, which is not something that can be done methodically. Like arildno said, it has to be done the long way. I suggest you find what you need to do exactly instead and stop there though - solving it is no fun at all.

 

[JasonRox]

I don't see why this can be made any simpler than just making a listing.

Have a table of the 1000 first numbers in front of you.

Put a cross on each number that is divisible with 2.

Repeat the process for all primes between 1 and 1000

Those numbers where there are an odd number of crosses at will be open, those with an even number closed.

Just a table with the first 100 will do. And just go over them over and over again 10 times. Crossing in different patterns so you know where you are.

 

[nugae]

It's fairly easy to see that the problem says "the door is closed if the number has an odd number of factors, the door is open if it has an even number of factors" - where we define "the number of factors" of a number N as including all numbers that divide N, including 1 and N itself. For instance, the number of factors of 6 is four: 1, 2, 3, and 6.

Note the following:

If you multiply a number N by a prime p (where N is not already divisible by p), pN has twice as many factors as N. [It has all the original factors of N, and also p times each of the original factors of N].

If you multiply a number N by the square of a prime p (where N is not already divisible by p), then p²N has three times as many factors as N. [The original factors of N, p times each of those factors, and p² times each of those factors].

In general, if you multiply N by an odd power of p, you multiply the number of factors by an even number. If you multiply N by an even power of p, you multiply the number of factors by an odd number.

Note that 1 has an odd number of factors (1 is the only factor).

Any number N>1 is a product of prime powers. These may be primes themselves (6 = 2·3), squares of primes (98 = 2·7²), cubes of primes (56 = 2³·7), and so on.

Now if you express N as a product of prime powers, and every one of those powers is an even power, then N will have an odd number of factors. This is because you can get from 1 to N by multiplying by an even power at each stage; and as we've seen before, multiplying N by an even power means that the number of factors of N gets multiplied by an odd number (3 for squared factors, 5 for fourth-power factors, and so on).

But if even one of the prime powers in N is a prime itself (ie. the first power of p) or an odd power of a prime, then as you're going from 1 to N, multiplying by that prime power will multiply the number of factors of N by an even number (doubling it, if we're talking about a prime, quadrupling it if we're talking about a prime cubed, and so on).

So N can only have an odd number of factors if N is a product of even powers of primes — in other words, if N is a square number.

So the only doors that end up closed are the ones that are at square-numbered positions: door 1, door 4, door 9, and so on.

There are much shorter and more mathematical ways of explaining this result, but I wanted to make it clear in words without having to use TeX to write elegant symbolic formulae.

 

[Data]

nugae's solution is correct. In general for

n = p_1^{e_1}...p_k^{e_k}

with p_1, ..., p_k distinct primes and e_1,...,e_k nonnegative integers, n has exactly

\prod_{i=1}^k (e_i + 1)

distinct natural divisors (see why?). If you multiply by a prime p not in \{ p_1,...,p_k\} then you must add a factor of 1+1=2.

For example, 1 has exactly 1 natural divisor, while any prime p = 1*p has exactly two natural divisors.

 

[drpizza]

nugae's correct: perfect squares.

Much simpler version:
If you write all the pairs of factors of a number, let's say 72:
1*72
2*36
3*24
4*18
6*12
8*9
There's an even number of factors.
Thus, for 72, the door's condition will be changed 12 times; open, closed, open, closed... Since it has an even number of distinct factors, it ends up closed.

Now, for a number like 36, note:
1*36
2*18
3*12
4*9
6*6!
Person 6 doesn't get to go down the hallway twice; so in this case, an odd number of people will change the condition of the door. The people being #'s 1,36,2,18,3,12,4,9,6.

It doesn't matter what order you let them go about opening and closing the doors; in the end, it only matters whether an even number of people change the state of the door or an odd number of people. The only way to get an odd number of people is if the number is a perfect square.

 

[Werg22]

I deleted my post because I realized I was mistaken. nugae's solution is certainly valid.

 

[nugae]

This is why I hate posting answers in forums. I think of a nice abstruse proof, then do my best to put it simply (and long-windedly)... and then someone else comes up with a truly excellent, simple, intuitive solution that doesn't require any clever algebraic symbols at all!

Thank you, drpizza, you're absolutely right and it's beautiful as well.

 

[Gib Z]

Let consider for 10 doors and 10 persons. That is the list. Now can you understand my question? Making a list isn't easy, but there is mathematical solution to this answer. The number for the closed door is 3. That is sqrt(10)=3.162=approx=3. Why?

Well now with the explanations provided by nugae and drpizza, you can see you were really on a hunch, because since its the number of perfect squares, we take the square root, and trancate it at the start of its decimal expansion, or more concisely, we take apply the floor function to it.