AoPS Wiki talk:Problem of the Day/August 23, 2011

Twenty bored students take turns walking down a hall that contains a row of closed lockers, numbered $1$ to $20$ . The first student opens all the lockers; the second student closes all the lockers numbered $2$ , $4$ , $6$ , $8$ , $10$ , $12$ , $14$ , $16$ , $18$ , $20$ ; the third student operates on the lockers numbered $3$ , $6$ , $9$ , $12$ , $15$ , $18$ : if a locker was closed, he opens it, and if a locker was open, he closes it; and so on. For the $i^{\text{th}}$ student, he works on the lockers numbered by multiples of $i$ : if a locker was closed, he opens it, and if a locker was open, he closes it. What is the number of the lockers that remain open after all the students finish their walks?

Locker n will be open at the end of the students' stampede if and only of the number of divisors it has is odd. For example, all the primes are opened by student $1$ and closed by student $p$ where $p$ is that prime. The only numbers with an odd number of factors are the perfect squares.

If you can see this, skip the following:
This can easily be seen: if $a$ is a natural number, all of its factors are in 'pairs' of distinct natural numbers except for its square root (if it has one) because, by definition, if $f|a$ , then $fm = a$ where $m$ is a perfect square. Unless $f = m$ , each factor is part of a pair, which means that the number of factors that are not square roots is even. This can also be shown by observing that if and only if $n$ has an even number of factors, the number of factors is odd (by the divisor function τ and basic parity) and it is a perfect square ( $p^{2k} = (p^k)^2$ ).

The largest perfect square under 20 is $16 = 4^2$ , so the answer is $4$ .

Page

Toolbox

Search

AoPS Wiki talk:Problem of the Day/August 23, 2011