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

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.164.15.141 我突然覺得同餘式或者 n進位 在解題時是很威的工具。 ※ 編輯: jurian0101 來自: 218.164.15.141 (02/03 18:02)