[具体数学]第三章·整值函数

第三章·整值函数分5节，包括底和顶的相关知识以及取模运算。底和顶（即取整函数）在许多问题以及编程中经常用到，很重要。

底和顶及其应用

\(\lfloor x\rfloor,\lceil x\rceil\) 定义不说了，就是向下/向上取整，书中翻译为“底”和“顶”。

性质： \[ \lceil x\rceil-\lfloor x\rfloor=[x不是整数] \]

反射律： \[ \lfloor-x\rfloor=-\lceil x\rceil\quad\lceil-x\rceil=-\lfloor x\rfloor \]

互相转化：对 \(\forall n\in\mathbb Z,m\in\mathbb N^*\)，有： \[ \left\lceil\frac{n}{m}\right\rceil=\left\lfloor\frac{n+m-1}{m}\right\rfloor \] 证：两边同时减去 \(\left\lfloor\frac{n}{m}\right\rfloor\) 有： \[ \begin{align} 左式&=\left\lceil\frac{n}{m}\right\rceil-\left\lfloor\frac{n}{m}\right\rfloor=[m\nmid n]\\ 右式&=\left\lfloor\frac{n+m-1}{m}\right\rfloor-\left\lfloor\frac{n}{m}\right\rfloor=1-\left(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor\right)=1-[m\mid n] \end{align} \] 其中，右式最后一步基于：\(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor=[m\mid n]\)，证一下：若 \(m\mid n\)，显然 \(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor=1\)；否则，设 \(n=km+r\;(1\leqslant r<m)\)，则 \(\left\lfloor\frac{n}{m}\right\rfloor=k\)，\(\left\lfloor\frac{n-1}{m}\right\rfloor=\left\lfloor k+\frac{r-1}{m}\right\rfloor=k\)（注意 \(0\leqslant \frac{r-1}{m}<1\)），所以 \(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor=0\)；综上，\(\left\lfloor\frac{n}{m}\right\rfloor-\left\lfloor\frac{n-1}{m}\right\rfloor=[m\mid n]\).

显然，\(左式=[m\nmid n]=1-[m\mid n]=右式\)，证毕。

分数部分： \[ \{x\}=x-\lfloor x\rfloor \]

常用法则

常用法则：取整函数等式与不等式之间的转化 \[ \boxed{\begin{align} \lfloor x\rfloor=n\iff n\leqslant x<n+1\iff x-1<n\leqslant x\\ \lceil x\rceil=n\iff n-1<x\leqslant n\iff x\leqslant n<x+1 \end{align}}\tag{1} \]

上述法则很简单很显然，但是也很重要，证明的时候可以用来把取整符号去掉。

常用法则：实数和整数之间的任何不等式都等价于整数之间的一个有关取整函数的不等式。 \[ \boxed{\begin{align} x<n&\iff \lfloor x\rfloor< n\\ n<x&\iff n<\lceil x\rceil\\ x\leqslant n&\iff\lceil x\rceil\leqslant n\\ n\leqslant x&\iff n\leqslant\lfloor x\rfloor \end{align}}\tag{2} \]

上述法则很容易证明，也很重要。

一个非常有用的定理

设 \(f(x)\) 是任意一个具有如下性质且在一个实数区间连续的单调递增函数： \[ f(x)=整数\implies x=整数 \] 那么我们有： \[ \begin{align} \left\lfloor f\left(\lfloor x\rfloor\right)\right\rfloor=\left\lfloor f(x)\right\rfloor\\ \left\lceil f\left(\lceil x\rceil\right)\right\rceil=\left\lceil f(x)\right\rceil \end{align} \] 证明：只对底进行证明，顶的情况类似。若 \(x\) 是整数，显然成立；否则，\(\lfloor x\rfloor<x\)，由于 \(f(x)\) 单调递增，有：\(f\left(\lfloor x\rfloor\right)<f(x)\)，于是 \(\left\lfloor f\left(\lfloor x\rfloor\right)\right\rfloor\leqslant\left\lfloor f(x)\right\rfloor\)。假若 \(\left\lfloor f\left(\lfloor x\rfloor\right)\right\rfloor<\left\lfloor f(x)\right\rfloor\)，由连续性知，介值定理成立：存在一个 \(y\in\left(\lfloor x\rfloor,x\right]\)，使得 \(f(y)=\left\lfloor f(x)\right\rfloor\)。根据 \(f(x)\) 的题设性质可知，\(y\) 是整数，然而我们无法在 \(\left(\lfloor x\rfloor,x\right]\) 中找到一个整数，故假设不成立。综上，\(\left\lfloor f\left(\lfloor x\rfloor\right)\right\rfloor=\left\lfloor f(x)\right\rfloor\). \(\square\)

