Answer to Santa's Little Helpers


The number of reindeer that will not have escaped at the end of the exercise will be equal to the number of square numbers that are less than or equal to N (where N is the number of stable doors; 1,000 in the problem above) so there are 31 doors remaining closed. But why?

Initially (before the reindeer are installed - no pun intended!), all of the doors are open. The action of each helper flips the door into its alternate open/closed state.

The first helper flips every door, the second helper flips doors 2, 4, 6, …, 1000, the third flips doors 3, 6, 9, …, 999 and, finally, the thousandth helper just flips door number 1,000.

The number of times door P is flipped is equal to 2 + the number of proper factors of P. For example, when P is 75, the proper factors are 3, 5, 15 and 25. This door will be flipped a total of six times (once extra by the first helper and once extra by the 75th helper). If a door is flipped an even number of times from an initial open state, it will be left open at the end and the reindeer inside will escape (as in this case). What we want to know is how many numbers less than or equal to N have an odd number of proper factors.

Suppose Q has an odd number of proper factors. If we include 1 and Q itself as factors, then the total number of factors of Q will still be odd. By the Fundamental Theorem of Arithmetic, Q may be represented as

Q = q1i1 × q2i2 × q3i3 × … × qmim

where {q1, q2, q3, …, qm} is a unique set of m distinct prime factors and each index {i1, i2, i3, …, im} is a uniquely defined whole number greater than or equal to zero (this is non-trivial). For example, 350 = 21 × 52 × 71.

Each factor of Q must contain a prime divisor that is one of the set of above q's. If we work out the total number of permutations of indices to which we may raise each q to obtain one of the factors of Q, we find that the total number of Q's factors (including 1 and Q) is (i1+1) × (i2+1) × (i3+1) × … × (im+1). We would like this number to be odd. A product of whole numbers can only be odd if all of the original numbers were odd. So each of the {i1, i2, i3, …, im} must be even (and here zero is considered an even number).

This means that Q itself must be a perfect square number. Therefore, all reindeer behind stalls with perfect square numbered doors remain and, for 1,000 doors, there are 31 perfect squares less than or equal to 1,000.


Q.E.D.