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\) 是平方数。

解

两个例子对照着看：

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 枚硬币的奇偶性 用的是另一种抵消，\((-1)^X\) 的乘积。

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