# Locker Problem & Solution

/This problem is brought to us by our instructor Zandra Vinegar, who authored the hints, explanation, and solution below.

### If you haven't solved this puzzle yet, try tackling it in parts:

*What doors are affected in the 5th round of the game?*

Solution: In the 5th round, the doors that are affected (opened if they are closed and closed if they are open) are doors 5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, and 100 -- all multiples of 5. So door 30, as an example, is affected because it is divisible by 5. Another way to say this is to say that locker 30 is affected because 5 is a *factor* of 30.

*Altogether, during which rounds is door 30 opened or closed?*

Solution: the rules of the game cause a door to be affected in the rounds of every number which divides it. For 30, these instances will be rounds 1, 2, 3, 5, 6, 10, 15, and 30. Therefore, locker 30 is opened in round 1, then shut in round 2, opened in round 3, shut in round 5, opened in round 6, shut in round 10, opened in round 15, and finally shut in round 30. None of the rest of the rounds affect locker 30 at all, so locker 30 winds up shut.

We could continue checking cases this way, and ultimately, we could solve this puzzle by counting the factors of every number. This would be a valid solution, but there's an easier way! Because we only want to know if the door winds up open or shut, we don't need to know exactly when or how many times it's been affected, only if the number of times is even or odd. The lockers all start out shut, so if a locker's state is changed an even number of times (6, for example: open, shut, open shut, open shut), then the locker will be shut at the end of the game. But any locker that is affected an odd number of times (affected 3 times, for example: open shut open), such a locker will be open at the end of the game. So the puzzle we need to solve becomes: *When does a number have an odd number of factors? *

Solution: A number will only have an odd number of factors *if it is a perfect square, such as 1 (= 1*1), 4 (=2*2), 9 (=*3*3), 16 ( =4*4), 25 (=5*5) and so on.

All numbers that are not perfect squares have an even number of factors - in fact, they come in natural pairs. If you find one factor of a number; for example, say you remember that 30 is divisible by 5; then you can use division by 5 to find another new divisor of 30: 30/5 is 6, so 6 is a factor of 30 as well. The only case in which we wouldn't get a *new* factor with this method is if the number is a perfect square, such as 36, and if we divided it by its square root: 36/6 is 6, which we already had! So any number that is not a perfect square will have an even number of factors. 30, has 4 pairs of factors: (1, 30), (2, 15), (3, 10), and (5, 6). And perfect squares have an odd number of factors, such as 16 which has the factors 1, 2, 4, 8, and 16. Therefore, locker 16 is open at the end of the game.

Try thinking about this first. Once you think you have a good answer, you can check your solution here.