为什么说这个定理很有用呢？它可以推导出： \[ \left\lfloor\frac{\left\lfloor x\right\rfloor+m}{n}\right\rfloor=\left\lfloor\frac{x+m}{n}\right\rfloor \] 这是取 \(f(x)=\frac{x+m}{n}\) 得到的结果。进一步特殊化，有： \[ \left\lfloor\frac{\left\lfloor \frac{a}{b}\right\rfloor}{c}\right\rfloor=\left\lfloor\frac{a}{bc}\right\rfloor \] 这一点在写代码的时候很有用啊。比如在推导一些数论函数的题的时候，就会经常遇到上述式子。

另外，如果我们取 \(f(x)=\sqrt x\)，可以知道： \[ \left\lfloor\sqrt{\lfloor x\rfloor}\right\rfloor=\left\lfloor\sqrt x\right\rfloor,\;\left\lceil\sqrt{\lceil x\rceil}\right\rceil=\left\lceil\sqrt x\right\rceil \]

区间内整数个数

区间	整数个数	限制条件
\([\alpha\cdots\beta]\)	\(\lfloor\beta\rfloor-\lceil\alpha\rceil+1\)	\(\alpha\leqslant\beta\)
\([\alpha\cdots\beta)\)	\(\lceil\beta\rceil-\lceil\alpha\rceil\)	\(\alpha\leqslant\beta\)
\((\alpha\cdots\beta]\)	\(\lfloor\beta\rfloor-\lfloor\alpha\rfloor\)	\(\alpha\leqslant\beta\)
\((\alpha\cdots\beta)\)	\(\lceil\beta\rceil-\lfloor\alpha\rfloor-1\)	\(\alpha<\beta\)

来看一个例子

求： \[ \sum_{n=1}^N\big[\left\lfloor\sqrt[3]{n}\right\rfloor\mid n\big] \] 解： \[ \begin{align} \sum_{n=1}^N\big[\left\lfloor\sqrt[3]{n}\right\rfloor\mid n\big]&=\sum_{n=1}^{N}\sum_{k\mid N}\big[k=\left\lfloor\sqrt[3]{n}\right\rfloor\big]&&枚举\;k\\ &=\sum_{k=1}^{K}\sum_{m=1}^{\left\lfloor\frac{N}{k}\right\rfloor}\big[k=\left\lfloor\sqrt[3]{n}\right\rfloor\big]&&设\;K=\left\lfloor\sqrt[3]{N}\right\rfloor，求和号换序并置\;n=km\\ &=\sum_{k=1}^{K-1}\sum_{m=1}^{\left\lfloor\frac{N}{k}\right\rfloor}[k^3\leqslant km<(k+1)^3]+\sum_{m}[K^3\leqslant Km\leqslant N] &&用不等式转化，注意最后一项单独计算\\ &=\sum_{k=1}^{K-1}\sum_{m=1}^{\left\lfloor\frac{N}{k}\right\rfloor}\left[m\in\left[k^2,\frac{(k+1)^3}{k}\right)\right]+\sum_{m}\left[m\in\left[K^2,\frac{N}{K}\right]\right]\\ &=\left(\sum_{k=1}^N\left\lceil k^2+3k+3+\frac{1}{k}\right\rceil-\lceil k^2\rceil\right)+\left\lfloor\frac{N}{K}\right\rfloor-\lceil K^2\rceil+1&&应用区间内整数个数的结论\\ &=\left(\sum_{k=1}^{K-1}3k+4\right)+\left\lfloor\frac{N}{K}\right\rfloor-K^2+1\\ &=\frac{(K-1)(3K+8)}{2}+\left\lfloor\frac{N}{K}\right\rfloor-K^2+1\\ &=\frac{1}{2}K^2+\frac{5}{2}K-3+\left\lfloor\frac{N}{K}\right\rfloor \end{align} \]

常用法则\((1)\) 中的不等式在上述证明中起到了关键的作用，否则我们无法很好地处理向下取整。

谱

定义实数 \(\alpha\) 的谱（spectrum）是一个无限多重集合： \[ \text{Spec}(\alpha)=\left\{ \lfloor\alpha\rfloor,\lfloor2\alpha\rfloor,\lfloor3\alpha\rfloor,\cdots \right\} \] 性质：

• 没有两个实数的谱相等。

  证明：假设 \(\alpha<\beta\)，则必定存在 \(N\) 使得 \(N(\beta-\alpha)\geqslant 1\)，则 \(N\beta\geqslant N\alpha+1\)，故 \(\lfloor N\beta\rfloor>\lfloor N\alpha\rfloor\)，它们的谱在 \(N\) 处不相等。\(\square\)

