数学问题杂记
riteme.site

数学问题杂记

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

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

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$ 的候选值:

imo-2012-c2-n11

$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$ 较小的情况:

imo-2012-c2-m16

$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$1,可以得到 $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$,与题设条件相违背,从而完成证明。


  1. 注意这个条件不能直接得到 $f$ 是双射的结论。