Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
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

3 Answers 3

up vote 8 down vote accepted

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.
share|improve this answer

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?

share|improve this answer

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

share|improve this answer
    
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
1  
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

Not the answer you're looking for? Browse other questions tagged or ask your own question.