• \(\text{Spec}(\alpha)\) 和 \(\text{Spec}(\beta)\) 给出了正整数的一个划分当且仅当 \(\alpha,\beta\) 均是无理数且 \(\frac{1}{\alpha}+\frac{1}{\beta}=1\). （例如 \(\text{Spec}(2)\) 和 \(\text{Spec}(2+\sqrt 2)\) 给出了正整数的一个划分）

  证：充分性：只需要证明对于任意的 \(n\)，\(\text{Spec}(\alpha)\) 中 \(\leqslant n\) 的元素个数 \(N(\alpha,n)\) 和 \(\text{Spec}(\beta)\) 中 \(\leqslant n\) 的元素个数 \(N(\beta,n)\) 之和为 \(n\) 即可。\(N\) 可如下求得： \[ \begin{align} N(\alpha,n)&=\sum_{k>0}\big[\lfloor k\alpha\rfloor\leqslant n\big]\\ &=\sum_{k>0}\big[\lfloor k\alpha\rfloor<n+1\big]\\ &=\sum_{k>0}\big[k\alpha<n+1\big]&&常用法则(2)\\ &=\sum_k\left[0<k<\frac{n+1}{\alpha}\right]\\ &=\left\lceil\frac{n+1}{\alpha}\right\rceil-1 \end{align} \] 于是 \[ \begin{align} N(\alpha,n)+N(\beta,n)&=\left\lceil\frac{n+1}{\alpha}\right\rceil-1+\left\lceil\frac{n+1}{\beta}\right\rceil-1=\left\lfloor\frac{n+1}{\alpha}\right\rfloor+\left\lfloor\frac{n+1}{\beta}\right\rfloor\\ &=\frac{n+1}{\alpha}+\frac{n+1}{\beta}-\left\{\frac{n+1}{\alpha}\right\}-\left\{\frac{n+1}{\beta}\right\}\\ &=n+1-\left[\left\{\frac{n+1}{\alpha}\right\}+\left\{\frac{n+1}{\beta}\right\}\right]\\ &=n \end{align} \] （注：上面的证明多次用到了 \(\frac{n+1}{\alpha}\) 和 \(\frac{n+1}{\beta}\) 必然是小数的条件。）

  必要性：若 \(\alpha\) 是有理数，那么 \(\beta=\frac{1}{1-\frac{1}{\alpha}}\) 也是有理数，把它们写成分数，设它们分子的最小公倍数为 \(m\)，那么二者的谱中都会出现 \(m\) 这个数，不能构成一个划分，故 \(\alpha,\beta\) 均为无理数。此时，\(N(\alpha,n)+N(\beta,n)=(n+1)\left(\frac{1}{\alpha}+\frac{1}{\beta}\right)-1=n\)，解得：\(\frac{1}{\alpha}+\frac{1}{\beta}=1\). 证毕。

针对第二个性质，\(\textbf{Solomon W. Golomb}\) 在他的论文 \(\text{The 'Sales Tax' Theorem}\) 中指出，当 \(\frac{1}{\alpha}+\frac{1}{\beta}=1\) 时（不要求无理数），\(\{\lfloor n\alpha\rfloor\mid n\geqslant 1\}\) 和 \(\{\lceil n\beta\rceil-1\mid n\geqslant 1\}\) 总会构成一个划分。

底和顶的递归式

高德纳数

\[ \begin{cases} K_0=1\\K_{n+1}=1+\min\left(2K_{\lfloor n/2\rfloor},3K_{\lfloor n/3\rfloor}\right) \end{cases} \]

证明或证伪： \[ K_n\geqslant n \] 证：我们来证一个更强的结论： \[ K_n>n \] 归纳法：首先，\(K_0=1>0\) 成立；其次，假设对 \(K_0\cdots K_n\) 都成立，那么 \(K_{\lfloor n/2\rfloor}>\lfloor n/2\rfloor\)，注意到 \(K_{\lfloor n/2\rfloor}\) 是整数，所以由常用法则\((2)\)可知： \[ K_{\lfloor n/2\rfloor}>n/2 \] 同理， \[ K_{\lfloor n/3\rfloor}>n/3 \] 所以， \[ K_{n+1}=1+\min\left(2K_{\lfloor n/2\rfloor},3K_{\lfloor n/3\rfloor}\right)>1+\min(2\cdot n/2+3\cdot n/3)=1+n \] 证毕。

一件很有趣的事情是，这个更强的结论容易归纳证明，但是原来更弱的结论却难以归纳证明。

