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

看板Math作者chun10396974 (娜嗲希摳老公)時間8月前 (2025/04/09 10:42)推噓5(5推 0噓 17→)

留言22則, 2人參與討論串3/3 (看更多)

※ 引述《arrenwu (最是清楚哇她咩)》之銘言： : 我下面會分別證明兩個命題 : (下面 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 想再請教一個問題，為何對於某區間 I={L, L+1, ..., BL-1} 給定一任意x<L，只要選擇Is的長度是(B-1)x，亦即Is={x, x+1, ..., Bx-1} 就能確保利用您所證明的正整數k之對應關係，能夠覆蓋整個I ----- Sent from JPTT on my Samsung SM-G9980. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.75.241 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1744166550.A.365.html

推

arrenwu

04/09 11:53, 8月前 , 1^F

04/09 11:53, 1^F

→

chun10396974

04/09 13:31, 8月前 , 2^F

04/09 13:31, 2^F

→

chun10396974

04/09 13:35, 8月前 , 3^F

04/09 13:35, 3^F