写在前面

今天(2022.12.7)的lc每日一题, 虽然是中等但也有很多需要注意的点, 看到了0x3f大佬的题解才发现自己知识点的太多不足, 比如下面这个式子:(出自具体数学练习3.12) \(\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1.\) 本文主要给出取整函数的一些内容, 包括几个重要的取整函数以及上下取整函数之间的关系等, 最后给出一些代码实现.

参考了具体数学¹, Wikipedia²以及³.

基本概念

这里的一些定义, 记号等均参考了具体数学.

取整函数

1. 上取整(ceil): $\lceil x\rceil$, 表示大于等于$x$的最小整数;
2. 下取整(floor): $\lfloor x\rfloor$, 表示小于等于$x$的最大整数;
3. 取整(等价于下取整): $[x]$, 同下取整.

数的表示

设$x\in\mathbb R$, 则

1. $\lfloor x\rfloor$表示$x$的整数部分(integer part)

2. ${x}$表示$x$的分数部分(fractional part), (不与单元素集合混淆的情况下)

3. 关系: \(x=\lfloor x\rfloor+\{x\}\iff\{x\}=x-\lfloor x\rfloor.\)

取余运算

(下取整表示)设$m,n\in\mathbb N^*$, 则 \(n=m\cdot\underbrace{\lfloor n/m \rfloor}_{\mbox{商}}+\underbrace{n\bmod m}_{\mbox{余数}}\tag{1}\) 其中, $n\bmod m\in[0, m)$.

性质

取余运算

范围

由$(1)$, 得 \(n\bmod m=n-m\lfloor n/m \rfloor\) 推广:(设$x,y\in\mathbb R$) \(x\bmod y=x-y\lfloor x/y \rfloor,\ y\ne0.\) 于是: \(\begin{cases} x\bmod y\in [0,y),&y>0\\ x\bmod y\in (y,0],&y<0 \end{cases}\)

另外, 定义 \(x\bmod 0=x.\tag{2}\)

类似, 定义一个新的运算$\rm mumble$, 用上取整表示数: \(x=y\cdot \lceil x/y\rceil-x\ \rm{mumble}\ y, \ y\ne0.\)

分配律

$\forall c,x,y\in \mathbb R$, \(c(x\bmod y)=(cx)\bmod(cy).\)

证明:

$\forall cy\ne0$, \(\begin{aligned} c(x\bmod y) &=c(x-y\lfloor x/y\rfloor)\\ &=cx-cy\lfloor cx/cy\rfloor\\ &=(cx)\bmod(cy). \end{aligned}\) 当$y=0$时, 根据定义$(2)$, 分配律依然成立.

数的表示

用取余重写数的表示(整数部分, 分数部分) \(x=\lfloor x\rfloor+x\bmod 1.\)

关系

幂等性

\[\begin{align} \Big\lfloor \lfloor x \rfloor \Big\rfloor &= \lfloor x \rfloor, \\ \Big\lceil \lceil x \rceil \Big\rceil &= \lceil x \rceil, \\ \Big\{ \{ x \} \Big\} &= \{ x \}. \end{align}\]

并有:(只关注内层作用) \(\begin{align} \Big\lfloor \lceil x \rceil \Big\rfloor &= \lceil x \rceil, \\ \Big\lceil \lfloor x \rfloor \Big\rceil &= \lfloor x \rfloor, \end{align}\)

互反律

\[\begin{aligned} \lfloor x \rfloor +\lceil -x \rceil &= 0, \\ -\lfloor x \rfloor &= \lceil -x \rceil, \\ -\lceil x \rceil &= \lfloor -x \rfloor. \end{aligned}\]

并且: \(\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ -1,&\text{ 若 }\ x\not\in \mathbb{Z}, \end{cases} \\[5pt] \lceil x \rceil + \lceil -x \rceil = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}\) 针对小数部分(${x } = x - \lfloor x \rfloor$): \(\{ x \} + \{ -x \} = \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}\)

与整数的关系

1. $\lceil x\rceil\geqslant x$; $\lfloor x\rfloor\leqslant x$; $\lfloor x \rfloor \leqslant \lceil x \rceil$.

2. $\lfloor x\rfloor=x\iff x\in \mathbb Z\iff \lceil x\rceil=x$;

3. If $x\notin \mathbb Z$, then $\lceil x\rceil-\lfloor x\rfloor=[x\ \mbox{not an integer}]=1$. 另一种表述: \(\lceil x \rceil - \lfloor x \rfloor = [x\mbox{是否为整数}]= \begin{cases} 0,&\text{ 若 }\ x\in \mathbb{Z},\\ 1,&\text{ 若 }\ x\not\in \mathbb{Z}. \end{cases}\)

