亮燈問題、楊輝三角與Sierpinski三角形

01-28

背景

　　在生日前幾天，我出了五道題作為有獎問答，亮燈問題作為第二題，一道規律題出場。答案很容易猜到——只需要模擬一下 $n=1$ 到 $n=4$ 的情況就可以猜到。然而給出一個證明卻並不那麼簡單，甚至可能涉及比表象深得多的東西。

亮燈問題

　　有 $n$ 盞燈環形排列，順時針依次標號為 $0..n-1$ 。初始時刻為 $0$ ，所有燈的亮滅（我們稱之為狀態）隨機。下一時刻每盞燈的亮滅取決於當前時刻這盞燈與順時針方向下一盞燈的亮滅。若兩盞燈狀態相同，則下一時刻該燈滅，否則該燈亮。

　　試求：當 $n$ 滿足什麼條件時，能保證在初始狀態隨機的情況下，時刻 $n$ 所有燈均為滅？

答案

$n=2^p quad (p in mathbb{N})$

證明

　　環形排列下，直接對燈的標號進行加減可能會出現越界的情況，所以我們需要對結果取模，即第 $i$ 盞燈順時針方向下 $k$ 盞燈為第 $(i+k) bmod n$ 盞燈。

　　定義 $S_t^i$ 表示時刻 $t$ 第 $i$ 盞燈的亮滅， $0$ 表示滅， $1$ 表示亮。

異或？

　　異或運算應用於邏輯運算（也可以看作為二進位下）。 $oplus$ 為異或運算符。其運演算法則相當於不帶進位的二進位加法： $0 oplus 0=0 1 oplus 0=1 0 oplus 1=1 1 oplus 1=0$

　　即二進位位相同則結果為 $0$ ，不同為 $1$ 。

　　根據異或運算的定義及題意，我們可以得到： $S_t^i=S_{t-1}^i oplus S_{t-1}^{(i+1)bmod n}$

　　又因為異或運算等價於不帶進位的加法，而我們只關注 $S_t^i$ 的奇偶，所以有： $S_t^i=left(S_{t-1}^i+S_{t-1}^{(i+1)bmod n}right) bmod 2$

　　由於在時刻 $t$ ，標號為 $i$ 的燈受到上一時刻標號 $i$ 、 $(i+1) bmod n$ 的燈的影響，而在時刻 $(t-1)$ ，標號 $(i+1) bmod n$ 燈受到時刻 $(t-2)$ 下標號 $(i+1) bmod n$ 、 $(i+2) bmod n$ 燈的影響。繼續推導可知，時刻 $t$ 下 $i$ 燈受到時刻 $0$ 下 $i$ 燈到 $(i+t) bmod n$ 燈初始狀態的影響，並且可能不止一次。

　　注意有 $a bmod p+b bmod p=(a+b) bmod p$ 的性質，所以方便起見，我們可以將取模運算放在最後操作。以下 $S$ 的值域將會擴充到自然數集，但是其意義仍為 $S bmod 2$ 。

受幾次影響？

　　定義 $Z_t^k$ 表示時刻 $t$ 下標號為 $i$ 的燈受到 $(i+k) bmod n$ 燈初始狀態的影響次數，則有： $S_t^i=sum_{j=0}^t Z_t^j S_0^{(i+j) bmod n}$

　　根據 $S$ 與 $Z$ 的定義，我們有： $S_{t+1}^i=sum_{j=0}^{t+1} Z_{t+1}^j S_0^{(i+j) bmod n}=S_t^i+S_t^{i+1}$

　　展開上式，得： $sum_{j=0}^{t+1} Z_{t+1}^j S_0^{(i+j) bmod n}=sum_{k=0}^t Z_t^k S_0^{(i+k) bmod n}+sum_{l=0}^t Z_t^l S_0^{(i+l+1) bmod n}$

　　因為 $Z$ 的定義，所以 $Z_t^{-1}$ 與 $Z_t^{t+1}$ 是無意義的，值為 $0$ ，則上式可改寫成下式形式： $begin{align}sum_{j=0}^{t+1} Z_{t+1}^j S_0^{(i+j) bmod n}&=sum_{k=0}^{t+1} Z_t^k S_0^{(i+k) bmod n}+sum_{l=0}^{t+1} Z_t^{l-1} S_0^{(i+l) bmod n} &=sum_{k=0}^{t+1} left(Z_t^k S_0^{(i+k) bmod n}+Z_t^{k-1} S_0^{(i+k) bmod n}right) &=sum_{k=0}^{t+1} left(Z_t^k+Z_t^{k-1}right) S_0^{(i+k) bmod n} end{align}$

　　所以有 $Z$ 的推導公式： $Z_{t+1}^k=Z_t^{k-1}+Z_t^k$

　　根據定義可以得到邊界條件： $Z_0^0=1$

