《具体数学》部分习题解答3

2023-12-06 17:23:04

习题三

- - 3.1
  - 3.2
  - 3.3
  - 3.5
  - 3.6
  - 3.7
  - 3.8
  - 3.10
  - 3.11
  - 3.12
  - 3.14
  - 3.15
  - 3.16
  - 3.17
  - 3.19
  - 3.20
  - 3.21
  - 3.22
  - 3.23
  - 3.25
  - 3.26
  - 3.30
  - 3.31
  - 3.34
  - 3.35
  - 3.45

3.1

在第一章分析约瑟夫问题时，将任意的一个正整数 n n n 表示成了 n = 2 m + l n=2^m+l n=2m+l 的形式，其中 0 ≤ l < 2 m 0 \le l < 2^m 0≤l<2m 。请利用底括号或顶括号，给出将 l l l 和 m m m 表示成为 n n n 的函数的显式公式

3.2

与一个给定实数 x x x 距离最近的整数的公式是什么？在对等情况下， x x x 恰好在两个整数的中间位置，请给出一个表达式，它（ a a a ）往上舍入成整数，即成为 ⌈ x ⌉ \lceil x \rceil ⌈x⌉ ;（ b b b ）向下舍入成整数，即成为 ⌊ x ⌋ \lfloor x \rfloor ⌊x⌋ 。

不失一般性，假设 x x x 位于 n n n 和 n + 1 n+1 n+1 之间。
a a a 种情况下，仅当 x ∈ [ n , n + 0.5 ) x \in [n,n+0.5) x∈[n,n+0.5) 时，答案是 n n n ，否则为 n + 1 n+1 n+1 ，因此将 x x x 加上0.5再向下取整。
b b b 种情况下，仅当 x ∈ [ n , n + 0.5 ] x \in [n,n+0.5] x∈[n,n+0.5] 时，答案是 n n n ，否则为 n + 1 n+1 n+1 ，因此将 x x x 减去0.5再向上取整。
a . ⌊ x + 0.5 ⌋ b . ⌈ x − 0.5 ⌉ a. \lfloor x + 0.5 \rfloor \\ b. \lceil x - 0.5 \rceil a.⌊x+0.5⌋b.⌈x−0.5⌉

3.3

当 m m m 和 n n n 是正整数，且 α \alpha α 是大于 n n n 的无理数时，计算 ⌊ ⌊ m α ⌋ n / α ⌋ \lfloor \lfloor m \alpha \rfloor n / \alpha \rfloor ⌊⌊mα⌋n/α⌋

3.5

当 n n n 是正整数时，求使得 ⌊ n x ⌋ = n ⌊ x ⌋ \lfloor n x \rfloor = n \lfloor x \rfloor ⌊nx⌋=n⌊x⌋ 成立的必要充分条件。（你的条件应该包含 { x } \{x\} {x} ）

3.6

当 f ( x ) f(x) f(x) 是仅当 x x x 为整数时才取整数值的连续单调递减函数时，关于 ⌊ f ( x ) ⌋ \lfloor f(x) \rfloor ⌊f(x)⌋ 有什么可谈的吗？

3.7

解递归式
X n = n , 0 ≤ n < m X n = X n − m + 1 , n ≥ m X_n = n \ , \quad 0 \le n < m \\ X_n = X_{n-m}+1 \ , \quad n \ge m Xn=n ,0≤n<mXn=Xn−m+1 ,n≥m

不妨列出部分 X n X_n Xn 的值：

n	0	1	2	3	… \dots …	m-1	m	m+1	… \dots …	2m	2m+1	… \dots …
X n X_n Xn	0	1	2	3	… \dots …	m-1	1	2	… \dots …	2	3	… \dots …

由此可以发现 X n X_n Xn 的规律并写出表达式： X n = n m o d m + ⌊ n m ⌋ X_n = n\ mod\ m + \lfloor \frac{n}{m} \rfloor Xn=n mod m+⌊mn⌋

3.8

证明狄利克雷抽屉原理：如果 n n n 个物体放进 m m m 个盒子中，那么某个盒子中必定含有 ≥ ⌈ n / m ⌉ \ge \lceil n/m \rceil ≥⌈n/m⌉ 个物体，且有某个盒子中必定含有 ≤ ⌊ n / m ⌋ \le \lfloor n/m \rfloor ≤⌊n/m⌋ 个物体。

