數理邏輯的解題方法

Question

隨便寫下一個0與1的排列 , 假如連續兩個相同的話 , 在它們下面寫一個0 , 假如不同的話 , 寫下一個1 , 重覆這過程直到你只剩下一個阿拉伯數字 , 你能預測最後1個數字是什麼嗎 ? 最後K個數字ㄋ??? 奉上20點，感恩
0 1 0 1 0 1 1
1 1 1 1 1 0
0 0 0 0 1
0 0 0 1
0 0 1
0 1
1
......

Answer 1

我們考慮一種運算，有a,b,c,d,e,f六個數，把它寫在第一排，下一排每個數是上一排的連續兩個數之和，用代數的方法，看它的係數會如何變化。如下：a,b,c,d,e,f(a+b),(b+c),(c+d),(d+e),(e+f)(a+2b+c),(b+2c+d),(c+2d+e),(d+2e+f)(a+3b+3c+d),(b+3c+3d+e),(c+3d+3e+f)(a+4b+6c+4d+e),(b+4c+6d+4e+f)a+5b+10c+10d+5e+f於是我們發現每一排的係數都是巴斯卡三角形的係數往下增加，於是我們歸納，假設一開始的數是a0a1a2....an，最後一個數是x，則x≡C(n,0)*a0+C(n,1)*a1+C(n,2)*a2....+C(n,n)*an(mod 2)不過乘以0等於沒乘，所以只算1的部份就好，以你的數字0101011為例，x≡C(6,1)+C(6,3)+C(6,5)+C(6,6)≡6+20+6+1≡1(mod 2)但是這樣還不夠簡化，如果我們把巴斯卡三角形的奇偶性也考慮進去，以模數2重寫一遍：11101111110001110011101010111111111100000001110000001110100000101111100001111.......好，還是以你的數字為例，它有7個數，那就取巴斯卡三角形恰有7個數那一排，上下並排，分別上乘以下再加起來1010101(巴斯卡)*******0101011(你的數)x≡1*0+0*1+1*0+0*1+1*0+0*1+1*1≡1(mod 2)又因為乘以0等於沒乘，所以「上有0」或「下有0」就不算，只取上下都是1者來相加，於是又簡化成x≡1*1(mod 2)