　　不難發現 $Z$ 與 $C$ 的邊界條件與推導公式相同，則有： $Z_t^k=C_t^k$ ， $S_t^i=left(sum_{j=0}^t C_t^j S_0^{(i+j) bmod n}right) bmod 2$

均滅？

　　若時刻 $n$ 所有燈均滅，則上一時刻即時刻 $(n-1)$ 時，標號 $i$ 的燈應受所有燈影響或不受任何一燈影響。但通過 $C_{n-1}^k$ 的奇偶性我們發現，不受任何一燈影響是不可能的。則 $i$ 燈應受所有燈影響，即為： $C_{n-1}^k=1 quad (n in Result, k in mathbb{N}, 0 leq k leq n-1)$

　　不妨將 $C_t^k bmod 2$ 即楊輝三角對 $2$ 取模的圖形）列出來：

　　不難發現規律：第 $2^p-1$ 行符合全為 $1$ 的條件，也就是說，答案為 $n=2^p (p in mathbb{N})$ （別忘了 $n=1$ 的情況！）而如果我們將 $1$ 染為黑色等邊三角形，將 $0$ 染為白色等邊三角形（如圖），我們將得到Sierpinski三角形（謝爾賓斯基三角形）。Sierpinski三角形是分形圖形的一個經典圖形，在Matrix67的博客里也有提及。

Sierpinski三角形？

　　接下來，我們需要證明為什麼第 $2^p-1$ 行符合全為 $1$ 的條件。則我們需要證明： $C_{2^p-1}^k equiv 1 pmod 2 quad (k in mathbb{N}, 0 leq k leq 2^p-1)$

　　展開得： $frac{(2^p-1)!}{k!(2^p-1-k)!} equiv 1 pmod 2$

　　定義 $G_i$ 表示 $i$ 分解質因數後 $2$ 的個數。定義 $T_r^l=sum_{j=l}^r G_j$ ，則上式可由下式證得： $T_k^1=T_{2^p-1}^{2^p-k}$

　　若將 $i$ 寫為二進位，則 $G_i$ 為二進位下 $i$ 末尾 $0$ 的個數。不難發現有以下兩條性質： $G_i=G_{i+2^j} quad (i, j in mathbb{Z^{+}}, 2^j > i)$ ， $G_{2^j}=j quad (j in mathbb{Z^{+}})$

　　二進位下 $(i+2^j)$ 可由二進位下 $i$ 的第 $j$ 位由 $0$ 變 $1$ 得到，由於第 $j$ 位在限制條件下一定比 $i$ 的最高位更高，所以在第 $j$ 位添加 $1$ 對末尾 $0$ 的個數即 $G$ 無影響，第一條式子得證。第二條式子也可以根據 $G$ 的定義得到。

　　接下來我們需要證明：在 $1..2^p-1$ 的範圍內， $G$ 以 $2^{p-1}$ 為軸對稱。

　　首先注意到，在 $p=1$ 的條件下，該結論成立。我們需要將結論擴展到 $p in mathbb{Z^{+}}$ 。

　　若在 $1..2^p-1$ 範圍內， $G$ 以 $2^{p-1}$ 為軸對稱，則有： $G_i=G_{2^{p-1}+(2^{p-1}-i)}=G_{2^p-i}$

　　又因為 $G_i=G_{i+2^p}$ ，所以： $G_{i+2^p}=G_i=G_{2^p-i}$

　　並且有 $G_{2^p}=G_{2^p}$ ，所以在 $1..2^{p+1}-1$ 範圍內， $G$ 以 $2^p$ 為軸對稱。所以我們可以將 $p=1$ 下的結論擴展到 $p in mathbb{Z^{+}}$ 。

　　根據 $G$ 的對稱性，我們有下式成立： $T_k^1=T_{2^p-1}^{2^p-k}$

　　所以下式成立： $frac{(2^p-1)!}{k!(2^p-1-k)!} equiv 1 pmod 2$

　　得： $C_{2^p-1}^k equiv 1 pmod 2 quad (k in mathbb{N}, 0 leq k leq 2^p-1)$

　　得證。

　　根據第 $2^p-1$ 行均為 $1$ ，我們可以推得第 $2^p$ 行只有 $C_{2^p}^0$ 與 $C_{2^p}^{2^p}$ 為 $1$ ，其餘為 $0$ ，這兩個 $1$ 將分別向下擴展到 $2^{p+1}-1$ 行，形成與 $1$ 到 $2^p-1$ 行相同的Sierpinski三角形。

　　所以楊輝三角在對 $2$ 取模的情況下，將會形成Sierpinski三角形。

　　我們的問題也證明完畢，證得答案為 $n=2^p (p in mathbb{N})$ 。

　　本文同步發表於我的博客。

　　本人才疏學淺，難免有錯漏之處，請於評論區指正，謝謝。