# 1000 Doors Homework Problem [duplicate]

I am faced with the following problem as homework- a man has 1000 doors. he opens every door, and then he closes every second door. Then he works on every third door- if it's open, then he closes it. if it's closed, he opens it. Then he works on every fourth door, fifth door, and so on all the way until the 1000th door. I need find the amount of doors left open and their numbers (Door 1, Door 2, etc.).

Can someone please tell me the first step to solving this and what kind of mathematics I need to use.

-

## marked as duplicate by Goos, Stefan4024, draks ..., Rick Decker, T. Bongers Dec 13 '13 at 0:40

For door number $n$, in which iterations is its state flipped? Thus how often is it flipped altogether? –  Daniel Fischer Dec 12 '13 at 23:17
These 31 doors will be open:$1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289,324,361,400,441,,4‌​84,529,576,625,676,729,784,841,900,961$ –  K. Rmth Dec 12 '13 at 23:24

Hints.

1. The $n$th door is changed in step $k$ iff $k$ divides $n$.
2. It is only important that the number of changes at a door is even or odd.
3. If $n$ is not square, its divisors can be paired up.
-

This is a problem involving divisibility. Notice that the number of times a door is opened/closed is precisely the number of divisors that it has. For example, prime numbers have only two divisors, $1$ and itself, so all prime numbered doors are opened and then closed. The doors which remain open are precisely the doors which have an odd number of divisors. Can you figure out what those are?

-

This is an absolute classic, in the first round he opens all of them, then he closes multiples of 2. Then he alters multiples of 3. So in round $j$ the door $a$ is opened or closed if and only if j divides it. How many times is each door altered think about its divisors.

full solution:

a door $j$ is altered the same number of times as the number of divisors it has, so the open doors are the ones with an odd number of divisors, let $d$ divide $j$, then $j=dk$. So every divisor corresponds to another unique divisor. Unless we have $d=k$ in which case $j=d^2$. so the ones open are exactly the perfect squares. Also see: light bulb teaser

-
How can I make the box thing that is only reveiled after you put the mouse pointer over it? –  Jorge Fernández Dec 12 '13 at 23:24
Use >!  for a spoiler. –  Daniel Fischer Dec 12 '13 at 23:25
don't spoil it. I only asked for a hint. –  Joao Dec 12 '13 at 23:26