---
description: "灯 $n$ 被拨 $d(n)$ 次，约数两两配对、只有完全平方数落单；100 盏里亮 10 盏"
---

# 100 盏灯的开关

## 题

100 盏灯编号 1–100，初始全灭。第 1 个人拨所有灯，第 2 个人拨所有 2 的倍数号，……，第 $k$ 个人拨所有 $k$ 的倍数号，一直到第 100 个人。"拨"指开变关、关变开。最后有几盏灯亮着？

## 一句话

亮着的恰好是**完全平方数号**：1, 4, 9, …, 100，共 **10 盏**。

## 关键技巧

换视角——不按人看，按灯看。第 $k$ 个人拨灯 $n$ $\iff$ $k \mid n$，所以灯 $n$ 一共被拨 $d(n)$ 次，$d(n)$ 是 $n$ 的约数个数。初始全灭，**亮 $\iff$ $d(n)$ 是奇数**。

约数天然成对：$k$ 是约数，$n/k$ 也是，二者一大一小。两两配对下来 $d(n)$ 是偶数——除非某个约数和自己配对，即 $k = n/k$，$n = k^2$。**只有完全平方数有一个落单的约数 $\sqrt n$。**

另一条路走素因子分解：$n = \prod p_i^{a_i}$ 时 $d(n) = \prod (a_i + 1)$。乘积为奇 $\iff$ 每个 $a_i + 1$ 都奇 $\iff$ 每个指数 $a_i$ 都偶 $\iff$ $n$ 是平方数。

## 解

两个例子对照着看：

| 灯号 | 约数配对 | $d(n)$ | 结局 |
| --- | --- | --- | --- |
| 12 | $1 \cdot 12,\ 2 \cdot 6,\ 3 \cdot 4$ | 6 | 灭 |
| 36 | $1 \cdot 36,\ 2 \cdot 18,\ 3 \cdot 12,\ 4 \cdot 9,\ 6 \cdot 6$ | 9 | 亮 |

36 的 $6 \cdot 6$ 只算一个约数，所以是 9 次不是 10 次。1–100 里的平方数是 $1^2, 2^2, \ldots, 10^2$，**亮 10 盏**；$N$ 盏灯时亮 $\lfloor \sqrt N \rfloor$ 盏。

## 延伸

- **常见错误**：以为质数号灯亮着——质数恰有 1 和自身两个约数，被拨 2 次，灭。
- **第 1 个人缺席**：每盏灯少拨一次，奇偶全反，非平方数亮，共 **90 盏**。
- **只有奇数号的人拨**：灯 $n$ 被拨的次数 = 奇约数个数。写 $n = 2^a m$（$m$ 奇），奇约数个数就是 $d(m)$，奇 $\iff$ $m$ 是平方数 $\iff$ $n$ 是平方数或平方数的 2 倍。100 盏里亮 **17 盏**：1, 2, 4, 8, 9, 16, 18, 25, 32, 36, 49, 50, 64, 72, 81, 98, 100。
- **只有质数号的人拨**：灯 $n$ 被拨 $\omega(n)$ 次（不同素因子的个数），亮 $\iff$ $\omega(n)$ 奇。1 没有素因子，灭；$30 = 2 \cdot 3 \cdot 5$ 亮，$6 = 2 \cdot 3$ 灭。100 盏里亮 **43 盏**——这里没有平方数那样整齐的结构，只能数。
- **只有前 50 人拨**：灯 $n \le 50$ 的约数全在场，还是平方数亮，7 盏；灯 $51 \le n \le 100$ 只缺了约数 $n$ 自己（它的其他约数都 $\le n/2 \le 50$），奇偶翻转，非平方数亮，$50 - 3 = 47$ 盏（去掉 64、81、100）。合计 **54 盏**。
- **拨得最多的灯**：60、72、84、90、96，各被拨 12 次。
- **总共拨了多少次**：按人数是 $\sum_k \lfloor 100/k \rfloor$，按灯数是 $\sum_n d(n)$，同一个双重计数，都是 **482**。Dirichlet 的约数和估计 $\sum_{n \le N} d(n) = N \ln N + (2\gamma - 1)N + O(\sqrt N)$ 给 476，差 6 在 $O(\sqrt N)$ 之内。平均每盏灯被拨约 $\ln N$ 次。
- **同款技巧**：把"按操作者统计"换成"按被操作对象统计"，再用配对抵消，是奇偶性题的通用开局——[12 枚硬币的奇偶性](coin-parity.md) 用的是另一种抵消，$(-1)^X$ 的乘积。

??? note "数值验证"

    直接模拟 100 个人拨灯，再对照约数个数：

    ```python
    import math

    N = 100
    def run(who):
        """who 里的每个人 k 依次拨 k 的倍数号灯，返回最后亮着的灯号。"""
        on = [False] * (N + 1)
        for k in who:
            for m in range(k, N + 1, k):
                on[m] = not on[m]
        return [i for i in range(1, N + 1) if on[i]]

    print(run(range(1, N + 1)))        # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
    primes = [p for p in range(2, N + 1) if all(p % q for q in range(2, math.isqrt(p) + 1))]
    omega = lambda n: sum(n % p == 0 for p in primes)
    r = run(primes)
    print(len(r), r == [n for n in range(1, N + 1) if omega(n) % 2])   # 43 True
    print(run(range(1, N + 1, 2)))     # [1, 2, 4, 8, 9, 16, 18, 25, 32, 36, 49, 50, 64, 72, 81, 98, 100]
    print(len(run(range(2, N + 1))))   # 90   第 1 人缺席
    print(len(run(range(1, 51))))      # 54   只有前 50 人

    d = [0] + [sum(n % k == 0 for k in range(1, n + 1)) for n in range(1, N + 1)]
    print(max(d), [n for n in range(1, N + 1) if d[n] == max(d)])     # 12 [60, 72, 84, 90, 96]
    print(sum(d), sum(N // k for k in range(1, N + 1)))                # 482 482
    print(N * math.log(N) + (2 * 0.5772156649 - 1) * N)                # 475.96015157880913
    ```