窗戶問題 - 拼圖

※ 引述《ddtddt (得)》之銘言：
: 第i層樓一共有i個窗戶如下圖:
: ..........
: ........
: 窗窗窗
: 窗窗
: 窗
: 窗戶的開關是有規則的，
: 若兩相鄰的窗戶同為開或同為關，則他們下面的窗戶必為關。
: 若兩相鄰的窗戶為一開一關，則他們下面的窗戶必為開。
: 如圖:
: 關開關
: 開開
: 關
: Q:已知第1024樓有513個窗戶是打開的，請問一樓的窗戶是開還關?














1 代表開, 0 代表關的話,
兩窗戶的狀態取 xor 相加恰好就會是他們下面那個窗戶的狀態.

假設已經知道第 i 層的各個窗戶狀態,
則第 1 層那唯一一個窗戶的狀態便能一步一步展開成第 i 層的某些窗戶狀態之和.

舉個例子:

x_{3,1} x_{3,2} x_{3,3}
x_{2,1} x_{2,2}
x_{1,1}


x_{1,1} = x_{2,1} + x_{2,2}
= x_{3,1} + 2x_{3,2} + x_{3,3} = x_{3,1} + x_{3,3}

其實係數就是二項式係數(黃色部分),
而且因為我們取的是 xor 加法, 事實上我們只要關心除 2 之後的餘數,
也就是奇偶性即可(紫色部分).

帕斯卡三角形取除 2 之餘數的極限形狀,
會趨近於一個碎形, 也就是 LPH66 大提示的 Sierpinski's triangle. (應該吧@@)

-----

回到原題,
我們只要知道帕斯卡三角形第 1024 層各個數字的奇偶性, 就有機會把可能性化約.

幸運地, 第 2^k 層的數字全部都會是奇數,
因此 x_{1,1} = 第 1024 層所有窗戶的狀態之和 = 513 = 1(mod 2)

-----

至於為啥都會全是奇數, 就有各種各類的證明.

比如從碎形的角度來看,
第 2 層恰好會是兩個第 1 層並排;
第 3~4 層恰好會是兩個第 1~2 層的三角形放在一起, 中間有個全零的倒三角;
第 5~8 層則是兩個 1~4 層的三角, 中間同樣補上零.

用歸納法就可以檢證此觀察.


























--