(huge 3) 整值函数
3.1 底和顶
定义
-
(lfloor x floor =)小于或等于 (x) 的最大整数，(lceil x ceil =)大于或等于 (x) 的最小整数
-
(x=lfloor x floor +{x})，称 (lfloor x floor) 为 (x) 的整数部分，({x}) 为 (x) 的分数部分。
性质
-
[x-1<lfloor x floorle xle lceil x ceil<x+1 ]
-
[lfloor x floor=xLeftrightarrow x是整数 Leftrightarrow lceil x ceil =x ]
-
[lceil x ceil -lfloor x floor =[x ext{不是整数}] ]
-
[lfloor -x floor=-lceil x ceil;-lceil -x ceil=-lfloor x floor ]
-
[egin{cases} lfloor x floor=n Leftrightarrow nle x<n+1, & (a)\ lfloor x floor=n Leftrightarrow x-1< nle x, & (b)\ lceil x ceil=n Leftrightarrow n-1< xle n, & (c)\ lceil x ceil=n Leftrightarrow xle n<x+1. & (d)\ end{cases} ]
-
[lfloor x+n floor =lfloor x floor +n ]
-
[egin{cases} x<nLeftrightarrow lfloor x floor <n , & (a)\ n<xLeftrightarrow n<lceil x ceil , & (b)\ xle nLeftrightarrow lfloor x floor le n , & (c)\ nle xLeftrightarrow nle lceil x ceil , & (d)\ end{cases} ]
-
[lfloor x+y floor = lfloor x floor +lfloor y floor 或 lfloor x floor +lfloor y floor+1 ]
3.2 底和顶的应用
-
(f(x)) 是在实数区间上连续的单调递增函数，满足 (f(x)=)整数(Rightarrow x=)整数，
[lfloor f(x) floor=lfloor f(lfloor x floor) floor ;lceil f(x) ceil=lceil f(lceil x ceil ) ceil ]特例：
[lfloor frac {x+m} n floor =lfloor frac {lfloor x floor +m} n floor;lceil frac {x+m} n ceil =lceil frac {lceil x ceil +m} n ceil ]应用：(lfloor x/1000 floor=lfloor lfloor lfloor x/10 floor/10 floor/10 floor)
-
[a le n<bLeftrightarrow lceil a ceil le n<lceil b ceil\ a < nle bLeftrightarrow lfloor a floor < nle lfloor b floor ]
-
谱 ：实数 $alpha $ 的谱是整数组成的一个无限多重集合（元素可重复）：
[Spec(alpha)={lfloor alpha floor,lfloor 2alpha floor,lfloor 3alpha floor,...} ]-
没有两个谱是相等的。即 (alpha eq eta Leftrightarrow Spec(alpha) eq Spec(eta))
-
(Spec(sqrt 2)) 和 (Spec(2+sqrt 2)) 的并集是 (N^{+})
-
3.3 底与顶的递归式
应用于一些类似于 (f(n)=f(lfloor frac n2 floor)+f(lceil frac n 2 ceil)) 的递归式
-
trick: (n=lfloor frac n2 floor+lceil frac n 2 ceil)
-
trick: (g(i)=n-f(i)) 可能发现优美形式
-
[{D_0}^{(q)}=1;\ {D_n}^{(q)}=lceil frac q {q-1}{D_{n-1}}^{(q)} ceil,n>0 ]
约瑟夫问题幸存者 (J_q(n)=qn+1-{D_k}^{q}) (k) 是使得 ({D_k}^{q}>(q-1)n) 的尽可能小的数。
3.4 mod：二元运算
定义
- 基本公式
- 推广：
-
$color {red} warning: $ 计算机语言的定义与这里不同。
[]
5 mod 3=5-3lfloor 5/3
floor & =2
5 mod -3=5-(-3)lfloor 5/(-3)
floor&=-1
-5 mod 3=-5-3lfloor -5/3
floor&=1
-5 mod -3=-5-(-3)lfloor -5/(-3)
floor&=-2
end {cases}
$$
-
(mod) 后的数称为模。
[]
0ge xmod y>y, y<0
$$
-
定义 (xmod 0=x)
-
(x mod 1={x})
-
[x mumble y=ylceil x/y ceil-x,y eq0 ]
性质
-
分配律： (c(xmod y)=(cx) mod (cy))
-
(n) 为整数时，
[n=lceil frac n m ceil+lceil frac {n-1} m ceil+...+lceil frac {n-m+1} m ceil\ n=lfloor frac n m floor+lfloor frac {n+1} m floor+...+lfloor frac {n+m-1} m floor ](x) 为实数时，
[lfloor mx floor =lfloor x floor+lfloor x+frac 1 m floor+...+lfloor x+frac {m-1} m floor ]
3.5 底和顶的和式
-
对所有无理数 $alpha $ 以及所有几乎处处连续的有界函数 (f) 有
[lim_{n ightarrow infty} {{frac 1 n} sum_{0le k <n} f({kalpha }) }=int _0^1 f(x) dx ] -
[sum_{0le k<m} lfloor frac {nk+x} m floor=dlfloorfrac x d floor+frac {(m-1)(n-1)} 2+frac {d-1} 2\ sum_{0le k<m} lfloor frac {nk+x} m floor=sum_{0le k<m} lfloor frac {mk+x} n floor ]
习题
热身题
1
(m=lfloor lg n floor,l=n-2^{lfloor lg n floor})
2
(a) (lfloor x+0.5 floor)
(b) (lceil x-0.5 ceil)
3
(m,nin N^+),(alpha) 是大于 (n) 的无理数时，计算 (lfloor lfloor malpha floor n/alpha floor)
4
水平0：给定一个显式对象 (x) 和一个显式对象 (P(x)) 猜测 (P(x)) 是否为真。
5
当 (n) 是正整数时，求使得(lfloor nx floor=nlfloor x floor) 成立的充分必要条件。
({x}<1/n) 是 (lfloor nx floor=nlfloor x floor) 的必要条件。
下证 是 ({x}<1/n) 是 (lfloor nx floor=nlfloor x floor) 的充分条件。
*严谨的答案做法：
$lfloor nx floor=lfloor nlfloor x floor+n{x} floor=nlfloor x floor+lfloor n{x} floor $
(lfloor n{x} floor =0)
(0le lfloor n{x} floor<1)
({x}<1/n)
下证 是 ({x}<1/n) 是 (lfloor nx floor=nlfloor x floor) 的充分条件。
(0lelfloor n{x} floor<1)
(lfloor n{x} floor =0)
(nlfloor x floor+lfloor n{x} floor =nlfloor x floor)
$lfloor nx floor=nlfloor x floor $
6
(f(x)) 是仅当 (x) 为整数时才取整数值的连续单调递减函数时，关于 (f(x)) 有什么可谈的吗？
不妨 (f(x)=-x)
(lfloor f(x) floor = lfloor -x floor =-lceil x ceil)
(f(lfloor x floor)=-lfloor x floor=lceil -x ceil)
(lceil f(x) ceil = lceil -x ceil =-lfloor x floor)
(f(lceil x ceil ) = -lceil x ceil =lceil -x ceil)
猜测 $ lceil f(x) ceil=lceil f(lfloor x floor) ceil$
证：
(xle lceil x ceil)
(f(x)ge f(lceil x ceil))
(lfloor f(x) floorge lfloor f(lceil x ceil ) floor)
若 (lfloor f(x) floor> lfloor f(lceil x ceil ) floor)
那么一定存在
(xle y<lceil x ceil) 且$f(y)=lfloor f(x ) floor $
(y) 为整数。
但不可能有整数严格位于 $lfloor x floor $ 和 $lceil x ceil $ 之间，因此 (lfloor f(x) floor=lfloor f(lceil x ceil ) floor)
同理可证另一条。
7
解递归式
0,1,2,3,...,m-1,
0,1,2,3,...,m-1,
m,m+1,...,2m-1
1, 2, ...,m,
2m,2m+1,...,3m-1
2, 3, ...,m+1
(X_n=nmod m+lfloor frac n m floor (nge m))
随便瞎几把乱证就好了懒得写。
8
证明狄利克雷抽屉原理：如果 (n) 个物体放进 (m) 个盒子中，那么某个盒子中必定含有 (ge lceil n/m ceil) 个物体，且有某个盒子中必定含有 (le lfloor n/m floor) 物品。
(1)
如果所有盒子都有 (< lceil n/m ceil) 个物体。
都有 $le lceil n/m ceil-1 $ 个物体。
希望能符合要求
(n le m(lceil n/m ceil-1))
(n/m +1le lceil n/m ceil)
恒不成立
(2)
如果所有盒子都有 (> lfloor n/m floor) 个物体。
都有 (ge lfloor n/m floor +1) 个
(n/m>lfloor n/m floor +1)
$n/m-1>lfloor n/m floor $
恒不成立。
9
证明，总可以用一种系统化的方法来这样做：
如果 (0<m/n<1) ，那么
（斐波那契算法）
令 (n=m(q-1)+r)
(r=0) 时，结束算法。
(r>0) 时，
(m) 每次至少减少 (1) ，直到 (m=0)
基础题
10
证明，表达式
总是等于 $lfloor x floor $ 或 (lceil x ceil)
每种情况在何时会出现？
(lceil frac {2x+1} 2 ceil=lceil x+frac 1 2 ceil)
(-lceil frac {2x+1} 4 ceil=-lceil frac x 2 +frac 1 4 ceil=lfloor -frac x 2-frac 1 4 floor),(lfloor frac {2x+1} 4 floor=lfloor frac x 2+frac 1 4 floor)
(lfloor frac x 2+frac 1 4 floor-lceil frac x 2 +frac 1 4 ceil=-[frac x 2 +frac 1 4不是整数])
-
(frac x 2+frac 1 4) 是整数
(frac {2x+1} 4) 是整数 (2x mod 4 =3)
(x) 无解
-
(frac x 2+frac 1 4) 不是整数
(lceil frac {2x+1} 2 ceil=lceil x+frac 1 2 ceil)
({x}lefrac 1 2) 时，原式 (=lceil x+frac 1 2 ceil-1=lfloor x floor +1-1=lfloor x floor)
({x}>frac 1 2) 时，原式 (=lceil x+frac 1 2 ceil-1=lceil x ceil +1-1=lceil x ceil)
11
当 (alpha=eta) 时，开区间包含 0 个整数。
(alpha=eta) 且 ({alpha}=0) 时，公式计算结果为 (-1) ，显然不会包含 (-1) 个整数。
12
证明：对于所有整数 (n) 和所有正整数 (m) 有
（这个恒等式给出了一种顶与底相互转化的方法）
证：
令 (q=lceilfrac n m ceil,n=m(q-1)+r) 则 (rin [1,m])
(lceil frac {n-1} m ceil+1=q-1+1=q=lfloor frac n m floor)
13
设 (alpha,eta) 时正实数，证明： (Spec(alpha)) 和 (Spec(eta)) 给出了正整数的划分，当且仅当 (alpha) 和 (eta) 是无理数且 (1/alpha +1/eta=1).
无理数：显然 否则 (eta alpha=alpha eta) 会重复
(1/alpha +1/eta=1) 时满足要求，见之前书中证明。
讨论
在 (1/alpha +1/eta eq1) 时是否满足要求。
即
在 (1/alpha +1/eta eq1) 时是否满足要求。
((n+1)(1/alpha +1/eta)-{frac {n+1} alpha }-{frac {n+1} eta }=n)
不知道了。。
14
证明或推翻 ((x mod ny) mod y=xmod y, n) 为整数。
正确，
n=0时显然。
否则，
令 (x=ty+r),(t=lfloor x/y floor),(t=pn+q),(p=lfloor frac t n floor)
(xmod y=r=x-t y)
(xmod ny=x-kny)
(k=lfloor frac x {ny} floor=lfloor frac {lfloor frac x {y} floor} n floor=lfloorfrac t n floor)
(xmod ny=x-kny=x-pny)
((x-pny)mod y=(qy+r)mod y=r)
证毕
15
存在与
类似的用顶替换底的恒等式吗？
令 (x=frac n m)
16
证明 (nmod 2=(1-(-1)^n)/2). 对 (n mod 3) 求出并证明类似的形如 (a+bomega^n+comega^{2n}) 的表达式，其中 (omega=(-1+isqrt 3)/2)
提示：(omega ^3=1) 且 (1+omega+omega^2=0)
17
在 (xge 0) 的情形下，通过用 (sum_j [1le jle x+k/m]) 替换 (lfloor x+k/m floor) 并首先对 (k) 求和，来计算和式 (sum_{0le k<m} lfloor x+k/m floor)
你的答案与 (lfloor mx floor =lfloor x floor+lfloor x+frac 1 m floor+...+lfloor x+frac {m-1} m floor) 吻合吗？
18
被我吃了