数学问题杂记

这里放些我见到过的比较有意思的数学题吧。本文会不定期更新。所有问题的标题都是记录到博客上的时间。

这里的题解都是我自己写的，部分参考了标准答案，因此不一定都是完全正确的。如有问题欢迎指出。

2017.6.14

问题描述

给你一个无限长度的空白的尺子，问最少在上面画多少个刻度，使得可以量出 $1$ 到 $10$ 每一个整数长度？
假设一共画了 $n$ 个刻度，每个刻度到最左边的刻度的距离为 $a_1,\; a_2, \;..., \;a_n$，那么称一个长度 $x$ 为可测量的当且仅当存在一对 $i, \;j$，满足 $a_i - a_j = x$。

解决方案

首先我们可以 xjb 试一试，$7$ 个点的方案是非常 naïve 的：

$7$ 个点的方案

通过一番尝试，我们可以构造出 $6$ 个点的方案：

$6$ 个点的方案

当然，因为没有长度限制，所以更长的方案我也构造出来过。总而言之，$6$ 个点的方案不是非常困难。构造上面这个方案时，我先画了一个原点，然后向右走一步，画一个点，继续走两步，画一个点。随后回到原点左边四格的位置画一个点。然后钦定最右边的为 $10$，将 $0$ 刻度画出来。此时发现 $9$ 不存在，所以将 $1$ 也点上。

那么现在问题来了，$5$ 个点的方案能否找出来？

理论上，$5$ 个点两两配对刚好 $10$ 对，给人一种可以构造的感觉。不过很可惜，$5$ 个点的方案是不存在的，这一结论可以使用计算机暴力得出。

下面给出一个不需要任何暴力的证明：

1. 由于 $5$ 个点两两配对一共 $10$ 对，所以所有点对之间的距离刚好是 $1$ 到 $10$，即不存在两个不同的点对之间的距离相同。由此可以推出，最远的两个点之间的距离为 $10$，所以我们可以先钦定刻度 $0$ 和刻度 $10$ 上有两个点。
2. 剩下还有 $3$ 个点，它们将长度为 $10$ 的线段分为 $4$ 段，这四段的长度总和要为 $10$，而 $10$ 的四拆分只有 $10 = 1 + 2 + 3 + 4$，所以这四段的长度构成 $1$ 至 $4$ 的一个排列。
3. 根据第一点，我们知道 $1$ 不能与 $2$ 或 $3$ 相邻，因为那样相邻的两段的长度之和就会与单独的长度为 $3$ 或 $4$ 的一段冲突，因此 $1$ 只能与 $4$ 相邻，并且 $1$ 只能在第一位或者最后一位。这样 $2$ 和 $3$ 必须相邻。又因为 $1+4 = 2+3$，所以我们推出矛盾，故不存在 $5$ 个点的方案。

到此处，我们已经可以回答上面的问题了，最少使用 $6$ 个刻度。

2017.6.14

问题描述

对于 $n$ 个非负实数 $x_1, \;x_2, \;...,\;x_n$，证明：

$x_1x_2\cdots x_n \leqslant \left( \frac{x_1 + x_2 + \cdots x_n}n \right)^n$

即基本不等式。

解决方案

我是在《具体数学》一书的习题上看到的，居然可以用反向归纳法，只能表示我这种菜鸡根本想不出来。

首先 $n = 1$ 时显然，就不再考虑了。

其次，根据初中知识，$(x_1 + x_2)^2 - 4x_1 x_2 = (x_1 - x_2)^2 \geqslant 0$，我们可以得到 $n = 2$ 时的结论。

接下来就比较机智了，首先如果对于 $n$ 成立，那么对于 $2n$ 也成立。我们可以考虑 $2n$ 时的不等式，是这样子的（现在还不成立）：

$x_1x_2\cdots x_{2n} \leqslant \left({x_1 + x_2 + \cdots x_{2n} \over 2n}\right)^{2n}$

既然是要倍增，于是试着分成两组 $y_1,\ y_2,\ ...,\ y_n$ 和 $z_1,\ z_2,\ ...,\ z_n$：

$\begin{aligned} y_i & = x_i \\ z_i & = x_{n + i} \end{aligned}$

令 $Y = y_1 + y_2 + \cdots + y_n$、$Z = z_1 + z_2 + \cdots + z_n$。因为基本不等式对于 $n$ 成立，于是有：

$\begin{aligned} y_1y_2\cdots y_n & \leqslant \left({y_1+y_2+\cdots+y_n\over n}\right)^n = (Y/n)^n \\ z_1z_2\cdots z_n & \leqslant \left({z_1+z_2+\cdots+z_n\over n}\right)^n = (Z/n)^n \end{aligned}$

又因为基本不等式对 $n = 2$ 成立，于是：

$\begin{aligned} x_1x_2\cdots x_{2n} & = y_1y_2\cdots y_nz_1z_2\cdots z_n \\ & \leqslant (Y/n)^n(Z/n)^n \\ & = ((Y/n)(Z/n))^n \\ & \leqslant \left(\left({Y/n + Z/n \over 2}\right)^2\right)^n \\ & = \left({Y+Z\over 2n}\right)^{2n} \\ & = \left({x_1+x_2+\cdots+x_{2n}\over 2n}\right)^{2n} \end{aligned}$

上面第二个不等号用了 $n = 2$ 的基本不等式。至此，我们成功的从 $n$ 推到出了 $2n$。

最后一步就是反向数学归纳法证明。假设现在 $n$ 是成立的，那么需要证明 $n - 1$ 也是成立的。这个证明非常简单，只需要令 $x_n$ 为 $E = \left(\sum_{k=1}^{n-1}x_k\right) / (n - 1)$，就可以发现：

