Re: [問題] 窗戶問題

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者arthurduh1 (arthurduh1)時間8年前 (2017/03/30 21:30)推噓0(0推 0噓 1→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《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 層的三角, 中間同樣補上零. 用歸納法就可以檢證此觀察. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.109.104.232 ※ 文章網址: https://www.ptt.cc/bbs/puzzle/M.1490880616.A.37E.html ※ 編輯: arthurduh1 (140.109.104.232), 03/30/2017 21:31:09