In the UCLA Math Department’s basement, there are 100 lockers, numbered 1 to 100; the summer break also happens to be exactly 100 days long; and even the janitors are interested in numbers.
On the first day of summer, all the lockers are unlocked. The janitor then walks by and, for every locker, locks it if it was unlocked, and unlocks it if it was locked. (Since all the lockers were unlocked, that means he locks each one.)
On the second day, the janitor walks by and, for every 2nd locker starting with #2, locks it if it was unlocked, and unlocks it if it was locked. (Since all the lockers were locked after the first day, that means he unlocks each one.)
On the third day, he walks by and, for every 3rd locker starting with #3, locks it if it was unlocked, and unlocks it if it was locked. (Now, some lockers get locked and some unlocked.)
On the Nth day, of course, he walks by and, for every Nth locker starting with #N, locks it if it was unlocked, and unlocks it if it was locked.
After 100 days, how many lockers are locked?
(Click here for the answer.)
Answer: 10.
Each locker has its locked status reversed once for every divisor that it has — so locker #14, for instance, has that happened on day 1, 2, 7, and 14. Most positive integers have an even number of divisors, since if N is divisible by M, it’s also divisible by N/M; the divisors thus form pairs (M, N/M), so for 14 the pairs are (1,14) and (2,7).
But squares have an odd number of divisors, since in one of these pairs the numbers are equal — thus, 16 is divisible by the pairs (1,16), (2,8), and (4,4), for a total of 5 divisors. There are 10 squares between 1 and 100.
Many people think the answer will likely have something to do with the number of primes; I did at first. But that’s not so — primes have even numbers of divisors just like most numbers, to be precise 2 divisors.
(Note: “Most positive integers” here is shorthand for “most positive integers on any given interval 1 to N where N is 5 or more.” Technically, there are as many squares as there are positive integer nonsquares, as many positive integers divisible by a million as there are positive integers, as many primes as there are nonprimes, and so on. But that is a story for another day.)
(Hide the answer.)
Comments are closed.