4. $x-1<\lfloor x\rfloor$, $x+1>\lceil x\rceil$, so we have: \(x-1<\lfloor x\rfloor\leqslant x\leqslant \lceil x\rceil<x+1.\)

---

设$n\in\mathbb Z,\ x\in \mathbb R$, 则有: \(\begin{cases} \lfloor x\rfloor=n\iff n\leqslant x<n+1\\ \lfloor x\rfloor=n\iff x-1<n\leqslant x\\[10pt] \lceil x\rceil=n\iff n-1<x\leqslant n\\ \lceil x\rceil=n\iff x\leqslant n<x+1\\ \end{cases}\) 并有, 整数项移出取整号: \(\begin{cases} \lfloor x+n\rfloor=\lfloor x\rfloor+n,\\ \tag{*} \lceil x+n\rceil=\lceil x\rceil+n, \end{cases}\) 不等式的转换: \(\begin{cases} \lfloor x\rfloor<n \iff x<n\\ \lfloor x\rfloor\geqslant n\iff x\geqslant n \\[10pt] \lceil x\rceil>n\iff x> n\\ \lceil x\rceil\leqslant n\iff x\leqslant n\\ \end{cases}\)

与函数的关系

设$f(x)$是任意一个具有如下性质且在一个实数区间内连续的单调递增函数, 即: \(f(x)=\mbox{integer}\Longrightarrow x=\mbox{integer}.\) 则有(若函数$f(x),f(\lfloor x\rfloor),f(\lceil x\rceil)$有定义) \(\lfloor f(x)\rfloor=\lfloor f(\lfloor x\rfloor)\rfloor,\quad \lceil f(x)\rceil=\lceil f(\lceil x\rceil)\rceil.\)

证明:(反证)

• 当$x=\lceil x\rceil$, 显然成立.

• 当$x<\lceil x\rceil$时, 根据函数$f(x)$单调性得到: \(f(x)<f(\lceil x\rceil),\) 根据上取整函数非降性质, 又可得到: \(\lceil f(x)\rceil\leqslant \lceil f(\lceil x\rceil)\rceil,\)

  • 若$\lceil f(x)\rceil< \lceil f(\lceil x\rceil)\rceil$, 由$f$连续性, 必定存在数$y$, 使得$x\leqslant y<\lceil x\rceil$, 以及$f(y)=\lceil f(x)\rceil$. 由于$f$定义, $y\in\mathbb Z$, 但是不存在介于$\lfloor x\rfloor$和$\lceil x\rceil$之间的整数, 矛盾, 由此得证.

由此得到一个特例:

$\forall m\in \mathbb Z$, $n\in\mathbb N^*$, 有 \(\left\lceil \frac {x+m}n\right\rceil=\left\lceil \frac {\lceil x\rceil+m}n\right\rceil,\ \left\lfloor \frac {x+m}n\right\rfloor=\left\lfloor \frac {\lfloor x\rfloor+m}n\right\rfloor.\tag{**}\)

恒等式

每组近似分配(埃尔米特恒等式的特例)

将$n$个物品分成$m$组, 按照非增次序排列且尽可能相等的部分的划分: \(n=\left\lceil \frac nm\right\rceil+\left\lceil \frac {n-1}m\right\rceil+\cdots+\left\lceil \frac {n-m+1}m\right\rceil.\tag{3}\)

证明: (构造)

设$n=qm+r$, 其中$q=\lfloor n/m\rfloor$, $r=n\bmod m, 0\leqslant r<m$, 则:

• 当$r=0$, 此时将$q=\lfloor n/m\rfloor$件物品放入第一组, 并且用$n’=n-q$替换$n$, 让$n’=qm’$件物品放入剩下的$m’=m-1$组中, 重复这个操作直到物品都被分组.

