Learn / Library / Brainteasers

Corridor of lamps

BrainteasersEasy

A corridor has $200$ lamps numbered $1$ to $200$ , all off. For each $k$ from $1$ to $200$ in turn, a technician presses the switch of every lamp whose number is a multiple of $k$ ; each press turns a lamp on if it is off and off if it is on. How many lamps are on at the end?

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

Hint

A lamp is pressed once for each divisor of its number.

Solution

Lamp $n$ is pressed once for every divisor of $n$ , and it ends on exactly when that count is odd.
Divisors pair up as $d$ and $\frac{n}{d}$ , so the count is odd only when some divisor is paired with itself, that is when $n$ is a perfect square.
The squares up to $200$ are $1^{2}$ to $1 4^{2}$ , since $1 4^{2} = 196$ and $1 5^{2} = 225$ .
So $14$ lamps are on.

Answer: $14$

Next question Back to the library