環球城市數學競賽2008秋季賽高級卷高中組第五題

角谷猜想中，對任一數經3n+1運算和偶運算後，求其最大奇因數，重覆操作結果，最後都將降至1
設數列{Pn}，P1=1，Pn=4*Pn-1+1，則{Pn}=(1,5,21,85,341,......}
另一數列{Qn}，Qn=2Pn，則{Qn}={2,10,42,170,682,......}
我們可以觀察到，上述數列{Pn}和{Qn}僅一次3n+1運算和多次偶變換，可直接降至1，
而對於n=2^k，單以偶變換即可得到奇因數1，
當n=2^k-1，常常會運算至較大的奇數，且需經過較多次的運算最後才能降至1
基於上述理解，對於本題，直覺上由n=2^k，2^k-1，以及{Pn}及{Qn}切入發現：
n=(1,5,21,85,341,......)時an=(1,3,5,7,9,.....)
n={2,10,42,170,682,......)時an=(2,4,6,8,10,......)
n=2^k時，an=2
n=2^k-1時an=1，n=2^k+1時an=3
1.
證明：當n=2^k，k > =1時，an=2，an-1=1，an+1=3
對應數列{an}，設一數列{bn}，使得bn=an-an-1，此數列的
首幾項為：1、1、-1、1、1、-1、-1、1、1、1、-1、-1、1、-1、-1、…。
其前n項中奇數項總和設為S1(n)，偶數項總和設為S2(n)，前n項總和設為S(n)
則S(n)=S1(n)+S2(n)，據此可求an=ao+S(n)
設n=2^k，將所有奇數分成4p+1和4p+3型數字
其中2^(k-1)個奇數中4p+1型和4p+3型總數各佔2^(k-2)個，故S1(2^k)=0
而偶數項2*1,2*2,......2*2^(k-1)之最大奇因數分別等於1,2,3,.....2^(k-1)數列之最大奇因數
因此，S2(2^k)=S(2^(k-1))，故S(2^k)=0+S2(2^k)=S(2^k-1)，
由此可得S(2^k)=S(2^(k-1))=S(2^(k-2))=....=S2=S1=2

故n=2^k時，an=0+2=2，此時n-1=2^k-1，n+1=2^k+1分別屬於4p+3和4p+1型奇數，
因此an-1=1，an+1=3

2.
同上，當k > =1，n=2^(k+2)+2^k時，將{bn}分成二段，
前半段1~2^(k+2)及後半段2^(k+2)+1~2^(k+2)+2^k，已知前半段總和S(2^(k+2))=2
後半段4*(2^k)+1~4*(2^k)+2^k之最大奇因數等同於1~2^k數列之最大奇因數，
故後半段總和=S(2^k)，亦即n=2^(k+2)+2^k時S(n)=S(2^(k+2))+S(2^k)=2+2=4
同理n=2^k+2^(k+2)+2^(k+4)+.....+2^(k+2(p-1))時，S(n)=2p
由上可知，當2^(k-1) < n < 2^k
若k為偶數時，則可找到n=2+2^3+2^5+....+2^(k-1)時an=k
若k為奇數，則可找到n=1+2^2+2^4+....+2^(k-1)時an=k
因此，在2^(k-1)~2^k中，必存在第n項，使得an=k

3.
若2^(k-1) < n < 2^k-1 < 2^k且an=k，則自第n項起至第2^k-1項時an由k降至1
其間變化經+1或-1，則當中所出現的an值必包含1~k所有數字
亦即在2^(k-1) < n < 2^k區段出現的an值所成集合必為{1,2,3....,k}
由此可知在無窮數列{an}中所有無窮區段中，將陸續出現所有正整數，且一旦出現，
亦將於接下來的每個無窮區段中不斷地重覆出現

環球城市數學競賽非常適合學生科展的題材，本人十分感謝九章孫先生。
這一題已經給我的孩子去思考，希望，在人生旅途中留給孩子美好的回憶。
再度謝謝九章孫先生。

若n為奇數則其最大奇因數及為n本身
且其最大奇因數除以4於1或3
記1 2 3....n...最大奇因數除4的餘數為1 2 3..n...的餘數

當n 為偶數 則n可表為2^n*k 2=2*1 4=2*2 6=2*3……
固2 4 6 8 的最大奇因數及為1 2 3 4 的最大奇因數
1的數為1 3的餘數為3 5的餘數為1 故其數的餘數為1 3 1 3
2的餘數極為1的餘數極為1 4的餘數極為2的餘數極為1
6餘數極為3的餘數極為3 8餘數極為4的餘數極為1
.

