※ 引述《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://webptt.com/cn.aspx?n=bbs/puzzle/M.1490880616.A.37E.html ※ 编辑: arthurduh1 (140.109.104.232), 03/30/2017 21:31:09