數學題 - 有幾個解? - 拼圖

:
: 【題目】已知 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

--