97高中數學競賽台中區複賽一第二題
[size=3]用0,1,2組成字串，但相鄰的三個位置不得出現"0,1,2"(按此順序)。[/size][size=3]令\( a_n \)為滿足上述條件且長度為n的字串個數。[/size]
[size=3]試求出\( a_n \)為6的倍數的充要條件。[/size]
我的解法:
先推出遞迴式\( \displaystyle a_n=3a_{n-1}-a_{n-3} \)
以及初值\( a_1=3，a_2=9，a_3=26 \)
然後有恆心有毅力去算除以6的餘數
終於找到42個一循環
依序為
[color=red]3,3,2[/color],3,[color=blue]0[/color],4,3,3,5,[color=blue]0[/color],
3,4,[color=blue]0[/color],3,5,3,[color=blue]0[/color],1,[color=blue]0,0[/color],
5,3,3,4,3,[color=blue]0[/color],2,3,3,1,
[color=blue]0[/color],3,2,[color=blue]0[/color],3,1,3,[color=blue]0[/color],5,[color=blue]0[/color],
[color=blue]0[/color],1,[color=red]3,3,2,[/color]
[color=#ff0000][/color]
[color=black]也就是每42個裡面的第5,10,13,17,19,20,26,31,34,38,40,41個是6的倍數[/color]
想請問是否正確?
如果是的話，那麼答案該如何寫??
不懂這裡所謂的"充要條件"意指何?或者是有別的看法
尤其是各位台中區的老師
複賽這幾題我卡了好久好久 Number of ternary (0,1,2) sequences without a consecutive '012'
[url]http://www.research.att.com/~njas/sequences/A076264[/url]
有提到a(n) = 3*a(n-1)-a(n-3)這個遞迴式，但沒看到和mod 6有關係的式子
最後的答案就硬算吧 小弟也曾試著直接去推敲，
也是發現如上文中的 \(\displaystyle a_n=\sum_{k=0}^{\left[n/3\right]} \left(-1\right)^k C^{n-2k}_{k} 3^{n-3k} \)，
然後想到分成 \(\pmod{2},\;\pmod{3}\)去討論。
1. 對於 \(\pmod{3}\) 的部分： \(\displaystyle a_n \not\equiv 0\pmod{3}\;\Leftrightarrow\;3\Big| n.\)
2. 對於 \(\pmod{2}\) 的部分： \(\displaystyle a_n\equiv\sum_{k=0}^{\left[n/3\right]} C^{n-2k}_{k} \pmod{2} \) ，再來就沒蝦咪頭緒了。 補上整份題目和答案 感謝瑋岳老師和bugmens提供的答案
我是沒有想到要分成2和3去討論
頁:
[1]
