环形灯泡

Light Bulbs in circle

专题: Discrete Math / 离散数学
难度: L4
来源: Brainstellar

题目详情

圆环上有 $n$ 盏灯，编号 1 到 $n$ ，初始全亮。

在时间 $t$ ，检查第 $t$ 盏灯：若它亮，则切换第 $t+1$ 盏灯（模 $n$ 意义下），若它灭则不操作。

证明：不断绕圈执行该规则，最终所有灯会再次全部点亮。

In a circle are light bulbs numbered 1 through n, all initially on. At time t, you examine bulb number t, and if it’s on, you change the state of bulb t + 1 (modulo n); i.e., you turn it off if it’s on, and on if it’s off. If bulb t is off, you do nothing. Prove that if you continue around and around the ring in this manner, eventually all the bulbs will again be on.

Hint

It doesn't matter what the rules are, only thing that matters is that all bulbs should not go off!

解析

把“当前灯泡状态 + 指针位置（ $t\bmod n$ ）”视为系统状态。状态空间有限。

由于过程不会进入“全灭且无法继续变化”的死状态（并且每个状态都有唯一前驱），因此状态序列必在有限步后重复。

从两次相同状态向前回溯到起点，可推出某个时刻会回到初始状态（全亮）。

Original Explanation

Solution

Suppose every orientation of light bulbs & position of current pointer (t modulo n) forms a different state. Since all bulbs don’t go off, we must repeat a state after finite number of steps. Also notice that every state has a unique pre-state. Suppose the two states are at time T1 & T2. Notice that at time 0 all bulbs are on. Thus moving backwards from both states, we arrive at T2-T1, where all bulbs are on again.