1 2 3 ….n….的餘數
1 <1> 3 <1> 1 <3> 3 <1> 1 <1> 3 <3.> 1 <3>
未加<>及為奇數 由剛剛所述 可發現到前3巷為1 1 3
而家<>的前三項亦為1 1 3

因為相鄰2數就有一個奇數
故不會出現連序4巷相同者 最多只有3項


由提意知 餘數為1者及為前項加1……

所以只要再締k項到地k+p項中 3的各數比1多1個 或1的各數比3的各數多一個 則第k項和第k+p項極為相同的數 例如第1項和第3 項

再由此無窮數列的餘數數列的循環性得 每數都出現無窮多次

1 2 3 ….n….的餘數
1 3 1 3 1 3 1
未加及為奇數 由剛剛所述 可發現到前3巷為1 1 3
而家的前三項亦為1 1 3


更正 1 2 3 ….n….的餘數

1 /1/ 3 /1/ 1 ./3/ 3 /1/ 1 /1/ 3

未加/ /及為奇數 由剛剛所述 可發現到前3巷為1 1 3
而家/ /的前三項亦為1 1 3

謝謝九章，這一題可以使用二進位法處裡。
也謝謝所有幫忙過我的老師，謝謝。

這個題目被我引用來當做今年的台北縣科學展覽主題，報名到昨天才結束。今天，上網提出我的一些挫折和二進位法發現的理由。
.
一些定義
定義數列{dp(n)}：
設無窮數列{dp(n)}，dp(0)=0，n、k和q是自然數， p為質數，n=p^(k-1)×q， q和p互質。
若q除以p^後餘數小於((p^2)+1)/2，dp(n)=dp(n-1)+1；若q除以p2後餘數大於或等於((p^2)+1)/2則dp(n)=dp(n-1)-1。
很顯然，當質數p=2時，數列{a(n)}就是{d2(n)}。
.
ABCD法式我原先所創造的一種方法。理由是每逢a((2^k)-1)=1，因此，以4個一組的切法。雖然，最後無法被用來證明「{a(n)}會出現無窮多個正整數」，但是，今年（2009年）1月2日，數學網站公佈此一題目後，今年花了整個寒假利用ABCD法發現{a(n)}的一些性質。
定義「ABCD」法：
A的Y2（n）組合：（1、1、1、3），經整組運算後增減＋2，出現最高數字：第3個數
B的Y2（n）組合：（1、1、3、3），經整組運算後增減0，出現最高數字：第2個數。
C的Y2（n）組合：（3、1、1、3），經整組運算後增減＋2，出現最高數字：第3個數。
D的Y2（n）組合：（3、1、3、3），經整組運算後增減-2，出現最高數字：第1個數。
.
寒假，一直以「ABCD 法」思考數列{a（n）}以便尋找第k區間a(n)=k，雖然失敗，但卻也幫忙我對數列{a(n)}的認識。
發現二進位法的主要來源是「ABCD 法」是以*1*3的型式出現。
最重要的是老師們的提醒幫忙我很多，在此說一聲謝謝。

引用：

顏嘉佑 寫道:
謝謝九章，這一題可以使用二進位法處裡。
也謝謝所有幫忙過我的老師，謝謝。

感謝所有教過我的老師。
.
如果把十進位的n以二進位法表示，就可以很快找到由n變成a(n)值的方法，先看直觀觀察，再觀看二進位轉換法法的猜測規則。
1 =（1）2、3 =（11）2、7 =（111）2，對於十進位1、3、7，都是a(n)=1
2 =（10）2、4 =（100）2、6 =（110）2、8 =（1000）2，對於十進位2、4、6、8，都是a(n)=2，
5 =（101）2、9 =（1001）2，對於十進位5、9都是a(n)=3，
10=（1010）2，對於十進位10都是a(n)=4，
規則一：猜測連續出現111…111時，a(n)值都不會增加。
規則二：連續出現000…000時，a(n)值都不會增加。
規則三：增加1個10型，a(n)值會增加1。
規則四：增加1個01型，a(n)值會增加1。
規則五：減少1個10型，a(n)值會減少1。
規則六：減少1個01型，a(n)值會減少1。
規則七：由直觀觀察， a(n)值都發現少1個1，每個二進位法之前，再加1個0，最後計算01型的數目和10型的數目總和就成為a(n)值。

根據上面猜測規則舉例：如n=10=(1010)2，也就是十進位的10變成二進位的（1010）2。在1010前加1個0，使得（1010）2變成01010，再計算01010中，由右向左出現01有2次及10各有2次，總計01型式和10型式次數有4次。那麼a(10)=4。


再度感謝老師，若我的科展作品「奇妙的數列」在五月九日舉行的臺北縣賽能得到肯定，完全要感謝所有的老師。

