A hallway contains 100 light bulbs and switches numbered 1 to 100, initially all switched OFF.
Nvidia technical mcq question, verified with a worked answer. Free to practise - no sign-up.
A hallway contains 100 light bulbs and switches numbered 1 to 100, initially all switched OFF. 100 people enter one by one:
- Person 1 toggles every switch (multiples of 1).
- Person 2 toggles switches that are multiples of 2 (2, 4, 6, ...).
- Person $k$ toggles switches that are multiples of $k$.
After all 100 people have passed through, which light bulbs remain ON?
Show answer & explanation
A light bulb remains ON if it is toggled an odd number of times. A bulb is toggled by person k if k is a divisor of the bulb's number; since only perfect squares have an odd number of divisors, only those bulbs remain ON.
Step-by-step Derivation:
Step 1: Define the state of bulb $n$. A bulb starts OFF. It is toggled by person $k$ if and only if $k$ is a divisor of $n$.
Step 2: The total number of times bulb $n$ is toggled is equal to the number of positive divisors of $n$, denoted as $d(n)$.
Step 3: A bulb is ON at the end if $d(n)$ is odd, and OFF if $d(n)$ is even.
Step 4: According to the fundamental theorem of arithmetic, any integer $n > 1$ can be written as $n = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}$. The number of divisors is $d(n) = (a_1 + 1)(a_2 + 1) \dots (a_m + 1)$.
Step 5: For $d(n)$ to be odd, every factor $(a_i + 1)$ must be odd, which means every exponent $a_i$ must be even.
Step 6: If all exponents in the prime factorization of $n$ are even, $n$ is a perfect square (i.e., $n = (p_1^{a_1/2} \dots p_m^{a_m/2})^2$).
Step 7: Identify perfect squares between 1 and 100: $1^2=1, 2^2=4, 3^2=9, 4^2=16, 5^2=25, 6^2=36, 7^2=49, 8^2=64, 9^2=81, 10^2=100$.