具體數學-第7課（取整基礎）

05-22

具體數學-第7課（取整基礎）

來自專欄自然語言處理與深度學習

原文鏈接：

具體數學-第7課 - WeiYang Blog?

godweiyang.com

首先聲明一下，最近這段時間忙畢設，沒時間更新博客了，大家見諒。

今天這節課開始講解取整相關知識，主要是數論相關的了。

符號定義

向下取整函數 $leftlfloor x ight floor$ 定義為小於等於 $x$ 的最大整數。

向上取整函數 $leftlceil x ight ceil$ 定義為大於等於 $x$ 的最小整數。

${ x}$ 定義為實數 $x$ 的小數部分，即

${ x} = x - leftlfloor x ight floor$

性質

性質1

$leftlceil x ight ceil - leftlfloor x ight floor = [x in mathbb{Z}]$

性質2

取整函數範圍：

$x - 1 < leftlfloor x ight floor le x le leftlceil x ight ceil < x + 1$

性質3

負數的取整：

$egin{array}{l}leftlfloor { - x} ight floor = - leftlceil x ight ceil \leftlceil { - x} ight ceil = - leftlfloor x ight floor end{array}$

性質4

取整函數中的整數可以提取出來：

$leftlfloor {x + n} ight floor = leftlfloor x ight floor + n$

應用

應用1

證明：

$leftlfloor {sqrt {leftlfloor x ight floor } } ight floor = leftlfloor {sqrt x } ight floor$

更一般的，我們還可以證明，對於任意連續、遞增的函數 $f(x)$ ，如果它滿足

$f(x) in mathbb{Z} Rightarrow x in mathbb{Z}$

那麼有

$egin{array}{l}leftlfloor {f(x)} ight floor = leftlfloor {f(leftlfloor x ight floor )} ight floor \leftlceil {f(x)} ight ceil = leftlceil {f(leftlceil x ight ceil )} ight ceil end{array}$

我們證明第2個式子，第1個同理可證。

如果 $x = leftlceil x ight ceil$ ，顯然成立。

否則 $x < leftlceil x ight ceil$ ，因為 $f(x)$ 遞增，所以有

$f(x) < f(leftlceil x ight ceil )$

兩邊同時取整，有

$leftlceil {f(x)} ight ceil le leftlceil {f(leftlceil x ight ceil )} ight ceil$

要證左右兩邊相等，那麼只要證

$leftlceil {f(x)} ight ceil < leftlceil {f(leftlceil x ight ceil )} ight ceil$

不成立即可。假設上式成立，那麼由中間值定理，一定存在 $x le y < leftlceil x ight ceil$ ，使得

$f(y) = leftlceil {f(x)} ight ceil$

敲黑板！！這裡是怎麼來的呢？

由下圖可以看出，當下面式子成立時，滿足中間值定理

$f(x) < leftlceil {f(x)} ight ceil < f(leftlceil x ight ceil )$

但是在這裡，我們假設是

$leftlceil {f(x)} ight ceil < leftlceil {f(leftlceil x ight ceil )} ight ceil$

那麼由 $leftlceil {f(x)} ight ceil < leftlceil {f(leftlceil x ight ceil )} ight ceil$ 能否推出 $leftlceil {f(x)} ight ceil < f(leftlceil x ight ceil )$ 呢？當然是可以的。

$egin{array}{l}leftlceil {f(x)} ight ceil < leftlceil {f(leftlceil x ight ceil )} ight ceil \ Rightarrow leftlceil {f(x)} ight ceil le leftlceil {f(leftlceil x ight ceil )} ight ceil - 1 < f(leftlceil x ight ceil )end{array}$

所以

$f(y) in mathbb{Z} Rightarrow y in mathbb{Z}$

又因為 $x le y < leftlceil x ight ceil$ ，所以不存在整數 $y$ ，矛盾！

所以證得

$leftlceil {f(x)} ight ceil = leftlceil {f(leftlceil x ight ceil )} ight ceil$

另一個特殊的例子是

$leftlfloor {frac{ {x + m}}{n}} ight floor = leftlfloor {frac{ {leftlfloor x ight floor + m}}{n}} ight floor$

其中 $m$ 和 $n$ 都是整數，並且 $n$ 是正整數。

應用2

接著介紹區間相關的性質。

求1到1000中使得下列式子成立的 $n$ 一共有多少個？

$leftlfloor {sqrt[3]{n}} ight floor |n$

求解方法如下：