$\begin{aligned} x_1x_2\cdots x_{n-1}E &\leqslant \left( {x_1 + x_2 + \cdots + x_{n - 1} + E \over n} \right)^n \\ x_1x_2\cdots x_{n-1}E &\leqslant \left( {(n - 1)E + E \over n} \right)^n \\ x_1x_2\cdots x_{n-1}E &\leqslant E^n \\ x_1x_2\cdots x_{n-1} &\leqslant E^{n-1} \\ x_1x_2\cdots x_{n-1} &\leqslant \left( {x_1 + x_2 + \cdots + x_{n - 1} \over n - 1} \right)^{n - 1} \end{aligned}$

因此对于 $n - 1$ 也是成立的。

最后综合一下，如果要想证明 $n > 2$ 成立，只需要从 $m = 2$ 开始，倍增 $m$ 直到 $m \geqslant n$，然后反向归纳到 $n$ 即可。因此基本不等式对于所有正整数 $n$ 均成立。

2017.12.16

问题描述

（哥德巴赫-欧拉定理）

(1) （《具体数学》第二章习题 31）证明：

$\sum_{j=2}^\infty\sum_{k=2}^\infty \frac1{j^k} = 1$

(2) （《具体数学》第二章习题 35）设集合 $P = \{m^n \mid m,\;n \geqslant 2,\;m,\;n\in \mathbf{N}\}$，因此我们知道：

$P = \{4,\;8,\;9,\;16,\;25,\;27,\;32,\;36,\;...\}$

证明：

$\sum_{k \in P} {1 \over k - 1} = 1$

解决方案

(1) 第一问使用几何级数即可：

$\begin{aligned} \sum_{j=2}^\infty\sum_{k=2}^\infty {1\over j^k} & = \sum_{j=2}^\infty \left({1 \over 1 - \frac1j} - 1 - \frac1j\right) \\ & = \sum_{j=2}^\infty \left(\frac1{j-1} - \frac1j\right) \\ & = 1 \end{aligned}$

(2) 考虑到 (1) 计算出的答案是 $1$，这在隐隐约约之中指引着我们去寻找 (1) 和 (2) 之间的联系。

经过一番考虑，我们发现如果分子分母同除 $k$ 会有奇效：

${1 \over k - 1} = \frac1k \cdot {1 \over 1 - \frac1k} = \frac1k\sum_{j=0}^\infty {1 \over k^j} = \sum_{j=1}^\infty {1 \over k^j}$

所以原式变身为：

$\sum_{k \in P}\sum_{j=1}^\infty \frac1{k^j}$

十分巧妙的是，我们可以找出一种一一对应的关系，满足 $p^q = k^j$，其中 $p,\;q \geqslant 2$ （即 (1) 中的下标 $j$ 和 $k$），而 $k \in P,\;j\geqslant 1$ （上面那个式子的下标）。

根据 $P$ 的定义，设 $k = m^n$。在这里，我们可以要求 $m \notin P$，因为如果 $m \in P$，那么意味着 $m$ 又可以被表示成 $a^b$ 的形式，这时我们只需令 $m = a$ 并且使 $n$ 乘上 $b$ 就可以了。所以具体对应方案如下：

1. 当 $j > 1$ 时，我们显然可以直接令 $p = k$ 以及 $q = j$，就可以满足要求。
2. 当 $j = 1$ 时，由于 $k = m^n$，所以我们还是可以令 $p = m$ 而 $q = n$。

为了证明这是双射，所以我们还需要从另一个方向来对应：

1. 若 $p \in P$，则 $k = p$ 并且 $j = q$，这是因为 $k \in P$。
2. 若 $p \notin P$，则 $k = p^q$，此时 $j = 1$。从这里可以看出我们要求 $m \notin P$ 的好处。

至此，我们就成功证明了 (2) 中的等式。

2018.1.7

问题描述

证明：对于任意的正整数 $n$，均可被表示为 $\left\lfloor \sqrt2 k \right\rfloor$ 或 $\left\lfloor (2 + \sqrt2)k \right\rfloor$ 中的有且仅有一种形式，其中 $k$ 也是正整数。

换句话说，集合 $A = \left\{\left\lfloor \sqrt2 k \right\rfloor \mid k \in \mathbf{N}^+\right\}$，$B = \left\{\left\lfloor (2 + \sqrt2) k \right\rfloor \mid k \in \mathbf{N}^+ \right\}$，证明 $A \cap B = \varnothing$ 并且 $A \cup B = \mathbf{N}^+$，就像把正整数集划分为两半一样。

解决方案

这个思路确实比较有趣，我们尝试证明，对于任意的正整数 $n$，集合 $A$ 中不大于 $n$ 的元素个数 $a$ 与集合 $B$ 中不大于 $n$ 的元素个数 $b$ 之和等于 $n$。如果得到了这个结论，原命题就很容易说明了。

先考虑集合 $A$:

$\begin{aligned} a & = \sum_k \left[1 \leqslant \left\lfloor \sqrt2 k \right\rfloor \leqslant n \right] \\ & = \sum_k \left[1 \leqslant \sqrt2 k < n + 1\right] \\ & = \left\lceil {n + 1 \over \sqrt2} \right\rceil - \left\lceil {1 \over \sqrt2} \right\rceil \\ & = \left\lceil {n + 1 \over \sqrt2} \right\rceil - 1 \end{aligned}$

同理可得：

$\begin{aligned} b & = \left\lceil {n + 1 \over 2 + \sqrt2} \right\rceil - 1 = \left\lceil {(2 - \sqrt2)(n + 1) \over 2} \right\rceil - 1 \\ & = n + 1 + \left\lceil -{\sqrt2(n + 1) \over 2} \right\rceil - 1 \\ & = n - \left\lfloor {n + 1 \over \sqrt2} \right\rfloor \end{aligned}$

因此：

$a + b = n - 1 + \left\lceil {n + 1 \over \sqrt2} \right\rceil - \left\lfloor {n + 1 \over \sqrt2} \right\rfloor \tag{1}$

我们知道，对于任意实数 $r$：

$\lceil r \rceil - \lfloor r \rfloor = \begin{cases} 0 & (r \in \mathbf{N}) \\ 1 & (\text{otherwise}) \end{cases}$

