Tuesday, 3 June 2008

Open Doors: Answer

Answer: The open doors will be 1, 4, 9, 16, 25, ..., 100 i.e. the perfect squares.

In order for a door to remain open, it must have been toggled even number of times e.g. door 4 toggled twice: start (open), toggle (close) on day 2 and toggle (open) on day 4. Door X is toggled on Day Y for every factor Y of X e.g. Door 16 is toggled on Day 2, 4, 8, 16. Door 30 is toggled on Day 2, 3, 5, 6, 10, 15, 30.

1. A perfect square is a number that can be expressed as the square of an integer e.g. 4 = 2^2, 9 = 3^2, 16 = 4^2, 25 = 5^2, ...
2. An integer N is a perfect aquare if and only if its prime factorization is a product of primes raised to even powers e.g. 36 = 2^2*3^2, 81 = 3^4. This is obvious since N = q^2 where q is an integer.
3. A perfect square has odd number of factors including 1 and itself e.g. 36 = 2^2*3^2 has (2+1)*(2+1) = 9 factors including 1 and itself (1, 2, 3, 4, 6, 8, 12, 18, 36). Excluding 1 which is the starting when all doors are open, perfect squares are the only numbers that have even number of factors including itself and hence will be toggled even number of times.