Ads
關呀
關呀
我諗到就係chok head=1 tail=0
跟住乘一個
(110000....
011000.....
..................
100......001)既matrix A
跟住計A^n不過好似好濕濟 :^(
其實就係咁做
不過喺Z_2唔算太難，上面解釋咗點做
Ads
我會咁樣formulate個題目
given n, consider A=(Z_2)^n
for (x1,...,xn), define s(x1,...,xn)=(xn,x1,...,x_{n-1})
（其實s只係permutation matrix)
question: for which n, x+s(x)+s^2(x)+...=0 for all x?
繼續
最後打錯咗，個game每一步可以睇成咁：
如果x係initial configuration,咁x+s(x)就係下一步嘅configuration（如果唔明嘅話可以問，我再解釋）
如果寫1做identity matrix, x+s(x)=(1+s)x, 即係每步只係乘同一個matrix
所以問題係：for which n, (1+s)^m x=0 for all x in A, when m is sufficiently large?
答案係if and only if n=2^k for some k
首先一個fact: consider (1+s)^2^k,咁你爆開佢嘅話所有coefficient都係雙數，除咗頭同尾嗰個，呢個用MI就證明到
因為依家個matrix啲entry係Z_2嘅數字，所以當個coefficient係雙數，佢會變咗0，所以(1+s)^2^k=1+s^2^k
但係當n=2^k時，s^2^k=s^n=1,而1+1=0，所以(1+s)^2^k = 0 when n=2^k
另一個case, n唔係2^k咁嘅樣
aim: show that there exists x such that (1+s)^m x is not 0 for infinitely many m
因為當有一步變咗0就代表就game會完，如果aim入面講嘅嘢係存在，咁就game就唔會完
let k be any number with 2^k>n. by剛才嘅argument,(1+s)^2^k = 1+s^2^k
但依個情況n除唔盡2^k，所以1+s^2^k=1+s^l for some l<n(因為s^n=1,l其實只係2^k除以n嘅餘數）
consider x=(1,0,0,...0)
明顯地(1+s^l)(x)唔等於0
以上依家事就對於任何k都啱，即係對於無限個k啱，即係(1+s)^2^k x is not 0 for infinitely many k, QED
Ads