反证法：假设所有盒子中含有 < ⌈ n m ⌉ < \lceil \frac{n}{m} \rceil <⌈mn⌉ 个物体，也即含有 ≤ ( ⌈ n m ⌉ − 1 ) \le ( \lceil \frac{n}{m} \rceil -1) ≤(⌈mn⌉−1) 个物体，因此，总共 m m m 个盒子一共含有 ≤ m ( ⌈ n m ⌉ − 1 ) \le m (\lceil \frac{n}{m} \rceil -1) ≤m(⌈mn⌉−1) 个物体，有： n m + 1 ≤ ⌈ n m ⌉ \frac{n}{m} + 1 \le \lceil \frac{n}{m} \rceil mn+1≤⌈mn⌉ ，矛盾，假设不成立，即证某个盒子中必定含有 ≥ ⌈ n / m ⌉ \ge \lceil n/m \rceil ≥⌈n/m⌉ 个物体。
同理可证某个盒子中必定含有 ≤ ⌊ n / m ⌋ \le \lfloor n/m \rfloor ≤⌊n/m⌋ 个物体。

3.10

证明，表达式
⌈ 2 x + 1 2 ⌉ − ⌈ 2 x + 1 4 ⌉ + ⌊ 2 x + 1 4 ⌋ \lceil \frac{2x+1}{2} \rceil - \lceil \frac{2x+1}{4} \rceil + \lfloor \frac{2x+1}{4} \rfloor ⌈22x+1⌉−⌈42x+1⌉+⌊42x+1⌋
总是等于 ⌊ x ⌋ \lfloor x \rfloor ⌊x⌋ 或者 ⌈ x ⌉ \lceil x \rceil ⌈x⌉ ，每一种情形在何时会出现？

3.11

给出正文中提及的证明细节：当 α < β \alpha < \beta α<β 时，开区间 ( α , β ) (\alpha , \beta) (α,β) 恰好包含 ⌈ β ⌉ − ⌊ α ⌋ − 1 \lceil \beta \rceil - \lfloor \alpha \rfloor -1 ⌈β⌉−⌊α⌋−1 个整数。为使证明正确，为什么 α = β \alpha = \beta α=β 的情形必须排除在外？

3.12

证明，对所有整数 n n n 和所有正整数 m m m 有
⌈ n m ⌉ = ⌊ n + m − 1 m ⌋ \lceil \frac{n}{m} \rceil = \lfloor \frac{n+m-1}{m} \rfloor ⌈mn⌉=⌊mn+m−1⌋
（这个恒等式给出了另一种将顶与底相互转化的方法，它用不到反射律）

3.14

证明或推翻： ( x m o d n y ) m o d y = x m o d y , n 为整数 (x \ mod \ ny) \ mod \ y =x \ mod \ y \ , \quad n为整数 (x mod ny) mod y=x mod y ,n为整数

3.15

存在与
⌊ m x ⌋ = ⌊ x ⌋ + ⌊ x + 1 m ⌋ + ⋯ + ⌊ x + m − 1 m ⌋ \lfloor mx \rfloor = \lfloor x \rfloor + \lfloor x + \frac{1}{m} \rfloor + \dots + \lfloor x + \frac{m-1}{m} \rfloor ⌊mx⌋=⌊x⌋+⌊x+m1⌋+⋯+⌊x+mm−1⌋
类似的用顶替代底的恒等式吗？

已知： n = ⌈ n m ⌉ + ⌈ n − 1 m ⌉ + ⋯ + ⌈ n − m + 1 m ⌉ 用 ⌈ m x ⌉ 替换 n ，得到： ⌈ m x ⌉ = ⌈ x ⌉ + ⌈ x − 1 m ⌉ + ⋯ + ⌈ x − m − 1 m ⌉ 已知：n = \lceil \frac{n}{m} \rceil + \lceil \frac{n-1}{m} \rceil + \dots + \lceil \frac{n-m+1}{m} \rceil \\ 用 \lceil mx \rceil 替换 n ，得到：\\ \lceil mx \rceil = \lceil x \rceil + \lceil x - \frac{1}{m} \rceil + \dots + \lceil x - \frac{m-1}{m} \rceil 已知：n=⌈mn⌉+⌈mn−1⌉+⋯+⌈mn−m+1⌉用⌈mx⌉替换n，得到：⌈mx⌉=⌈x⌉+⌈x−m1⌉+⋯+⌈x−mm−1⌉

