時間 (2025-04-09 10:42:27)

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

--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 111.83.75.241 (臺灣)
※ 文章網址: https://pttweb.tw/Math/M.1744166550.A.365

#1推 : 什麼東西能夠覆蓋整個 I？04/09 11:53

#2→ : Is能夠覆蓋I04/09 13:31

#3 例如第一篇文中的I=[8, 15]04/09 13:35

#4 而若x=3，則Is=[3, 3×2-1]可以完全覆蓋04/09 13:35

#5 若x=2，則Is=[2, 2×2-1]可以完全覆蓋04/09 13:35

#6 假如x=3，但是Is只取[3, 4]就會導致I中的10和11找不04/09 13:41

#7 到其在Is中的對應者04/09 13:41

#8推 : 你說的是原圖裡面的 (12)？04/10 08:53

#9 能否把你想要證明的結果寫成一個定理的形式？04/10 08:53

#10 你所有的描述都還在自然語言的範疇，非常模糊04/10 08:53

#11 所謂的Is覆蓋 I 是怎麼個覆蓋法？04/10 09:37

#12→ : 我描述的不是很清楚，04/10 11:07

#13 我想問的是為何只要Interval Is滿足[x, x+1, ..., B04/10 11:07

#14 x-1]，那就能保證Is符合原圖中的(12)04/10 11:07

#15推 : 那張圖裡面的 C(s,x) 和 C(s,Is) 是啥意思？04/10 11:36

C(s, x)指的就是先前您證明的正整數k之對應關係，當前state為x，在收到輸入symbol為s?
※ 編輯: chun10396974 (111.83.75.241 臺灣), 04/11/2025 08:23:38

#16 你有你原本那張圖的來源嗎？04/11 10:03

https://arxiv.org/pdf/1311.2540
※ 編輯: chun10396974 (111.83.75.241 臺灣), 04/11/2025 10:11:24
※ 編輯: chun10396974 (111.83.75.241 臺灣), 04/11/2025 10:14:07

#17→ : C的定義在第八頁的下方04/11 10:14

#18推 : 他這個2014 Jan 6 的版本看起來跟你最原本貼的好像04/13 11:12

#19 有落差了。你方便指出你現在想證明的結論是在Jan 604/13 11:12

#20 版本的哪部分嗎？04/13 11:12

#21→ : 欲證給定第九頁的方程式(9)，只要選取Is=[x, Bx-1]04/14 17:06

#22 ，必能滿足方程式(10)的關係04/14 17:06

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

同標題文章