100 Door puzzle
Puzzle: There are various versions of the puzzle, there are 100 doors (or some other object), and 100 cops (prisoners). All the doors are closed initially. Cop 1 goes and opens up all the the doors, Cop 2 goes and closes door at even number 2,4,6 etc. Cop 3 goes and alters the state of doors divisible by 3 (3,6,9), so if the door was closed it is opened and if it was open, it is closed by cop 3. Cop 4 will alter state of all the doors divisible by 4 and so on. At the end we have to find out how many doors are closed now.
Solution: Before getting to a generic solution, lets take case of few doors 1 by one. We can easily see that a door’s state is same if it was visited even number of time (initially closed than (open + close) (open + close).. ), and it is changed if the door is visited odd number of times.
Case of Door 1: Only visited once by Cop1, so the state changes to open
Case of Door 2: Visited twice by cop1 and cop2, so finally it is closed, no change in state (see it is visited even number of times)
Case of Door 3: Visited by 1 and 3- Closed
Case of Door 4: Visited by 1, 2 and 4- Open
Case of Door 5: Visited by 1 and 5- Closed
Case of Door 6: by 1, 2, 3 and 6- Closed
Case 9: 1, 3 and 9- Open
Case 10: 1,2, 5 and 10- Open
So on careful examination, figure out doors which have even number of divisors are not changing state. When will a number have odd number of divisors? A divisor pair of a number z is x*y (always 2, and hence even)
for 50: 1*50, 2*25, 5*10- Even
for 100: 1 * 100, 2*50, 4*25, 5*20, 10*10- Odd (As 10 appears twice)
So for all the perfect squares, we can see we have odd number of divisors and hence the state of the door will be changed.