3.16

证明 n m o d 2 = ( 1 − ( − 1 ) n ) / 2. n \ mod \ 2 = (1 - (-1)^n )/2. n mod 2=(1−(−1)n)/2. 对 n m o d 3 n \ mod \ 3 n mod 3 求出并证明类似的形如 a + b ω n + c ω 2 n a + b \omega^n + c \omega^{2n} a+bωn+cω2n 的表达式，其中 ω \omega ω 是复数 ( − 1 + i 3 ) / 2 (-1 + i \sqrt{3} ) / 2 (−1+i3 )/2 。提示： ω 3 = 1 \omega^3 = 1 ω3=1 且 1 + ω + ω 2 = 0 1 + \omega + \omega^2 = 0 1+ω+ω2=0

n 无非是两种情况： n = 2 k 或 n = 2 k + 1 , 其中 k ∈ Z 如果 n = 2 k ，则 n m o d 2 = 1 − ( − 1 ) 2 k 2 = 0 如果 n = 2 k + 1 ，则 n m o d 2 = 1 − ( − 1 ) 2 k + 1 2 = 1 无论哪种情况等式均成立。 n 无非是两种情况：n = 2k 或 n = 2k+1 , 其中 k \in \mathbb{Z} \\ 如果 n = 2k ，则 n \ mod \ 2 = \frac{1-(-1)^{2k}}{2} = 0 \\ 如果 n = 2k+1 ，则 n \ mod \ 2 = \frac{1-(-1)^{2k+1}}{2} = 1 \\ 无论哪种情况等式均成立。 n无非是两种情况：n=2k或n=2k+1,其中k∈Z如果n=2k，则n mod 2=21−(−1)2k=0如果n=2k+1，则n mod 2=21−(−1)2k+1=1无论哪种情况等式均成立。
同理：

3.17

在 x ≥ 0 x \ge 0 x≥0 的情况下，通过用 ∑ j [ 1 ≤ j ≤ x + k / m ] \sum_{j} [1 \le j \le x + k/m] ∑j[1≤j≤x+k/m] 替换 ⌊ x + k / m ⌋ \lfloor x + k/m \rfloor ⌊x+k/m⌋ 并首先对 k k k 求和，来计算和式 ∑ 0 ≤ k < m ⌊ x + k / m ⌋ \sum_{0 \le k < m} \lfloor x + k/m \rfloor ∑0≤k<m⌊x+k/m⌋ 。你的答案与 ⌊ m x ⌋ = ⌊ x ⌋ + ⌊ x + 1 m ⌋ + ⋯ + ⌊ x + m − 1 m ⌋ \lfloor mx \rfloor = \lfloor x \rfloor + \lfloor x + \frac{1}{m} \rfloor + \dots + \lfloor x + \frac{m-1}{m} \rfloor ⌊mx⌋=⌊x⌋+⌊x+m1⌋+⋯+⌊x+mm−1⌋吻合吗？

3.19

求出关于实数 b > 1 b > 1 b>1 的一个必要充分条件，使得
⌊ log ⁡ b x ⌋ = ⌊ log ⁡ b ⌊ x ⌋ ⌋ \lfloor \log_b{x} \rfloor = \lfloor \log_b{\lfloor x \rfloor} \rfloor ⌊logbx⌋=⌊logb⌊x⌋⌋
对所有实数 x ≥ 1 x \ge 1 x≥1 都成立

3.20

当 x > 0 x>0 x>0 时，求闭区间 [ α … β ] [\alpha \dots \beta] [α…β] 中 x x x 的所有倍数之和