$egin{array}{l}W{ m{ = }}sumlimits_{1 le n le 1000} {left[ {leftlfloor {sqrt[3]{n}} ight floor |n} ight]} \ = sumlimits_{k,n} {left[ {k = leftlfloor {sqrt[3]{n}} ight floor } ight]left[ {k|n} ight]left[ {1 le n le 1000} ight]} \ = sumlimits_{k,m,n} {left[ { {k^3} le n < { {(k + 1)}^3}} ight]left[ {n = km} ight]} left[ {1 le n le 1000} ight]\ = 1 + sumlimits_{k,m} {left[ { {k^3} le km < { {(k + 1)}^3}} ight]} left[ {1 le k < 10} ight]\ = 1 + sumlimits_{k,m} {left[ {m in [{k^2},{ {(k + 1)}^3}/k)} ight]} left[ {1 le k < 10} ight]\ = 1 + sumlimits_{1 le k < 10} {(leftlceil { {k^2} + 3k + 3 + 1/k} ight ceil - leftlceil { {k^2}} ight ceil )} \ = 1 + sumlimits_{1 le k < 10} {(3k + 4)} \ = 172end{array}$

繼續推廣，求1到 $N$ 中使得上面式子成立的 $n$ 有多少個？

令

$K = leftlfloor {sqrt[3]{N}} ight floor$

也就是小於等於 $leftlfloor {sqrt[3]{N}} ight floor$ 的最大整數。

所以

$egin{array}{l}W = sumlimits_{1 le k < K} {(3k + 4)} + sumlimits_m {left[ { {K^3} le Km le N} ight]} \ = leftlfloor {N/K} ight floor + frac{1}{2}{K^2} + frac{5}{2}K - 3end{array}$

漸進地等於

$W = frac{3}{2}{N^{2/3}} + O({N^{1/3}})$

應用3

定義一個實數的譜為：

$Spec(alpha ) = { leftlfloor alpha ight floor ,leftlfloor {2alpha } ight floor ,leftlfloor {3alpha } ight floor , ldots }$

很容易證明如果兩個實數 $alpha e eta$ ，那麼

$Spec(alpha ) e Spec(eta )$

假設 $alpha < eta$ ，那麼令

$m(eta - alpha ) ge 1$

所以

$meta ge malpha + 1 Rightarrow leftlfloor {meta } ight floor > leftlfloor {malpha } ight floor$

所以集合 $Spec(eta )$ 中小於 $leftlfloor {malpha } ight floor$ 的元素個數小於 $m$ 。而集合 $Spec(alpha )$ 中小於 $leftlfloor {malpha } ight floor$ 的元素個數大於等於 $m$ 。所以兩個集合不相等。

譜有很多奇妙的性質，例如下面兩個譜：

$egin{array}{l}Spec(sqrt 2 ) = { leftlfloor {sqrt 2 } ight floor ,leftlfloor {2sqrt 2 } ight floor ,leftlfloor {3sqrt 2 } ight floor , ldots } \Spec(2{ m{ + }}sqrt 2 ) = { leftlfloor {2{ m{ + }}sqrt 2 } ight floor ,leftlfloor {2(2{ m{ + }}sqrt 2 )} ight floor ,leftlfloor {3(2{ m{ + }}sqrt 2 )} ight floor , ldots } end{array}$

可以發現，這兩個譜正好劃分了正整數集。

證明方法也很簡單，只要證明對任意正整數 $n$ ，兩個集合中小於 $n$ 的元素個數之和為 $n$ ，過程如下：

$egin{array}{l}leftlfloor {ksqrt 2 } ight floor le n\ Rightarrow ksqrt 2 < n + 1\ Rightarrow k < frac{ {n + 1}}{ {sqrt 2 }}end{array}$

所以第一個集合中小於 $n$ 的元素個數為

$leftlfloor {frac{ {n + 1}}{ {sqrt 2 }}} ight floor$

同理第二個集合中小於 $n$ 的元素個數為

$leftlfloor {frac{ {n + 1}}{ {2 + sqrt 2 }}} ight floor$

所以總個數為

$egin{array}{l}leftlfloor {frac{ {n + 1}}{ {sqrt 2 }}} ight floor + leftlfloor {frac{ {n + 1}}{ {2 + sqrt 2 }}} ight floor \ = leftlfloor {frac{ {sqrt 2 }}{2}(n + 1)} ight floor + leftlfloor {frac{ {2 - sqrt 2 }}{2}(n + 1)} ight floor \ = n + 1 + leftlfloor {frac{ {sqrt 2 }}{2}(n + 1)} ight floor + leftlfloor { - frac{ {sqrt 2 }}{2}(n + 1)} ight floor \ = n + 1 + leftlfloor {frac{ {sqrt 2 }}{2}(n + 1)} ight floor + leftlfloor {frac{ {sqrt 2 }}{2}(n + 1)} ight floor - 1\ = nend{array}$

得證。