2

There are $1000$ doors $D_1,D_2,D_3,\dots,D_{1000}$ and $1000$ persons $P_1,P_2,\dots,P_{1000}$. Initially all the doors were closed. Person $P_1$ goes and opens all the doors. Then person $P_2$ closes doors $D_2,D_4,\dots,D_{1000}$ and leaves the odd-numbered doors open. Next, $P_3$ changes the state of every third door, that is $D_3,D_6,\dots,D_{999}$.(For instance, $P_3$ closes the open door $D_3$ and opens the closed door $D_6$, and so on.) This goes on. Finally, person $P_{1000}$ opens $D_{1000}$ if it were closed or closes if it were opened. At the end, how many doors remain open$?$

  • Please use more descriptive titles. Searching becomes difficult otherwise. Also, don't just post every training question you see. Search the site first. – Jyrki Lahtonen Aug 14 '15 at 07:49

2 Answers2

3

At the end, how many doors remain open?

A door is flipped by each of its factors (e.g. Door 8 is flipped by runs 1, 2, 4, and 8) Each door representing a perfect square (1, 4, 9, ... 961) will have an odd number of factors, thus an odd number of flips and will be left in an open state.

I actually did this exercise in a high school math class by having students hold up pieces of paper numbered 1-25. Unfortunately most of the 10th graders didn't appreciate the beauty of the exercise...

D Stanley
  • 312
  • @D Stanley how do you hide text like that? Feel free to direct me to a tutorial or other resource if you feel it more appropriate. – 727 Aug 12 '15 at 20:57
  • 1
    @LJL Prefix it with >! - similar to a quote. Click the question mark in the top right of the editor and look for "Spoiler" in advanced help. – D Stanley Aug 12 '15 at 22:26
2

Initially all doors are closed. We want to count how many times the state of a given door is changed.

It is easy to see that the state of any given door is changed once for each divisor it has (the 12th door, for example, is changed by the 1st, 2nd, 3rd, 4th, 6th, and 12th person). Thus, if a door number has an even number of divisors, its "net" state is unchanged and stays closed at the end.

If a door has an odd number of divisors, it will be open at the end.

Now for the trick: the only way for a number to have odd divisors is if it is a perfect square. Otherwise, factors always come in pairs — 12 has (1,12) and (2,6) and (3,4), but only a perfect square like 25 could have the single factor of 5.

Thus we must count the number of perfect squares between 1 and 1000. As another user pointed out, thus number is 31.

pancini
  • 19,216