推 chun10396974: 看懂了，謝謝 04/08 14:38
※ 引述《chun10396974 (娜嗲希摳老公)》之銘言：
: 手機排版請見諒
: Asymmetrical Numeral System中提到b unique的滿足條件是兩個區間符合這三個關係
: http://i.imgur.com/F4HVpyl.jpg
我下面會分別證明兩個命題
(下面 B 跟 L 我都用大寫)
I = {L, L+1, L+2, ... BL-1}
命題1： 如若x > BL-1 , 則存在唯一正整數k 使得 floor(x/B^k) 屬於 I
命題1的證明相對直觀
我們可以把比 BL-1 大的正整數們，
分成 [LB, LB^2-1], [LB^2, LB^3-1], ...... [LB^k, LB^(k+1)-1] . ....
這幾個區間，相互之間都沒有重疊，
所以 x 一定在某個區間 [LB^k, LB^(k+1)-1] 裡面
而在這個區間裡面，因為 LB^k <= x <= LB^(k+1)-1，
所以 L <= x/B^k <= LB - 1/B^k，
floor(x/B^k) 必然在 I 裡頭
命題2： 如果 x < L，
並任意給定一個數列 {d[i]}，此數列的任何一項都在 [0, B-1] 中。
定義一個新的數列 A[n] ：
A[0] = x
A[n+1] = BA[n] +d[n] ,for all n >= 1
則存在唯一正整數 k 使得 A[k] 在 I 裡頭
(你可能覺得這命題好像被我寫得面目全非，
但原本寫的那個 xB^k + d[1]B^(k-1) + .... + d[k] 其實就是 A[k])
首先呢，我們可以看出 A[n+1] - A[n] = (B-1)A[n] + d[n] > 0，
數列 A[n] 是個嚴格遞增的數列，
所以只要 n 夠大，A[n]會超過所有 I 裡面的數。
但這個數列又有一個性質，就是
如果 A[n] < L, 則 A[n+1] <= BL-1
也就是說，如果 A[n] 比 I 裡面所有的數都小，
那 A[n+1] 不可能比 I 裡面所有的數都大
證明這個也不難， A[n+1] = B*A[n] + d[n]
<= B*(L-1) + d[n] (A[n] <= L-1)
<= B*(L-1) + B-1 (d[n] <= B-1)
<= LB - 1
整理下來就是：(1) A[0] = x 比 I 裡面的數都小。
(2) A[n] 比 I裡面的數都小的時候，
A[n+1] 不可能比 I 裡面的數都大
(3) 因為 A[n] 嚴格地增，
所以會有某個 n 使得 A[n] 比 I 裡面所有的數都大
(1),(2),(3) => 存在某個正整數 k 使得 A[k] 落在 I 裡面
下一步就是證明：
如果 L <= A[k] <= LB-1，則 A[k-1] < L 且 A[k+1] > LB-1
這個直接計算就有了
--
早川秋看到的未來
https://i.imgur.com/aRFJqId.jpg
https://i.imgur.com/SXPvXGe.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 98.45.195.96 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1743742115.A.8C4.html
※ 編輯: arrenwu (98.45.195.96 美國), 04/05/2025 00:57:28