※ 引述《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. (應該吧@@)