1000 doors 1000 children.first children open all door second child closed every second door third child close open every third.4th to 100th child repeated this.how many door finally opened

Question

cheesecakekitten · Answer

http://4.bp.blogspot.com/-gisqSw2qDQw/T37Pic_tMRI/AAAAAAAAE2U/dG907OyX5so/s1600/poker%2Bface.jpg

anonymous · Answer

Just so I have the setup right in my mind... Allow me to simplify to 5 doors and 5 children as an example. In the first run through, the first child opens each door (so all 5 are open); the second closes doors 2 and 4; the third closes 3; the fourth opens 4; and the fifth closes 5. (Thus leaving you 1 and 4 remaining open.)

Am I following?

anonymous · Answer

If that is the case, I think you can count the number of doors remaining open in the following way.

With the first child, all doors are opened, i.e.
$$a_1=\sum_{k=1}^{1000}1=1000\text{ open doors}$$
With the second child, every even-numbered door is closed, so we subtract
$$a_2=\sum_{k=1}^{1000/2}1=500~~\implies~~a_1-a_2=500\text{ open doors}$$
The third child closes every odd third door and opens every even third door... We subtract the odd summation and add the even summation:
$$a_3=\left\lfloor\frac{1}{2}\sum_{k=1}^{\lfloor1000/3\rfloor}1\right\rfloor=166~~\implies~~a_1-a_2+a_3=666$$
and so on.

@ganeshie8 What do you think? This approach may be a bit cumbersome :/

ganeshie8 · Answer

I think that gives a sequence from which we can find the number of doors open after $n$th pass! 

If we just want to know the number of open doors in the end of 1000th pass, we can work out easily by noticing that a door with number $n$ will be visited by children exactly $\tau(n)$ times.  ($\tau$ is the number of positive divisors function).

Further, the door remains closed if $\tau(n) $ is even and open otherwise.

anonymous · Answer

Ah cool, I had this idea that some pattern of prime number doors (plus 1) would remain open and was wondering if there was any merit to it. I wasn't sure how to put it into words.

ganeshie8 · Answer

Exactly! her eis the formula for $\tau$ function :
Suppose $$n = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$
then the number of divisors of $n$ is given by
$$\tau(n) = (e_1+1)(e_2+1)\cdots(e_r+1)$$

ganeshie8 · Answer

clearly $\tau(n)$ is even when atleast one of the exponents $e_i$ in the prime factorization of $n$ is odd

ganeshie8 · Answer

$\tau(n)$ will be odd only when all the exponents $e_i$ in the prime factorization of $n$ are even