⌈ α x ⌉ 代表闭区间中首个 x 的倍数 ⌊ β x ⌋ 代表闭区间中最后一个 x 的倍数因此有： ∑ k = ⌈ α x ⌉ ⌊ β x ⌋ k x = x 2 ( ( ⌊ β x ⌋ ) 2 + ⌊ β x ⌋ − ( ⌈ α x ⌉ ) 2 + ⌈ α x ⌉ ) \lceil \frac{\alpha}{x} \rceil 代表闭区间中首个 x 的倍数 \\ \lfloor \frac{\beta}{x} \rfloor 代表闭区间中最后一个 x 的倍数 \\ 因此有：\sum_{k=\lceil \frac{\alpha}{x} \rceil}^{\lfloor \frac{\beta}{x} \rfloor} kx = \frac{x}{2} ((\lfloor \frac{\beta}{x} \rfloor)^2 + \lfloor \frac{\beta}{x} \rfloor -(\lceil \frac{\alpha}{x} \rceil)^2 + \lceil \frac{\alpha}{x} \rceil) ⌈xα⌉代表闭区间中首个x的倍数⌊xβ⌋代表闭区间中最后一个x的倍数因此有：k=⌈xα⌉∑⌊xβ⌋kx=2x((⌊xβ⌋)2+⌊xβ⌋−(⌈xα⌉)2+⌈xα⌉)

3.21

对 0 ≤ m ≤ M 0 \le m \le M 0≤m≤M ，有多少个数 2 m 2^m 2m 的十进制表示中，其首位数字为1？

在十进制表示中，如果首位数字为 1 , 对应该数字为 10 的幂而在 [ 1 0 n , 2 ∗ 1 0 n ) 中一共有 ( ⌈ lg ⁡ 2 + n lg ⁡ 10 ⌉ − ⌈ n lg ⁡ 10 ⌉ ) 个 2 的幂，即一个 2 的幂问题即转换为：对于 0 ≤ m ≤ M ， 2 m 中有多少个 10 的幂？因此答案为： ⌊ log ⁡ 2 M ⌋ + 1 在十进制表示中，如果首位数字为1,对应该数字为10的幂 \\ 而在[10^n, 2*10^n)中一共有(\lceil \lg{2} + n \lg{10} \rceil - \lceil n \lg{10} \rceil)个2的幂，即一个2的幂 \\ 问题即转换为：对于0 \le m \le M，2^m中有多少个10的幂？ \\ 因此答案为：\lfloor \log{2^M} \rfloor + 1 在十进制表示中，如果首位数字为1,对应该数字为10的幂而在[10n,2∗10n)中一共有(⌈lg2+nlg10⌉−⌈nlg10⌉)个2的幂，即一个2的幂问题即转换为：对于0≤m≤M，2m中有多少个10的幂？因此答案为：⌊log2M⌋+1

3.22

计算和式 S n = ∑ k ≥ 1 ⌊ n / 2 k + 1 2 ⌋ S_n = \sum_{k \ge 1} \lfloor n/2^k + \frac{1}{2} \rfloor Sn=∑k≥1⌊n/2k+21⌋ 以及 T n = ∑ k ≥ 1 2 k ⌊ n / 2 k + 1 2 ⌋ 2 . T_n = \sum_{k \ge 1} 2^k \lfloor n/2^k + \frac{1}{2} \rfloor^2. Tn=∑k≥12k⌊n/2k+21⌋2.

3.23

证明序列
1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5 , … 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5, \dots 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,…
的第 n n n 个元素是 ⌊ 2 n + 1 2 ⌋ \lfloor \sqrt{2n} + \frac{1}{2} \rfloor ⌊2n +21⌋ （这个序列恰好包含 m m m 个 m m m）

3.25

证明或推翻：对所有非负的 n n n ，由
K 0 = 1 K n + 1 = 1 + m i n ( 2 K ⌊ n / 2 ⌋ , 3 K ⌊ n / 3 ⌋ ) , n ≥ 0 K_0 = 1 \\ K_{n+1} = 1 + min(2K_{\lfloor n/2 \rfloor},3K_{\lfloor n/3 \rfloor}) \ , n \ge 0 K0=1Kn+1=1+min(2K⌊n/2⌋,3K⌊n/3⌋) ,n≥0
所定义的高德纳数满足 K n ≥ n K_n \ge n Kn≥n.

3.26