您可以感謝九章及幫助過您的老師們，但讓人感覺到你所看中溝通的對象只有這個問題本身或者九章孫先生與您的老師們

謝謝!

引用：

笑哥 寫道:
您可以感謝九章及幫助過您的老師們，但讓人感覺到你所看中溝通的對象只有這個問題本身或者九章孫先生與您的老師們

剛開始，我是花了整個寒假以ABCD法破解這一題，老實說，很煩! 我雖找到一些眉目! 但，驗證的步驟很囉唆!
直到這學期剛開學時，我從泰國回台灣，再仔細看前輩的提示，我是有很大信心想克服!

今年二月中旬，老師帶學長參加台灣國際科學展覽碰到一位數學教授，提到另一位學長的科展作品有起死回生之路。
回到學校，老師向我提到別的學長科展作品，卻讓我回神，同時，今年同校的一位同學也有一篇拈的作品，讓我思考把十進位改成二進位法去觀察此一數列，結果，有更驚人的發現，就在台北縣縣科展交卷的前一天，連夜的更改作品內容，交出去!

從交出去作品之後，我好感動!
數學居然有這麼美麗!

當然，我還要感謝評審讓我有機會在縣賽發表我的作品。希望，比賽的那一天，有好的表現!
我更歡迎笑哥老師提供意見給我!

要感謝的人太多了!
九章的孫老師，我的學長，在國際科展向老師提起別的學長作品的教授，笑哥老師，學校老師的鼓勵，還有我的父母親，沒有逼我到補習班補數學，讓我有時間想科展的事!

我的老師常常提到學校學長的作品，尤其是這五年來學長的作品，我都仔細欣賞!
拈具有二進位的特色，還有台灣國際科展教授對學長作品的提示，應該是這個作品大量使用二進位法的主要原因!
謝謝曾經提醒老師的教授!
謝謝! 謝謝所有曾經幫忙我的老師! 當然，更要謝謝我的父母!

剛剛考完將江翠國中數理資優班初選，希望，我能通過，順利參加覆試，甚至於上榜!
謝謝各位老師!
謝謝!

引用：

顏嘉佑 寫道:
要感謝的人太多了!
九章的孫老師，我的學長，在國際科展向老師提起學長作品的教授，笑哥老師，學校老師的鼓勵，還有我的父母親，沒有逼我到補習班補數學，讓我有時間想科展的事!

拈具有二進位的特色，還有台灣國際科展教授對學長作品的提示，應該是這個作品大量使用二進位法的主要原因!

同學的科展作品[拈]也給我幫忙很多!
原因: 二進位法!

在國際科展向老師提起學長作品的教授，真的要好好的感謝!
謝謝!
若，這篇作品能被肯定，真的要好好感謝他!

引用：

笑哥 寫道:
您可以感謝九章及幫助過您的老師們，但讓人感覺到你所看中溝通的對象只有這個問題本身或者九章孫先生與您的老師們

謝謝笑哥老師!
換另一個角度思考:
在笑哥老師所提的方法，只能在第k區間存在一個自然數n使a(n)=k，也就是說存在性被證明，但，使用二進位髮就可以證明a(n)=k是唯一存在的。
只要設計n=(101010...)2再根據上面所提的二進位法七種規則，唯一性就可以被證明了。
此處的第k區間是指n介於2^(k-1)~~~2k-1之間。

也許，我學識還很低淺，還要改進的空間還很大，我很難從笑哥老師的方法中找到唯一性。

不知道說什麼好,我還在讀書呢
但原本大家應當在此分享心得
總之...
哎..
辛苦你了
要不是被逼我才懶得想這些題目呢
更懶得解釋什麼
對了,我智商才117,讀普通班
沒空補習,也不用做科展

謝謝笑哥老師
因為你的 2009-01-14 01:43提示，讓我有所突破，讓我幾乎想放棄此一題目的想法恢復動機，想克服這個題目，讓我有勇氣挑戰這個題目，謝謝!
當然，二進位法的想法幫忙我很多，再此說一聲謝謝!
謝謝各位前輩!

今天早上比賽完畢，很感謝我的父母及所有教過我的老師；尤其是笑哥老師的提示讓我找到存在性，台灣國際科展中和我的老師提到二進位法解決學長科展問題的老師!
雖然，第三次參加台北縣科展，但我還是很緊張，唯一性的定義還是沒有說好，不知道，有沒有機會代表台北縣到嘉義市的國展! 把二進位法介紹給數學前輩。
好緊張!
真希望，能有資格拿這篇作品參加國展!

最後，謝謝九章的孫老師! 笑哥老師! 所有教過我的老師!
謝謝!

謝謝!
謝謝孫老師和笑哥老師，這一題拿了國小數學科第三名!
謝謝!