如果我们尝试对原结论归纳，会有： \[ K_{n+1}=1+\min\left(2K_{\lfloor n/2\rfloor},3K_{\lfloor n/3\rfloor}\right)\geqslant1+\min\left(2\left\lfloor \frac{n}{2}\right\rfloor,3\left\lfloor \frac{n}{3}\right\rfloor\right) \] 然而，\(2\left\lfloor\frac{n}{2}\right\rfloor\) 可以小到 \(n-1\)（当 \(n\) 是奇数时），\(3\left\lfloor\frac{n}{3}\right\rfloor\) 可以小到 \(n-2\)（当 \(n=3k+2\) 时），所以我们只能得到： \[ K_{n+1}\geqslant1+\min(n-1,n-2)=n-1 \] 不能归纳出结论。

这种现象在证明时还是比较常见的，即证明更强的结论反而更简单。数学之有趣大概于此。

再论约瑟夫问题

我们不从递归式，而是换一种角度思考约瑟夫问题。这里探究每隔 \(q-1\) 个人死一个的一般情形。我们不断地指定新的编号：刚开始是 \(1,2,\cdots,n\)，随后 \(1\) 号变成 \(n+1\) 号、……、\(q-1\) 号变成 \(n+q-1\) 号，\(q\) 号处死，\(q+1\) 号变成 \(n+q\) 号，\(q+2\) 号变成 \(n+q+1\) 号……，\(2q\) 号处死，\(2q+1\) 号变成 \(n+2q-1\) 号，……，\(kq+1\) 号变成 \(n+kq+1-k=n+(q-1)k+1\) 号，……，最后剩下 \(qn\) 号。

上面一段话没人想看，举个例子好了：\(n=10\)，\(q=3\) 时，编号是这样变化的： \[ \begin{matrix} 1&2&3&4&5&6&7&8&9&10\\ 11&12&&13&14&&15&16&&17\\ 18&&&19&20&&&21&&22\\ &&&23&24&&&&&25\\ &&&26&&&&&&27\\ &&&28\\ &&&29\\ &&&30 \end{matrix} \]

如何理解上述编号过程？想象两个指针一前一后的扫，前一个指针从 \(1\) 开始递增地、遇到一个数就赋值；后一个指针遇到 \(q\) 的倍数就把它删掉（删掉的数不被第一个指针赋值）。于是乎，当一个数被赋值为 \(q\) 的倍数时，它就被敲响了丧钟。

对于编号 \(qk+r\;(1\leqslant r<q)\)，我们考虑它的下一个编号是多少。\(qk+r\) 意味着它被下一次赋值时，会有 \(k\) 个人死亡，所以它的下一个编号是 \(qk+r+(n-k)\)；反过来，编号 \(N=n+k(q-1)+r\;(1\leqslant r<q)\) 的上一个编号就是 \(qk+r=qk+N-n-k(q-1)=N-n+k\)。由于我们已经知道最后一个存活的人是 \(qn\)，所以可以据此逆推出幸存者的原号码： \[ \begin{align} &N:=qn\\ &\textbf{while}\quad N>n\quad\textbf{do}\quad N:=\left\lfloor\frac{N-n-1}{q-1}\right\rfloor+N-n\\ &J_q(n):=N \end{align} \] 如果作变量代换：\(D=qn+1-N\)，上述代码可以简化： \[ \begin{align} &D=1\\ &\textbf{while}\quad D\leqslant(q-1)n\quad\textbf{do}\quad D:=\left\lceil\frac{q}{q-1}D\right\rceil\\ &J_q(n):=qn+1-D \end{align} \]

\(\bmod\)：二元运算

定义

\[ x\bmod y=x-y\lfloor x/y\rfloor,\quad y\neq0 \]

注意上述定义中，\(x,y\in\mathbb{R}\).

特殊定义： \[ x\bmod0=x \]

\(\LaTeX\) 里，\bmod 能像其他二元运算符一样打出一个漂亮的 \(\bmod\)，而如果直接用 \mod 前后会有一大片空格。

另外，同余式中用 \pmod，它会自动在两边加上括号，例如：\(x\equiv1\pmod m\) 的代码是：x\equiv1\pmod m.

务必注意不同的编程语言中的模运算和数学语言的 \(\bmod\) 可能会有差别。

例如： \[ \begin{align} &5\bmod 3=2\\ &5\bmod-3=5-(-3)\lfloor5/(-3)\rfloor=-1\\ &-5\bmod3=-5-3\lfloor(-5)/3\rfloor=1\\ &-5\bmod-3=-5-(-3)\lfloor(-5)/(-3)\rfloor=-2 \end{align} \] 而在 \(\text{C++}\) 下：