而 $(n+1) / \sqrt2$ 一定是无理数，故 $(1)$ 式中的取上整减取下整的部分恒为 $1$，即 $a + b = n$。

事实上，对于任意的正无理数 $\alpha$ 和 $\beta$，只要满足 $1/\alpha + 1/\beta = 1$，集合 $A = \left\{\left\lfloor \alpha k \right\rfloor \mid k \in \mathbf{N}^+\right\}$ 和集合 $B = \left\{\left\lfloor \beta k \right\rfloor \mid k \in \mathbf{N}^+\right\}$ 就会是一个正整数的划分。具体的证明方法与上面类似。

2018.1.13

问题描述

求下面这个递推式的通项公式：

$\begin{aligned} R(1) & = 4 \\ R(n + 1) & = 3R(n) + 2^{n-1}-4n ~~~~(\forall n > 1) \end{aligned}$

解决方案

这里主要是记录一下 Repertoire Method 这种方法，不过现在我还不知道该怎么翻译这个名称…

这个方法基于一个简单的观察：如果设

$\begin{aligned} R(1) & = a \\ R(n + 1) & = 3R(n) + b\cdot 2^{n-1} + c\cdot n + d \end{aligned}$

我们会发现：

$\begin{aligned} R(1) & = a \\ R(2) & = 3a + b + c + d \\ R(3) & = 9a + 5b + 5c + 4d \\ R(4) & = 27a + 19b + 18c + 13d \\ R(5) & = 81a + 65b + 58c + 40d \\ &\cdots \end{aligned}$

可以猜测，$R(n)$ 的通项公式可以被写成以下形式：

$R(n) = a\cdot f(n) + b \cdot g(n) + c\cdot h(n) + d \cdot \varphi(n)$

其中 $f(n)$、$g(n)$、$h(n)$ 和 $\varphi(n)$ 都是关于 $n$ 的简单函数。运用数学归纳法，不难证明可以一直保持这种形式。

我们现在的目标就是求出这四个函数。接下来的步骤就比较投机了，我们可以猜测当 $a$、 $b$、$c$、$d$ 取不同值的时候 $R(n)$ 可能的形式，我们可以假设 $R(n) = 1$，尝试找出是否有对应的值。根据递推的等式，可以列出：

$\begin{cases} 1 = a \\ 1 = 3 \times 1 + b \cdot 2^{n-1} + c\cdot n + d \end{cases}$

不难发现：$a = 1$ 以及 $d = -2$，其余两个变量只能为 $0$。回代到 $R(n)$ 的通项公式中：

$R(n) = f(n) - 2\varphi(n) = 1$

我们明白，如果能按照类似的方式找到 $4$ 个这样的方程，我们就可以把四个函数全部都解出来。现在继续尝试一些其它的函数。考虑到递推式中有 $n$ 这种东西，可以尝试当 $R(n) = n$ 时的情况：

$\begin{cases} 0 = a \\ n + 1 = 3n + b \cdot 2^{n-1} + c\cdot n + d \end{cases}$

可以解出 $a = 1,\;c = -2,\;d = 1$。因此 $f(n) - 2h(n) + \varphi(n) = n$。

根据同样的想法，尝试一下 $R(n) = 2^n$：

$\begin{cases} 2 = a \\ 2^{n+1} = 3 \times 2^n + b \cdot 2^{n-1} + c\cdot n + d \end{cases}$

此时 $a = 2,\;b = -2$，同时我们有 $f(n) - g(n) = 2^{n-1}$。

此外注意到第二个递推式中 $R(n)$ 前的系数是 $3$，说明通项公式中应该是有 $3^n$ 这种东西的。于是尝试 $R(n) = 3^n$：

$\begin{cases} 3 = a \\ 3^{n + 1} = 3^{n+1} + b \cdot 2^{n-1} + c\cdot n + d \end{cases}$

So easy, $a = 3$，并且可以直接知道 $f(n) = 3^{n - 1}$。

现在 $4$ 个方程集齐了，只需要解下面这个方程组：

