Learn / Library / Brainteasers

Half open to begin with

BrainteasersHard

$1000$ lockers are numbered $1$ to $1000$ . At the start every even-numbered locker is open and every odd-numbered locker is closed. Then for each $k$ from $1$ to $1000$ , student $k$ toggles every locker whose number is a multiple of $k$ , opening it if closed and closing it if open. How many lockers are open at the end?

Checking an answer needs JavaScript. The hint and the solution open without it.

Hint

Combine the starting state with the parity of the number of divisors.

Solution

Locker $n$ changes state once per divisor of $n$ , so only the perfect squares change state an odd number of times.
So a non-square keeps its starting state and a square ends in the opposite state.
Up to $1000$ there are $31$ squares, since $3 1^{2} = 961$ and $3 2^{2} = 1024$ ; of these, $15$ are even and $16$ are odd.
Open at the end are the even non-squares, $500 - 15 = 485$ of them, and the odd squares, $16$ of them.
So $485 + 16 = 501$ lockers are open.

Answer: $501$

Next question Back to the library