5 % 3 = 2
5 % (-3) = 2
(-5) % 3 = -2
(-5) % (-3) = -2

但是 \(\text{python}\) 下与数学语言又是一致的：

>>> 5%3
2
>>> 5%(-3)
-1
>>> (-5)%3
1
>>> (-5)%(-3)
-2

分配律

对 \(\forall c,x,y\in\mathbb R\)，有： \[ c(x\bmod y)=(cx)\bmod(cy) \] 证明： \[ c(x\bmod y)=c(x-y\lfloor x /y\rfloor)=cx-cy\lfloor x/y\rfloor=(cx)-(cy)\lfloor(cx)/(cy)\rfloor=(cx)\bmod (cy) \] \(\square\)

一个例子

把 \(n\) 个物品分成 \(m\) 组，把组按照不增的次序排列，使分得尽可能均匀。

答案很简单：前 \(n\bmod m\) 组分 \(\left\lceil\frac{n}{m}\right\rceil\) 个，后 \(m-n\bmod m\) 组分 \(\left\lfloor\frac{n}{m}\right\rfloor\) 个。

如果问第 \(k\) 组有多少个物品，我们想找到一个式子，当 \(k\leqslant n\bmod m\) 时值为 \(\left\lceil\frac{n}{m}\right\rceil\)，当 \(k>n\bmod m\) 时值为 \(\left\lfloor\frac{n}{m}\right\rfloor\). 可以验证，答案是： \[ \text{num}(k)=\left\lceil\frac{n-k+1}{m}\right\rceil \] 又根据 \(\sum\limits_{k=1}^m\text{num}(k)=n\)，我们可以得到一个恒等式： \[ n=\left\lceil\frac{n}{m}\right\rceil+\left\lceil\frac{n-1}{m}\right\rceil+\cdots+\left\lceil\frac{n-m+1}{m}\right\rceil \] 该式对 \(\forall n\in\mathbb Z,\,m\in\mathbb{N}^*\) 恒成立。

对应的，如果把原题改成不减，我们也可以得到一个恒等式： \[ n=\left\lfloor\frac{n}{m}\right\rfloor+\left\lfloor\frac{n+1}{m}\right\rfloor+\cdots+\left\lfloor\frac{n+m-1}{m}\right\rfloor \]

底和顶的和式

我们不是很能直接处理取整函数，所以往往一个有效的技巧是引入变量来规避取整。

第一个例子

求 \[ \sum_{0\leqslant k<n}\lfloor\sqrt k\rfloor \] 的封闭形式。

解： \[ \begin{align} \sum_{0\leqslant k<n}\lfloor\sqrt k\rfloor&=\sum_{m,k\geqslant 0}m[k<n]\big[m=\lfloor\sqrt k\rfloor\big]&&变量替换\\ &=\sum_{m,k\geqslant 0}m[k< n][\sqrt k-1<m\leqslant \sqrt k]&&常用法则(1)\\ &=\sum_{m,k\geqslant 0}m[k< n][m^2\leqslant k<(m+1)^2]\\ &=\sum_{m,k\geqslant 0}m[m^2\leqslant k<(m+1)^2\leqslant n]+\sum_{m,k\geqslant 0}m[m^2\leqslant k< n<(m+1)^2]&&拆分 \end{align} \] 其中，第一个和式计算如下： \[ \begin{align} \sum_{m,k\geqslant 0}m[m^2\leqslant k<(m+1)^2\leqslant n]&=\sum_{0\leqslant m\leqslant \lfloor\sqrt n\rfloor-1}m\left((m+1)^2-m^2\right)\\ &=\sum_0^{a-1}2m^2+m&&记\;a=\lfloor\sqrt n\rfloor\\ &=2\cdot\frac{(a-1)a(2a-1)}{6}+\frac{a(a-1)}{2}\\ &=\frac{2}{3}a^3-\frac{1}{2}a^2-\frac{1}{6}a \end{align} \] 第二个和式计算如下： \[ \sum_{m,k\geqslant 0}m[m^2\leqslant k< n<(m+1)^2]=a(n-a^2) \] （注意到仅当 \(m=a=\lfloor\sqrt n\rfloor\) 的时候才满足条件）

因此， \[ \sum_{0\leqslant k<n}\lfloor\sqrt k\rfloor=\frac{2}{3}a^3-\frac{1}{2}a^2-\frac{1}{6}a+na-a^3=na-\frac{1}{3}a^3-\frac{1}{2}a^2-\frac{1}{6}a \]

第二个例子

接下来两个大坑先留着。。。