An Open and Shut Case Concluded
The solution to this problem lies in trying to find out how many times the state of each door is changed. Clearly it will change once for every factor which it has, so how many factors does a number have? A prime number, such as 7, has exactly two distinct factors, 1 and itself. (This is now usually taken as the definition of a prime number, in order to exclude 1 from that category.) Since we want the door to be open, and it starts off shut, we need to find numbers with an odd number of factors. Listing a few, e.g. 20 
{1, 2, 4, 5, 10, 20}, 25{1, 5, 25}, 36 {1, 2, 3, 4, 6, 9, 12, 18, 36}, shows that it looks as if we want squares. A moment’s thought shows that factors essentially occur in pairs, i.e. if f is a factor of a number N then N/f will also be a factor, and these will always be different unless N is a perfect square and f is its square root, which we don’t of course list twice. Thus the only numbers with an odd number of factors are the perfect squares.
A more formal proof involves writing N = p1e1 × p1e2 × … × pnen where the pi are primes raised to the powers ei. The fact that this expression is unique, apart from the order of the primes, is called the Fundamental Theorem of Arithmetic, and is the reason for needing to rule out 1 as a prime. In any factor of N each prime can occur 0, 1, 2 … ei times, so the total number of factors is (e1 + 1)(e2 + 1)(…)(en + 1). The only way for this product to be odd is if all the ei are even, and this would make N a perfect square.
