100 盏灯

编号为完全平方数的灯会亮着：$1,4,9,16,\dots,100$。

原因：第 $k$ 盏灯会在所有能整除 $k$ 的轮次被切换一次，总切换次数等于 $k$ 的因子个数。只有完全平方数的因子个数为奇数（因为 $\sqrt{k}$ 这一因子成对合并后会“单独剩一个”），因此只有完全平方数最后保持“开”。

---

Original Explanation

10 bulbs

Solution

Observation

Draw a small grid of 6x6 on a piece of paper and simulate the outcome.

Observe that each bulb is toggled as many times as many unique divisors it has. For example, bulb number 6 has divisors [1,2,3,6], so it is toggled back and forth by person number [1,2,3,6], i.e, 4 times.

In this case, only the bulb number $1$ and $4$ are ON at the end of 6 steps, and they have odd number of divisors. Can it be that perfect square number have odd unique divisors?

Checking for some more numbers:

• Divisors for $9$ are $[1,3,9]$, hence $3$ toggles
• Divisors for $16$ are $[1,2,4,8,16]$, hence $5$ toggles

Hence we form a conjecture: For perfect squared numbers, the count of unique factors is always odd.

Proof: Divisors are always found in pairs. For number $K$ if we find one divisor $d_1$ then we also just found another divisor $d_2 = K/d_1$. The divisor count would increase by 2, unless $d_1 = d_2$ which happens exactly once for a perfect square and never for any other number.

Note that for a non-square number, the count of unique divisors are always even.

A bulb at position $K$ is toggled between ON / OFF states only by the person whose number is divisor of $K$. When $K$ is a perfect square number then the bulb will be ON at the end because of the odd sequence of toggling. For all the other numbers, the bulb will be OFF because of the even sequence of toggling.

Thus bulbs 1,4,9....81,100 are ON, at the end.

Hence 10 bulbs are on.

Generalization

If there are $n$ bulbs in a sequence and $n$ people, then the number of bulbs that are ON at the end is $\lfloor \sqrt{n} \rfloor$

Divisor Formula

Let $n$ be a positive integer and $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ is the prime factorization of $n$

In how many different ways can we form a divisor?

Let $d$ be a divisor of $n$, $d = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$ where $0 \le a_i \le e_i$.

Thus, there are $e_i + 1$ choices for each prime factor $p_i$, indepdently for each $i$.

Thus, the total number of divisors of $n$ is given by

$\tau(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$

If $n$ is a perfect square, then each $e_i$ is even, so $e_i + 1$ is odd. Therefore, the product $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$ is odd.