• 当$r>0$, 将$\lceil n/m\rceil=\lfloor n/m\rfloor+1= q+1$件物品放进第一组, 用$n’=n-q-1$替换$n$,

  \[n'=n-q-1=qm+r-q-1=q(\underbrace{m-1}_{m'})+\underbrace{r-1}_{r'}\]

  即$n’=qm’+r-1$件物品留给后面的分组. 此时新的余数为$r’=r-1$, 但$q$保持不变. 当余数$r$减到$0$时, 此时情况同上, 所以有 \(n件商品:\begin{cases} \qquad r个组:q+1件物品\\ m-r个组:q件物品 \end{cases}\)

那么在第$k$组($1\leqslant k\leqslant m$)中有多少物品?

应该是: \(\left\lceil \frac {n-k+1}m\right\rceil\)

证明:

将$n=qm+r$代入上式, 得到: \(\left\lceil \frac {n-k+1}m\right\rceil=\left\lceil \frac {qm+r-k+1}m\right\rceil\stackrel{(*)}{=}q+\left\lceil \frac {r-k+1}m\right\rceil\) 应用边界条件: $1\leqslant k\leqslant m,\ 0\leqslant r<m$, 得到 \(\left\lceil \frac {r-k+1}m\right\rceil=[k\leqslant r]\) 上面的$[k\leqslant r]$表示当满足$k\leqslant r$时, 取$1$, 否则取$0$, 这正好满足我们上面给出的构造分组的方法.

将其写成累加形式, 则有: \(\begin{aligned} n&=\left\lceil \frac nm\right\rceil+\left\lceil \frac {n-1}m\right\rceil+\cdots+\left\lceil \frac {n-m+1}m\right\rceil\\ &=\sum_{i=0}^{m-1}\left\lceil \frac {n-i}m\right\rceil=qm+\sum_{i=0}^{m-1}\left\lceil \frac {r-i}m\right\rceil\\ &=qm+\sum_{i=0}^{r-1}\left\lceil \frac {r-i}m\right\rceil=qm+r\\ \end{aligned}\)

同理, 根据各个部分按照非减的次序排列, 小的组放在前面, ($\lfloor n/m\rfloor$在第一组)就得到: \(n=\left\lfloor \frac nm\right\rfloor+\left\lfloor \frac {n+1}m\right\rfloor+\cdots+\left\lfloor \frac {n+m-1}m\right\rfloor.\tag{3'}\) 针对上面得到的结论, 还可以进行推广:

利用$\lfloor mx\rfloor$替换$(3’)$式中的$n$, 并用$(**)$式去掉下取整函数中的下取整函数可以得到: \(\lfloor mx\rfloor=\left\lfloor x\right\rfloor+\left\lfloor x+\frac 1m\right\rfloor+\cdots+\left\lfloor x+\frac{m-1}m\right\rfloor.\) 上式就是埃尔米特恒等式. $$

$$

$\bigstar$上下取整转换

下面介绍前言部分提到的一个重要的关系, 利用这个式子可以方便的转换上取整和下取整, 因为计算机编程语言中常用下取整. \(\left\lceil \frac{n}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1.\tag{***}\) 以及: \(\left\lfloor \frac{n}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil = \left\lceil \frac{n + 1}{m} \right\rceil - 1.\)

证明:(方法1)

直接由埃尔米特恒等式的特例$(3)$的第一项等于$(3’)$式的第二项, 即为本结论, 需要从组合意义角度出发. (分组方法)

证明:(方法2)

对$(!!*)$两端同时减去$\left\lfloor \dfrac nm\right\rfloor$, 得到:

• 左边:(利用与整数的关系之3) \(\left\lceil \frac{n}{m} \right\rceil-\left\lfloor \dfrac nm\right\rfloor=\left\lceil\frac{n\bmod m}{m}\right\rceil=\begin{cases} 0,&\text{ 若 }n\bmod m=0,\\ 1,&\text{ 若 }n\bmod m>0. \end{cases}\)

• 右边: 可设$n=mq+r$, 并有$q=\lfloor n/m \rfloor,0\leqslant r=n\bmod m<m$, 则 \(\begin{aligned} \left\lfloor \frac{n+m-1}{m} \right\rfloor-\left\lfloor \frac nm\right\rfloor &=\left\lfloor \frac{mq+m+r-1}{m} \right\rfloor-\left\lfloor \frac {mq+r}m\right\rfloor\\ &=\left\lfloor \frac{r+m-1}{m} \right\rfloor-\left\lfloor \frac {r}m\right\rfloor\\ &=\left\lfloor \frac{r+m-1}{m} \right\rfloor\\ &=\left\lfloor \frac{n\bmod m+m-1}{m} \right\rfloor\\ &=\begin{cases} 0,&\text{ 若 }n\bmod m=0,\\ 1,&\text{ 若 }n\bmod m>0. \end{cases} \end{aligned}\)

即得结论.

当然, 还有通过广义Ramsey定理证明的方法(鸽巢原理的推广), 可以参见³.

总的来看, 这个结论通过上面的近似分组问题就可以解释了.

ref