時間 (2025-04-04 12:48:33)

推文1則 (1推 0噓 0→)
※ 引述《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

--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 98.45.195.96 (美國)
※ 文章網址: https://pttweb.tw/Math/M.1743742115.A.8C4
※ 編輯: arrenwu (98.45.195.96 美國), 04/05/2025 00:57:28

#1推 : 看懂了，謝謝04/08 14:38

Re: [代數] 證明集合對應關係

同標題文章