Learn / Library / Brainteasers

Only odd walkers

BrainteasersMedium

A gym has $100$ lockers numbered $1$ to $100$ , all closed. Only the students with odd numbers walk past, $k = 1, 3, 5, \dots, 99$ , and student $k$ changes the state of 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

Locker $n$ is touched once for each odd divisor of $n$ .

Solution

Write $n = 2^{a} \times m$ with $m$ odd; locker $n$ is touched once per divisor of $m$ .
That count is odd exactly when $m$ is a perfect square, so $n$ is a square or a square multiplied by $2$ .
Up to $100$ there are $10$ squares and $7$ numbers of the form $2 j^{2}$ : $2$ , $8$ , $18$ , $32$ , $50$ , $72$ and $98$ .
So $10 + 7 = 17$ lockers are open.

Answer: $17$

Next question Back to the library