:
: 【題目】已知 0≦X0<1 設 Xn+1 = 2*Xn if 2Xn <1
:
: = 2*Xn - 1 if 2Xn ≧1
:
: 則有____個X0 能符合條件 X5 = X0
:
: A. 0 B. 1 C. 15 D. 31 E. 無窮多個
:
: ( 1993 美國AMC12 )
先寫規規矩矩的解答，這個解也和前兩位的解法等價，只是瑣碎一點。
依據題義可以設 Xn+1 = 2*Xn - [2*Xn] , []代表高斯記號。
X5 = 2*X4 - [2*X4]
= 4*X3 - 2*[2*X3] - [4*X3 - 2*[2*X3]]
= 4*X3 - 2*[2*X3] - [4*X3] + 2*[2*X3]
= 4*X3 - [4*X3]
綠色部分的驗證可以分成 X3€[0,1/4), [1/4,1/2), [1/2,3/4), [3/4, 1)
四種情況均恆等無誤。
依此類推有 X5 = 32*X0 - [32*X0] = X0
因此得到 31*X0 = [32*X0] 是一整數 k ， X0 = k/31
由於 X0<1 k= 0~30 故有31解無誤
(以下是拙作，圖解法)
為避免圖形複雜，簡化成 X1=X0 的簡單情形
數線: 0 1/2 1
├────┼────┤
迭代事實上是一種映射關係。
觀察到位於 [0,1/2) 區間的點經1次迭代會位在 [0,1)區間某處。
T
事實上，[0,1/2) ─→ [0,1) 是線性映射(就是x2)，元素是1對1。
而 [1/2,1) 一樣 映射到 [0,1) (是x2-1)，1對1。
0 1/4 1/2 3/4 1
將數線四等分 ├──┼──┼──┼──┤
或八、十六、三十二等分的結果是一樣的。原題就是32個區間，各自映射到[0,1)。
NOTE:每個區間的映射法，正是前兩位解法中的 32a - n
結論是根據巴納赫不動點定理(壓縮映射，必存在唯一個不動點)
那解必然是每個區間一個，共32個解...等等，怎麼會這樣???????
那就是utomaya大在文章中提到的0.1111...等於1的問題。也就是上面每題，數線最後
一個區間的不動點是一個無窮接近1但不是1的數 (謎音: 那他就是1，拖出去)。因此
該區間沒有解滿足條件。
因此32個區間只有31個解。
另外，構造這些解的方法 utomaya大 上篇文中已經寫出來了。
-----------------------------------------------------------------------------
後記：解答寫一寫，沒想到卻發現每個人的解答都是相關聯的。真是法門萬變不離其宗。
當初準備考AMC12時解的考古題，昨天回去看發現完全看不懂過程。
因為計算處只畫了一個數線
0 1/4 1/2 1
├...┼───┼───────┼────────┼────────┤
然後在接近左邊的地方每格裡面打了一個x
我很確定當時不知道啥小巴拿赫不動點定理，因此以上算是我重新發掘解法的過程。
謝謝terrorlone、etrexetrex、utomaya的回答^^y
--
: 【題目】已知 0≦X0<1 設 Xn+1 = 2*Xn if 2Xn <1
:
: = 2*Xn - 1 if 2Xn ≧1
:
: 則有____個X0 能符合條件 X5 = X0
:
: A. 0 B. 1 C. 15 D. 31 E. 無窮多個
:
: ( 1993 美國AMC12 )
先寫規規矩矩的解答，這個解也和前兩位的解法等價，只是瑣碎一點。
依據題義可以設 Xn+1 = 2*Xn - [2*Xn] , []代表高斯記號。
X5 = 2*X4 - [2*X4]
= 4*X3 - 2*[2*X3] - [4*X3 - 2*[2*X3]]
= 4*X3 - 2*[2*X3] - [4*X3] + 2*[2*X3]
= 4*X3 - [4*X3]
綠色部分的驗證可以分成 X3€[0,1/4), [1/4,1/2), [1/2,3/4), [3/4, 1)
四種情況均恆等無誤。
依此類推有 X5 = 32*X0 - [32*X0] = X0
因此得到 31*X0 = [32*X0] 是一整數 k ， X0 = k/31
由於 X0<1 k= 0~30 故有31解無誤
(以下是拙作，圖解法)
為避免圖形複雜，簡化成 X1=X0 的簡單情形
數線: 0 1/2 1
├────┼────┤
迭代事實上是一種映射關係。
觀察到位於 [0,1/2) 區間的點經1次迭代會位在 [0,1)區間某處。
T
事實上，[0,1/2) ─→ [0,1) 是線性映射(就是x2)，元素是1對1。
而 [1/2,1) 一樣 映射到 [0,1) (是x2-1)，1對1。
0 1/4 1/2 3/4 1
將數線四等分 ├──┼──┼──┼──┤
或八、十六、三十二等分的結果是一樣的。原題就是32個區間，各自映射到[0,1)。
NOTE:每個區間的映射法，正是前兩位解法中的 32a - n
結論是根據巴納赫不動點定理(壓縮映射，必存在唯一個不動點)
那解必然是每個區間一個，共32個解...等等，怎麼會這樣???????
那就是utomaya大在文章中提到的0.1111...等於1的問題。也就是上面每題，數線最後
一個區間的不動點是一個無窮接近1但不是1的數 (謎音: 那他就是1，拖出去)。因此
該區間沒有解滿足條件。
因此32個區間只有31個解。
另外，構造這些解的方法 utomaya大 上篇文中已經寫出來了。
-----------------------------------------------------------------------------
後記：解答寫一寫，沒想到卻發現每個人的解答都是相關聯的。真是法門萬變不離其宗。
當初準備考AMC12時解的考古題，昨天回去看發現完全看不懂過程。
因為計算處只畫了一個數線
0 1/4 1/2 1
├...┼───┼───────┼────────┼────────┤
然後在接近左邊的地方每格裡面打了一個x
我很確定當時不知道啥小巴拿赫不動點定理，因此以上算是我重新發掘解法的過程。
謝謝terrorlone、etrexetrex、utomaya的回答^^y
--
All Comments