证明：辅助的约瑟夫数满足：
( q q − 1 ) n ≤ D n ( q ) ≤ q ( q q − 1 ) n , n ≥ 0 (\frac{q}{q-1})^n \le D_n^{(q)} \le q (\frac{q}{q-1})^n \ , \quad n \ge 0 (q−1q)n≤Dn(q)≤q(q−1q)n ,n≥0

辅助的约瑟夫数：
D 0 ( q ) = 1 D n ( q ) = ⌈ q q − 1 D n − 1 ( q ) ⌉ , n > 0 D_0^{(q)} = 1 \\ D_n^{(q)} = \lceil \frac{q}{q-1} D_{n-1}^{(q)} \rceil \ , \quad n > 0 D0(q)=1Dn(q)=⌈q−1qDn−1(q)⌉ ,n>0
在辅助的约瑟夫数中， q q q 应该是正整数.

用数学归纳法证明：
第一个 ≤ \le ≤ 号：
假设 ( q q − 1 ) n − 1 ≤ D n − 1 ( q ) 则： D n ( q ) = ⌈ q q − 1 D n − 1 ( q ) ⌉ ≥ ⌈ ( q q − 1 ) n ⌉ ≥ ( q q − 1 ) n 假设 (\frac{q}{q-1})^{n-1} \le D_{n-1}^{(q)} \\ 则： D_n^{(q)} = \lceil \frac{q}{q-1} D_{n-1}^{(q)} \rceil \ge \lceil (\frac{q}{q-1})^n \rceil \ge (\frac{q}{q-1})^n 假设(q−1q)n−1≤Dn−1(q)则：Dn(q)=⌈q−1qDn−1(q)⌉≥⌈(q−1q)n⌉≥(q−1q)n
第二个 ≤ \le ≤ 号：
假设 D n − 1 ( q ) ≤ q ( q q − 1 ) n − 1 − ( q − 1 ) ≤ q ( q q − 1 ) n − 1 D n ( q ) = ⌈ q q − 1 D n − 1 ( q ) ⌉ ≤ ⌈ q ( q q − 1 ) n − q ⌉ ⇔ D n ( q ) ≤ q ( q q − 1 ) n + 1 − q ≤ q ( q q − 1 ) n 假设 D_{n-1}^{(q)} \le q (\frac{q}{q-1})^{n-1} - (q - 1) \le q (\frac{q}{q-1})^{n-1} \\ D_n^{(q)} = \lceil \frac{q}{q-1} D_{n-1}^{(q)} \rceil \le \lceil q (\frac{q}{q-1})^n - q \rceil \\ \Leftrightarrow D_n^{(q)} \le q(\frac{q}{q-1})^n + 1 - q \le q (\frac{q}{q-1})^n 假设Dn−1(q)≤q(q−1q)n−1−(q−1)≤q(q−1q)n−1Dn(q)=⌈q−1qDn−1(q)⌉≤⌈q(q−1q)n−q⌉⇔Dn(q)≤q(q−1q)n+1−q≤q(q−1q)n

3.30

证明：如果 m m m 是一个大于2的整数，其中 α + α − 1 = m \alpha + \alpha^{-1} = m α+α−1=m 且 α > 1 \alpha > 1 α>1，那么递归式

有解 X n = ⌈ α 2 n ⌉ . X_n = \lceil \alpha^{2^n} \rceil. Xn=⌈α2n⌉. 例如，如果 m = 3 m=3 m=3, 则解为：
X n = ⌈ ϕ 2 n + 1 ⌉ , ϕ = 1 + 5 2 , α = ϕ 2 X_n = \lceil \phi^{2^{n+1}} \rceil \ , \quad \phi = \frac{1+\sqrt{5}}{2} \ , \quad \alpha = \phi^2 Xn=⌈ϕ2n+1⌉ ,ϕ=21+5 ,α=ϕ2

3.31

证明或推翻： ⌊ x ⌋ + ⌊ y ⌋ + ⌊ x + y ⌋ ≤ ⌊ 2 x ⌋ + ⌊ 2 y ⌋ . \lfloor x \rfloor + \lfloor y \rfloor + \lfloor x+y \rfloor \le \lfloor 2x \rfloor + \lfloor 2y \rfloor. ⌊x⌋+⌊y⌋+⌊x+y⌋≤⌊2x⌋+⌊2y⌋.