$\left\{ \begin{aligned} f(n) - 2\varphi(n) & = 1 \\ f(n) - 2h(n) + \varphi(n) & = n \\ f(n) - g(n) &= 2^{n-1} \\ f(n) & = 3^{n - 1} \end{aligned} \right.$

不难解出：

$\left\{ \begin{aligned} f (n) & = 3^{n - 1} \\ g(n) & = 3^{n-1} - 2^{n - 1}\\ h(n) & = \frac14 3^n - \frac12 n - \frac14 \\ \varphi(n) & = \frac12 3^{n - 1} - \frac12 \end{aligned} \right.$

现在来解决原问题。原问题中，$a = 4,\;b = 1,\;c = -4,\;d = 0$，所以 $R(n) = 4f(n) + g(n) - 4h(n) = 2\times 3^{n-1} - 2^{n-1}+2n+1$。纵观整个过程，Repertoire Method 并不简单，甚至有点繁琐，但仍不失为探究问题的一种好思路。

2018.2.17

问题描述

证明，对于任意的整数 $n$ 和正整数 $m$，满足：

$\left\lceil {n \over m} \right\rceil = \left\lfloor {n + m - 1 \over m} \right\rfloor$

解决方案

直接证明这个问题并不是特别困难，因为右边就是 $1 + \lfloor n/m - 1/m \rfloor$，然后分情况讨论 $n/m$ 是否为整数就可以得到结论。这里就不详细说了。

另外一种方法比较有意思，考虑将 $n$ 表示为 $m\lfloor n/m \rfloor + n \bmod m$ 的形式，然后上式左右同减 $\lfloor n/m \rfloor$ 可以得到：

$\begin{aligned} & \left\lceil {n \over m} \right\rceil = \left\lfloor {n + m - 1 \over m} \right\rfloor \\ \Leftrightarrow \ & \left\lceil {n \over m} \right\rceil - \left\lfloor {n \over m} \right\rfloor = \left\lfloor {m\lfloor n/m \rfloor + n \bmod m + m - 1 \over m} \right\rfloor - \left\lfloor {n \over m} \right\rfloor \\ \Leftrightarrow \ & \left[\frac{n}m \not\in \mathbf{Z} \right] = \left\lfloor {n \over m} \right\rfloor + \left\lfloor {n \bmod m + m - 1 \over m} \right\rfloor - \left\lfloor {n \over m} \right\rfloor \\ \Leftrightarrow \ & [n \bmod m \neq 0] = [n \bmod m + m - 1 \geqslant m] \\ \Leftrightarrow \ & [n \bmod m > 0] = [n \bmod m > 0] \end{aligned}$

从而证明了等式。

2018.4.4

问题描述

（IMO 2012 预选题 C2）

在 $\{1,2,...,n\}$ 中最多能选出多少对不相交的二元组 $(a, b)$，满足 $a + b \leqslant n$，并且任意两对的元素之和不同？

如，当 $n = 6$ 时，可以找出 $2 + 4 = 6$ 和 $1 + 3 = 4$，并且最多也只能找出两对。

解决方案

首先考虑上界，假设找到了 $m$ 对，则选出来的数字之和至少是：

$\sum_{k=1}^{2m}k = m(2m + 1)$

而每对的和两两不同，意思是数字之和至多为：

$\sum_{k = 0}^{m-1}(n-k) = mn - {m(m-1) \over 2}$

根据这两个界限，可知：

$m \leqslant {2n - 1 \over 5} \Leftrightarrow m \leqslant \left\lfloor {2n - 1 \over 5} \right\rfloor$

现在我们来尝试构造，使得正好能选出 $\lfloor (2n - 1)/5 \rfloor$ 对二元组。为了更方便地考虑这个问题，首先构建一个直观一点的模型。设第 $k$ 个二元组（$1 \leqslant k \leqslant m$）为 $(a_k, b_k)$，以及 $c_k = a_k + b_k$。尝试 $a_k = k$ 以及 $c_k = n - k + 1$ 的情况（也就是选取的最小的 $m$ 个数字和最大的 $m$ 个和，因为这样看起来成功率高一些），建立一个表格，如下图所示，其中每一个在第 $x$ 行第 $y$ 列的单元格上的数字为 $c_y - a_x$，代表 $b_k$ 的候选值：

$n = 11$，$m = 4$ 时的情况。 左边一竖列从上至下为 $a_1..a_m$，最上面一横排从左至右为 $c_m..c_1$，中间 $16$ 个单元格代表的是 $b_k$ 的候选值。图中给出了一种构造方案，即 $1 + 8 = 9$，$2+9=11$，$3+5=8$ 和 $4+6=10$，这也是最优的方案之一

观察这个表格，一个重要的信息就是每一个从左上至右下的斜列（后简称斜列）上的数字是一样的。正如上图中所展示的，我们需要从中间 $m^2$ 个单元格中圈出 $m$ 个数字作为 $b_1..b_m$。当然这是有讲究的。由于不能选相同的数字，所以每一行、每一斜列均只能圈一个；因为和要两两不同，所以每一竖列也只能圈一个。同时我们注意到左下角可能会有和 $a_1..a_m$ 相同的区域，姑且称其为 “禁区”，因为这个里面的数字也不能圈。如果这些条件均满足了，那么不难发现我们得到了一个合法方案。

根据上面的限制，格子中究竟写了什么数字已经不再重要了。现在的麻烦主要在于左下角的 “禁区”，它导致我们不能随意选择。因此，在构造的时候，要尽可能远离那个区域，也就是左下角要尽可能留出空白。为了探究规律，手玩一下 $m$ 较小的情况：

$m$ 为 $1..6$ 时的最优解？

上图中 $m = 6$ 的规律已经体现得很明显了。记第 $x$ 行第 $y$ 列为 $(x, y)$。我们从 $(1, 2)$ 开始，设当前处在 $(x, y)$ 处，则下一步移动到 $(x+1,y+2)$ 处。如果 $y + 2 > m$，则移动到 $(x + 1, 1)$ 处。这有点类似于象棋中的 “跳马”。

这样构造出来的方案显然是满足要求的，但是我们还需要考察 $m$ 的最大值，因为随着 $m$ 的增大，“禁区” 的范围也会扩大。由于我们的 “马步” 走法的直线的斜率小于 “禁区” 边界的斜率，所以只需考虑第 $1$ 列中的情况。在表格中 $(x, y)$ 上的数字为 $n - m - x + y$，易知最左列中 “禁区” 最高点是倒数第 $3m - n$ 个格子，而在这一列中，我们选取的位置是倒数第 $\lceil m/2 \rceil$ 个格子，所以：

$\begin{aligned} & 3m - n < \left\lceil {m\over 2} \right\rceil \\ \Leftrightarrow \: & 3m - n < \frac{m}2 \\ \Leftrightarrow \: & m < {2n \over 5} \\ \Leftrightarrow \: & m \leqslant \left\lceil{2n \over 5}\right\rceil - 1 = \left\lceil{2n - 5\over 5}\right\rceil \\ \end{aligned}$

虽然我们得到的结果与之前不同，但实际上 $\lceil (2n - 5) / 5 \rceil = \lfloor (2n - 1) / 5 \rfloor$，这是因为：

$\begin{aligned} &\left\lceil {2n - 5 \over 5} \right\rceil = \left\lfloor {2n - 1 \over 5} \right\rfloor \\ \Leftrightarrow \: & \left\lceil {2n - 5 \over 5} \right\rceil \leqslant {2n - 1 \over 5} < \left\lceil {2n - 5 \over 5} \right\rceil + 1 \\ \Leftrightarrow \: & \left\lceil {2n - 1 \over 5} - \frac45 \right\rceil \leqslant \left\lfloor {2n - 1 \over 5} \right\rfloor \leqslant {2n - 1 \over 5} < {2n \over 5} \leqslant \left\lceil {2n \over 5} \right\rceil \end{aligned}$

最后一行最左边的小于等于号是通过分 $(2n - 1) / 5$ 是否为整数的两种情况讨论得来的：当它是整数时取等，否则其小数部分不大于 $4/5$，所以不等式成立。综上，答案就是 $\lceil (2n - 5) / 5 \rceil = \lfloor (2n - 1) / 5 \rfloor$。

2018.5.19

问题描述

(1) 给定自然数 $n$，计算 $\newcommand{up}[1]{\left\lceil #1 \right\rceil}\newcommand{dw}[1]{\left\lfloor #1 \right\rfloor} \sum_{k=1}^\infty 2^k\lfloor n/2^k + 1/2\rfloor^2$。

(2) 给定实数 $x$，定义 $\newcommand{\dis}[1]{\lVert #1 \rVert} \dis{x} = \min\{\up{x} - x,\ x - \dw{x}\}$ 即 $x$ 离最近的整数的距离，计算 $\sum_{k \in \mathbf{Z}} 2^k \lVert x / 2^k \rVert^2$。

解决方案

(1) 计算这个和的思路有点非常规，考虑递推的方法，设 $S_n$ 为上面的和式。考虑到任意自然数 $n$ 均可被唯一分解为 $2^p \cdot q$（$q$ 是奇数），当 $k = p + 1$ 时：

$\begin{aligned} \left\lfloor {n \over 2^k} + \frac12 \right\rfloor & = \left\lfloor {q + 1 \over 2} \right\rfloor = {q + 1 \over 2} \\ \left\lfloor {n - 1 \over 2^k} + \frac12 \right\rfloor & = \left\lfloor {q + 1 \over 2} \right\rfloor - 1 = {q - 1 \over 2} \end{aligned}$

所以 $S_n$ 和 $S_{n - 1}$ 中第 $k$ 项之差为 $2^k \cdot q = 2n$，而其余项中 $n / 2^k$ 得不到像上面 $q$ 这样的奇数，两者结果相同。所以 $S_n = S_{n - 1} + 2n = n^2 + n$。

(2) 第二问实际上除了形式与第一问类似，其实没有多少关联......

为了方便书写和探究，记函数 $f(x)$ 为我们需要计算的式子。写个程序瞎试一下其实会发现 $f(x) = x \ (x \geqslant 0)$。此外由于平方的原因，$f(-x) = f(x)$，不难推测 $f(x) = \lvert x \rvert$。

难的是如何证明猜出来的结论。首先无论 $k$ 趋向于正无穷还是负无穷，级数总是收敛的，故对于所有的 $x$，$f(x)$ 总存在。由于 $f(-x) = f(x)$，因此我们可以只用考虑 $x \geqslant 0$ 的情况。另外可以注意到 $f(2x) = 2f(x)$。令 $f(x) = l (x) + r(x)$，将 $f(x)$ 中 $k \leqslant 0$ 的项放入 $l(x)$ 中，其余的放入 $r(x)$ 中，分开处理这两部分。

对于 $l(x)$，由于 $1/2^k$ 当 $k \leqslant 0$ 时均为整数，所以 $\lVert x / 2^k \rVert = \lVert (x + 1) /2^k \rVert$，即 $l(x + 1) = l(x)$。因为 $\lVert x \rVert \leqslant 1/2$，所以 $l(x) \leqslant \sum_{k = 0}^\infty 2^k / 4 = 1/2$。

对于 $r(x)$，$k > 0 \Rightarrow 2^k \geqslant 2$，$0 \leqslant x < 1$ 时，$\lVert x / 2^k \rVert$ 和 $\dis{(x+1)/2^k}$ 都可以简单地化简出来。此时 $r(x) = \sum_{k=1}^\infty x^2/2^k = x^2 < 1$，而 $r(x + 1) = (1-x)^2/2 + \sum_{k=2}^\infty (x+1)^2/2^k = x^2 + 1$。即 $r(x + 1) = r(x) + 1$。综上，当 $0 \leqslant x < 1$ 时 $f(x + 1) = f(x) + 1$。

是否有更一般的结论呢？对于任意自然数 $n$，$f(x + n) = f(x) + n$ 能否被证明？考虑到 $f(2x) = 2f(x)$，因此尝试将 $n$ 设为 $2^mq + r$ 的形式，其中 $m \geqslant 1$，$r$ 为 $0$ 或 $1$ 从而使得 $m$ 的条件可以满足。对 $n$ 使用归纳法，当 $n = 0,\ 1$ 时显然，之后 $f(x + n) = 2^mf((x+r)/2^m + q)$，由于 $q < n$ 且 $x + r < 2 \leqslant 2^m$ 根据归纳假设，之前的式子等于 $2^mf((x+r)/2^m) + 2^mq = f(x + r) + n - r = f(x) + n$。

根据以上结论，再结合 $f(0) = 0$，我们已经可以得到对于任意整数 $n$，$f(n) = \lvert n \rvert$。接下来的步骤非常巧妙的利用了夹逼原理：还是假设 $x \geqslant 0$，对于任意正整数 $m$，我们有：

$$ \begin{aligned} f(x) & = 2^{-m}f(2^mx) \\ & = 2^{-m}\dw{2^mx} + 2^{-m}f(\{2^mx\}) \end{aligned} $$

现在是时候来证明我们的猜想了：

$$ \begin{aligned} 0 \leqslant \lvert f(x) - x \rvert & = \lvert 2^{-m}\dw{2^mx} - x + 2^{-m}f(\{2^mx\}) \rvert \\ & \leqslant 2^{-m}\lvert \dw{2^mx} - 2^mx \rvert + 2^{-m}f(\{2^mx\}) \\ & < 1\cdot 2^{-m} + (1/2 + 1) \cdot 2^{-m} = 5/2 \times 2^{-m} \end{aligned} $$

当 $m$ 趋近于无穷大时，右式趋近于 $0$。因此不难得到 $f(x) = \lvert x \rvert$ 的结论。

2018.6.10

问题描述

已知 $0 \leqslant a < 1$，$b \geqslant 0$，找出关于 $a$ 和 $b$ 的充要条件使得我们能够根据多重集合 $S(a,\ b)$：

$$ S(a,\ b) = \{\dw{na} + \dw{nb}:\ n \in \mathbf{N}^+\} $$

唯一确定 $a$ 和 $b$ 的值。

解决方案

对于这个题，关键的一个处理步骤就是令 $\newcommand{fa}[1]{\{ #1 \}}b = \dw{b} + \fa{b}$。考虑到 $\dw{b}$ 是整数，且 $0 \leqslant \fa{b} < 1$，可以尝试做出以下转化：

$$ \begin{aligned} \dw{na} + \dw{nb} & = \dw{na} + \dw{n\dw{b} + n\fa{b}} \\ & = \dw{n(a + \dw{b})} + \dw{n\fa{b}} \end{aligned} $$

换句话讲，$S(a,\ b) = S(\fa{b},\ a + \dw{b})$。因此可以得出其必要条件为 $a = \fa{b}$。

得到这个后证明它同时也是充分条件也就不难了。令 $n = 1$，可以得到 $\dw{b}$。之后将所有的 $n\dw{b}$ 从 $S(a,\ b)$ 中减去，得到 $S(a,\ \fa{b})$。由于 $a = \fa{b}$，所以将 $S(a,\ \fa{b})$ 中每个元素除以 $2$ 就是 $\{\dw{na}:\ n \in \mathbf{N}^+\}$，由此可以唯一确定 $a$。

2018.11.17

问题描述

已知 $\varphi$ 为任意实数，求：

$\lim_{n\rightarrow\infty} \prod_{k = 1}^n \cos{\varphi \over 2^k}$

解决方案

首先你需要跳出 $\cos$ 的怪圈，想到 $\sin$ 的倍角公式：

$\sin x = 2\cos \frac{x}2 \sin \frac{x}2$

于是你发现可以继续展开下去，得到一堆 $\cos$ 相乘：

$\sin x = 2^n\cos \frac{x}2 \cos \frac{x}4 \cdots \cos \frac{x}{2^n} \sin \frac{x}{2^n}$

所以我们求的极限就是：

$\lim_{n\rightarrow\infty} \prod_{k = 1}^n \cos{\varphi \over 2^k} = \lim_{n\rightarrow\infty} {\sin \varphi \over 2^n \sin \frac{\varphi}{2^n}}$

当然上面这里要求 $\sin(\varphi/2^n) \neq 0$。若 $\varphi \neq 0$，当 $n$ 足够大时，$0 < |\varphi / 2^n| < \pi / 2$，从此函数值就不可能等于 $0$ 了，这样就只剩 $\varphi = 0$ 的情况了。而若 $\varphi = 0$，原来那个极限等于 $1$，之后我们就默认其不为 $0$。由于 $\varphi / 2^n \rightarrow 0$，利用 $x \sim \sin x$ ($x \rightarrow 0$)，所以：

$\lim_{n\rightarrow\infty} {\sin \varphi \over 2^n \sin \frac{\varphi}{2^n}} = \lim_{n \rightarrow \infty} {\sin \varphi \over 2^n \frac{\varphi}{2^n}} = {\sin \varphi \over \varphi}$

2019.2.27

问题描述

已知正整数 $a$、$b$ 互质且 $a > b$，以及正整数 $m$、$n$。证明：

$\gcd(a^n - b^n,\ a^m - b^m) = a^{\gcd(n,\ m)} - b^{\gcd(n,\ m)}$

解决方案

涉及到 gcd 的计算时，Euclid 算法是一个好思路。假设 $n \geqslant m$，那么我们需要计算 $(a^n - b^n) \bmod (a^m - b^m)$。尝试关于 $a$ 做一下长除法：

$\phantom{a^m-b^m/} a^{n-m} + a^{n - 2m}b^m + a^{n - 3m}b^{2m} + \cdots \newline a^m - b^m /\overline{a^n - b^n\phantom{000000000000000000000000}} \newline \phantom{a^m-b^m/}\underline{a^n - a^{n - m}b^m} \newline \phantom{a^m-b^m/a^n-}a^{n - m}b^m - b^n\phantom{000} \newline \phantom{a^m-b^m/a^n-}\underline{a^{n - m}b^m - a^{n - 2m}b^{2m}} \newline \phantom{a^m-b^m/a^n-a^{n-m}b^m-}a^{n - 2m}b^{2m} - b^n \newline \phantom{a^m-b^m/a^n-a^{n-m}b^m-}\underline{a^{n - 2m}b^{2m} - a^{n - 3m}b^{3m}} \newline \phantom{a^m-b^m/a^n-a^{n-m}b^m-a^{n-2m}b^{2m}-}a^{n - 3m}b^{3m} - b^n \newline \phantom{a^m-b^m/a^n-a^{n-m}b^m-a^{n-2m}b^{2m}-}\cdots$

算了几项后就不难看出 $a^n - b^n = (a^m - b^m)(a^{n-m}+a^{n-2m}b^m+\cdots+a^rb^{n-m-r}) + a^rb^{n-r}-b^n$，这里 $r = n \bmod m$。所以原式等于 $\gcd(a^rb^{n-r}-b^n,\ a^m - b^m) = \gcd(b^{n-r}(a^r-b^r),\ a^m - b^m)$。可惜的是带着一个 $b^{n-r}$，没能直接达成目标。

不过目前为止我们还没用过 $a$ 与 $b$ 互质这个条件。试想如果 $b^{n-r}$ 与 $a^m - b^m$ 互质，那么就可以直接去掉它。注意到 $b^{n - r}$ 实际上就是 $b^{m\lfloor n/m \rfloor}$，不妨写作 $b^{km}$。考虑 $\gcd(b^{km},\ a^m - b^m)$，对 $b^{km}$ 关于 $b$ 做长除法，可以得到 $b^{km} = (a^m - b^m)\left(-b^{(k - 1)m} - a^mb^{(k - 2)m} - \cdots - a^{(k - 1)m}\right) + a^{km}$，故：

$\gcd(b^{km},\ a^m - b^m) = \gcd(a^{km},\ a^m - b^m)$

由于上面两式相等，记做 $d$，那么 $d\mid a^{km}$ 并且 $d\mid b^{km}$，这等价于 $d \mid \gcd(a^{km},\ b^{km})$，而 $a$ 与 $b$ 互质，故 $d = 1$，因此在原式中可以去掉 $b^{n - r}$，从而得以递归完成证明。

2019.3.6

问题描述

对于正整数 $n$，找到最小的 $m$，使得存在一个长度为 $p$ 递增序列 $\{a_k\}$ 满足 $n = a_1 < a_2 < \cdots < a_p = m$ 且 $\prod_{k = 1}^p a_k$ 为完全平方数，记 $f(n) = m$。证明：$f$ 是一个从正整数集 $\mathbb N$ 到合数集（包括 $1$，记做 $C$）的双射。

解决方案

动手之前先要明白，证明 $f$ 为双射需要能够确认 1) 值域为 $C$；2) $f$ 是单射；3) $f$ 是满射。首先，$f(1) = 1$ 这一对可以简单地排除掉。此外，$f(n)$ 不可能为质数，因为递增序列里面的数字是不重复的，如果最后一个数是质数，那么它就只有一个，导致乘积不是完全平方数，这保证了第一点。

第二，所谓单射就是不同的变量值映射到了不同的函数值。考虑 $1 < x < y$，如果 $f(x) = f(y) = r$，那么存在 $x = a_1 < a_2 < \cdots < a_p = r$ 以及 $y = b_1 < b_2 < \cdots < b_q = r$，满足 $\prod_{k=1}^p a_k$ 和 $\prod_{k = 1}^q b_k$ 均为完全平方数。注意到 $r$ 在其中出现了两次，于是乎我们可以考虑 $\prod_{k=1}^pa_k\prod_{j=1}^qb_j$，将其中重复出现的数字除去，得到的乘积依然为完全平方数，且其中没有 $r$。因为 $x < y$，所以其中最小的数字为 $x$，这推出 $f(x) < r$，产生矛盾。所以 $f$ 为单射。

最后，所谓满射就是对于值域内每一个值，都是对应的变量值映射过来。这需要我们从反方向考虑。既然 $f(n)$ 是找最小的 $m$，不妨考虑令 $g(m)$ 表示最大的 $n$ 使得存在题中所述的序列。首先要保证 $g(m)$ 的定义是合理的：对于每个合数 $m$，可以写成 $m = ab$，并且假设 $1 < a < b < m$，显然 $abm$ 是满足要求的，所以至少有一个合法的方案。之后我们就希望 $f(g(m)) = m$。根据 $f(n)$ 最小化的要求，$f(g(m)) \leqslant m$。如果 $r = f(g(m)) < m$，类似于之前的讨论，存在 $g(m) = a_1 < a_2 < \cdots < a_p = r$ 和 $g(m) = b_1 < b_2 < \cdots < b_q = m$ 满足对应的乘积为完全平方数。这时候 $g(m)$ 又出现了两次，于是乎同样的套路，对于右端点 $m$ 我们可以得到左端点比 $g(m)$ 更大的方案，与 $g(m)$ 的定义矛盾，于是 $f(g(m)) = m$¹，可以得到 $f$ 是满射。

2019.3.6

问题描述

在 $n$ 维 Euclidean 空间 $\mathbb R^n$ 上，定义一个点 $x$ 到一个点集 $A$ 之间的距离 $\lambda(x,\ A)$ 为：

$\lambda(x,\ A) = \inf\{|x - y|:\ y \in A\}$

类似的，对于 $\mathbb R^n$ 中的两个点集 $A$ 和 $B$，定义两个集合间的距离 $\lambda(A,\ B)$ 为：

$\lambda(A,\ B) = \inf\{|x - y|:\ x \in A,\ y \in B\} = \inf\{\lambda(x,\ B):\ x \in A\}$

考虑当 $A$ 与 $B$ 有交集时，显然 $\lambda(A,\ B) = 0$；现假设 $A \cap B = \varnothing$：

(1) 此时 $\lambda(A,\ B)$ 是否恒大于 $0$?

(2) 若 $A$、$B$ 均为闭集，则 $\lambda(A,\ B)$ 是否恒大于 $0$？

(3) 若 $A$ 为紧集，$B$ 为闭集，则 $\lambda(A,\ B)$ 是否恒大于 $0$？

解决方案

(1) 两个开区间 $(1,\ 2)$ 和 $(2,\ 3)$ 不相交，但是取 $x_k → 2^-$ 和 $y_k → 2^+$ 得到 $|x_k - y_k| → 0$。

(2) 在 (1) 中因为开集不包含自己的聚点，因此只要有公共聚点，就会导致集合间的距离可以无限靠近。然而即使要求没有公共聚点，集合间的距离依然可以无限靠近，毕竟集合间在无限远处的行为没有限定。在实数轴上可能难以想象反例，不过在二维 Euclidean 空间中，考虑 $A = \{(x,\ y):\ y \geqslant 1/x,\ x > 0\}$ 和 $B = \{(x,\ y):\ y \leqslant -1/x,\ x > 0\}$，当 $x → +\infin$ 时两个集合的边界不断靠近，不难得出这两个集合间的距离为 $0$。

在实数轴上也有反例。首先回顾一下：离散集也是闭集。这样一来，令 $A = \mathbb Z$，$B = \{n + 1/n:\ n \in \mathbb Z\}$，当 $n → +\infin$ 时可以看出 $A$、$B$ 间的距离为 $0$。

(3) 更进一步，当我们限定 $A$ 为有界闭集时，等价于当 $A$ 是紧集时，以上两个漏洞就钻不了啦，此时可以证明 $\lambda(A,\ B) > 0$。

如果从紧集的开覆盖定义出发，我们会联想到闭集的补集是开集，这样这条路就通了。考虑 $B$ 的补集 $\complement B$：对任意 $\complement B$ 中的点 $x$，总存在 $\delta(x) > 0$，满足以 $x$ 为圆心，半径为 $\delta(x)$ 的开邻域 $\mathcal O(x,\ \delta(x))$ 完全在 $B$ 之外。于是构造 $\mathcal C = \{\mathcal O(x,\ \delta(x) / 2):\ x \in \complement B\}$ 为 $\complement B$ 的一个开覆盖。这里半径减半是为了方便之后留出 $A$ 与 $B$ 之间的间距做的准备。由于 $A \cap B = \varnothing$，所以 $A \subset \complement B$，故 $\mathcal C$ 也是 $A$ 的开覆盖，因此存在一个有限子覆盖 $C$。取 $\delta = \min\{\delta(x):\ \mathcal O(x,\ \delta(x)/2) \in C\}$，考虑任意 $A$ 中的点 $y$，总存在开邻域 $\mathcal O(x,\ \delta(x)/2) \in C$ 盖住了 $y$，那么显然 $\mathcal O(y,\ \delta(x)/2) \subset \mathcal O(x,\ \delta(x))$，而后者与 $B$ 无交集，故 $\lambda(y,\ B) \geqslant \delta(x)/2 \geqslant \delta/2$，因此有 $\lambda(A,\ B) = \inf\{\lambda(y,\ B):\ y \in A\} \geqslant \delta/2 > 0$。

直接用紧集的定义给人一种强行证明的感觉。实际上，我们还可以从连续函数的角度出发，那就是考虑 $A \mapsto \mathbb R$ 的多元函数 $f(x) = \lambda(x,\ B)$。我们知道紧集上的连续函数必能取到最值，假如 $\xi \in A$ 是最小值点，则 $f(x) \geqslant f(\xi) = \lambda(\xi,\ B) > 0$，直接就完成了证明。连续意味着当两个点无限接近时，函数值也会无限逼近。因此，考虑 $A$ 中的两个点 $x_1$、$x_2$：

在 $\mathbb R^2$ 中的距离示意图

如上图，考虑取 $B$ 中任意一点 $P$，那么有 $f(x_1) \leqslant |x_1 - P|$ 以及 $f(x_2) \leqslant |x_2 - P|$，此时将两个函数值与两条边关联起来了。在 $\triangle Px_1x_2$ 中：

$|x_1 - x_2| \geqslant \big||x_1 - P| - |x_2 - P|\big|$

对不等式两边同时枚举 $P \in B$ 求下确界，得到：

$|x_1 - x_2| \geqslant \left|\inf_{P \in B}|x_1 - P| - \inf_{P \in B}|x_2 - P|\right| = |f(x_1) - f(x_2)|$

因此 $f(x)$ 满足 Lipschitz 连续条件，故 $f(x)$ 连续。

2019.4.19

问题描述

证明：对于正整数 $n$ 和 $m$，

(1) 若 $n^k \equiv 1 \pmod m$，则 $n \perp m$。

(2) 若 $n^ p \equiv n^q \equiv 1 \pmod m$，则 $n^{\gcd(p,\ q)} \equiv 1 \pmod m$。

(3) 若 $n^{m - 1} \equiv 1 \pmod m$ 以及对于所有 $m - 1$ 的质因子 $p$ 满足 $n^{(m - 1)/p} \not\equiv 1 \pmod m$，则 $m$ 为质数。

解决方案

(1) 非常简单，使用 Euclid 算法即可：
$\gcd(n^k,\ m) = \gcd(1,\ m) = 1$
而 $\gcd(n,\ m) \mid \gcd(n^k,\ m)$，所以 $\gcd(n,\ m) = 1$，即 $n$ 与 $m$ 互质。

(2) 类似的，可以利用所谓更相减损术。假设 $p > q$，则
$n^p \equiv n^q \ ⇒ \ n^q(n^{p - q} - 1) \equiv 0 \ ⇒ \ n^{p - q} \equiv 1 \pmod m$
此时保持条件 $n^{p - q} \equiv n^q \equiv 1 \pmod m$，因此一直进行下去直到有 $n^{\gcd(p,\ q)} \equiv 1 \pmod m$ 即可。

(3) 前面两个实际上是帮助解决 (3) 的简单结论。首先我们就可以通过第一个条件得知 $n \perp m$，包括 $n$ 的任意幂次都与 $m$ 互质。可这和 $m$ 为质数有什么关系？试想如果 $n^k$ 可以遍历 $1$ 到 $m - 1$ 每一个数，那就可以得到这些数都与 $m$ 互质，从而推出 $m$ 为质数。考虑到幂次在模 $m$ 意义下有循环节，因此我们只考虑 $n^1$ 到 $n^{m - 1}$，因此我们需要这些幂次两两之间互不相同。

假设存在 $1 \leqslant j < k < m$ 有 $n^j \equiv n^k \pmod m$，那么就有 $n^j(1 - n^{k - j}) \equiv 1 \pmod m$，也即 $n^{k - j} \equiv 1 \pmod m$，而这里 $1 \leqslant k - j \leqslant m - 2$。换句话说，对于 $1$ 到 $m - 2$ 中的幂次 $k$，不能有 $n^k$ 与 $1$，也就是 $n^{m - 1}$，同余。考虑反证法，如果存在这样的 $k$，那么就有 $n^k \equiv n^{m - 1} \equiv 1 \pmod m$，此时根据 (2) 中的结论，设 $d = \gcd(k,\ m - 1)$，那么 $n^d \equiv 1 \pmod m$。这一步的巧妙之处在于利用 $d$ 这个 $m - 1$ 的因子与第二个条件相沟通。因为 $k < m - 1$，于是 $d$ 至少与 $m - 1$ 相差了某个素因子 $p$，于是推出 $n^{(m - 1)/p}$ 是 $n^d$ 的整幂次，从而同余 $1$，与题设条件相违背，从而完成证明。

---