数学竞赛每日一练 第5期解答

题目来源：2021年浙江省女奥选拔试题。

已知数列 $x_0=0$，$x_1=1$，

$$ x_{n+1}=\left\{ \begin{aligned} x_n+n&,\ x_n< n\\ x_n-n&,\ x_n\geq n \end{aligned} \right. $$

求数列 $\{x_n\}$ 中使 $x_n=0$ 的所有项。

注． 原文为「简解」，只列出两条「不难证明」的断言。以下按原文转写，并把这两条断言以及由它们到最终结论的推理补齐。

解答 对于任意正整数 $n$，令

$$ g(n)=\left\{ \begin{aligned} 1&,\ x_{n+1}>x_n\\ -1&,\ x_{n+1}<x_n \end{aligned} \right. $$

另设 $g(0)=1$。由递推式可见，对 $n\geq 1$ 有

$$ g(n)=1\iff x_n< n,\qquad g(n)=-1\iff x_n\geq n. $$

又由归纳易知 $x_n\geq 0$：$x_0=0$，$x_1=1$；对 $n\geq 1$，若 $x_n< n$ 则 $x_{n+1}=x_n+n>0$，若 $x_n\geq n$ 则 $x_{n+1}=x_n-n\geq 0$。

命题 1. 除 $x_i=0$ 的情形外，不存在连续的 $i$ 和 $i+1$，使得 $g(i)=g(i+1)=1$。

证明． 设 $g(i)=g(i+1)=1$。由 $g(i)=1$ 得 $x_{i+1}=x_i+i$；再由 $g(i+1)=1$ 得 $x_{i+1}<i+1$。于是 $x_i+i<i+1$，即 $x_i<1$。由 $x_i\geq 0$ 得 $x_i=0$。$\square$

命题 2. 不存在连续的 $i$ 和 $i+1$，使得 $g(i)=g(i+1)=-1$。

证明． 反设存在，取满足条件的最小的 $i$。显然 $g(0)=1$（$x_1=1>x_0=0$），故 $i\geq 1$；又 $g(1)=-1$（$x_1=1\geq 1$），且 $x_2=0$、$g(2)=1$，故 $g(1)=g(2)$ 不可能是 $-1$，于是 $i\geq 2$。由 $i$ 的最小性知 $g(i-1)=1$，即 $x_{i-1}<i-1$，于是 $x_i=x_{i-1}+(i-1)<2(i-1)=2i-2$。另一方面，由 $g(i)=g(i+1)=-1$ 知 $x_i\geq i$、$x_{i+1}=x_i-i\geq i+1$，从而 $x_i\geq 2i+1$，矛盾。故命题成立。$\square$

结论． 设 $n\geq 2$ 且 $x_n=0$，考察 $n$ 之后的各项。由 $x_n=0<n$ 知 $g(n)=1$，$x_{n+1}=n$；再由 $x_{n+1}=n<n+1$ 知 $g(n+1)=1$，$x_{n+2}=2n+1$。这是命题 1 允许的唯一例外（$x_n=0$）。

此后由命题 1、2，$g$ 的取值在下一零项出现前必须严格交替，而 $x_{n+2}=2n+1\geq n+2$，故 $g(n+2)=-1$，于是

$$ x_{n+3}=x_{n+2}-(n+2)=n-1,\qquad x_{n+4}=x_{n+3}+(n+3)=2n+2, $$

即每经过一对 $(+1,-1)$，下标增加 $2$ 而 $x$ 的值减少 $1$。一般地，对 $0\leq t\leq n-1$，

$$ x_{n+1+2t}=n-t,\qquad x_{n+2+2t}=2n+1+t, $$

其中 $x_{n+1+2t}$ 处的 $g$ 值为 $1$ 自动成立（$n-t<n+1+2t$），而 $x_{n+2+2t}$ 处的 $g$ 值为 $-1$ 等价于 $2n+1+t\geq n+2+2t$，即 $t\leq n-1$：故对 $0\leq t\leq n-1$ 上式给出的值恰好构成 $g$ 的严格交替，而当 $t=n-1$ 时 $x_{3n}=3n$，$g(3n)=-1$，得 $x_{3n+1}=0$。即该项之后的第一个零点为 $n+1+2n=3n+1$。

所以若把 $x_n=0$ 的各项按大小记为 $0=n_0<n_1<n_2<\cdots$，则 $n_1=2$（直接计算：$x_1=1$，$x_2=0$），且对 $k\geq 1$

$$ n_{k+1}=3n_k+1. $$

解得

$$ n_k=\frac{5\cdot 3^{k-1}-1}{2}\quad(k\geq 1). $$

综上，$x_n=0$ 当且仅当 $n=0$ 或 $n=\frac{5\cdot 3^{m-1}-1}{2}$（$m$ 为任意正整数）。

例如 $m=1,2,3,4$ 依次给出 $x_2=x_7=x_{22}=x_{67}=0$。