Light Bulb Toggling After 100th Person

This brain teaser revisits a classic hallway of light bulbs and a sequence of people toggling them, but now asks only about the configuration after a fixed number of passes. The candidate must reason about which bulbs have been affected how many times, and infer a pattern that lets them count and identify the final "on" bulbs without simulating each toggle. It is framed as a neat, finite puzzle rather than an open-ended proof question, making it a common warm-up or screening question in puzzle-heavy interviews and introductory quant or software screens.

The problem leans on number-theoretic structure rather than computation. A strong answer recognizes that each bulb's final state is determined by the parity of the number of times it is toggled, which in turn depends on the divisor structure of its position label. The interviewer is watching for recognition of divisor pairing, the special role of perfect squares, and the ability to convert that insight into a concrete count and an explicit list. Clarity in explaining the pattern and checking extremal cases matters as much as getting the final numbers correct.

What it tests

The core structure here is that the number of times an action is applied to an object is determined by the number of divisors of its label, and that divisors naturally come in pairs unless the number is a perfect square. For any positive integer $n$, its divisors can be listed as pairs $(d, n/d)$, so the total count is even unless $n$ is a perfect square, in which case one divisor is repeated (the square root), making the count odd. This means that in any process where an object's state flips with each divisor, only perfect squares will end up in a different state than the rest. The reason this pattern holds is that the structure of integer divisors is fundamentally paired except when symmetry (a square root) creates a singleton. This insight generalizes to any situation where an object's state depends on the parity of the number of its divisors.