关于“猴子摘桃”问题的证明

cms42

俺用Markdown码的，渲染效果不好，请转https://www.zybuluo.com/cms42/note/1775467

猴子摘桃问题
问题符号化描述如下：

（约定以下全部讨论在\(Z_+\)值域内进行）
定义一函数 \(F(x) = \frac{a-1}{a}(x-1) \)，其中\(a \gt 1\)，显然这一函数并非对于所有\(x\)都在\(Z_+\)域内有意义，函数有意义的充要条件是\(x\equiv1\pmod{a}\)。
定义记号 \(F_n(x)\)表示对于\(x\)进行\(n\)次\(F\)变换，即：
\[
F_n(x)=\begin{cases}
x, & \text{ if } n = 0\\
F(F_{n-1}), & \text{ if } n \gt 0
\end{cases}
\]
设对于某一确定\(n\)，所有使\(F_n(x)\)在\(Z_+\)域内有意义的\(x\)的集合为\(T_n\)，其中最小的\(x\)为\(M_n\)。
给出\(a\)、\(n\)，求\(M_n\)。

据说结论为\(a^n-(a-1)\)，但我找了一圈似乎没有特别好的证明，遂尝试自行说明。这是萌新的第一次证明，多有不足之处，还请大佬批评指教。更简单的方法应该还有，希望能抛砖引玉。

***T1.1*** \(x \in T_n\)，当且仅当\(F(x) \in T_{n-1}\)

***T1.2*** 若\(x \in T_n\)，则\((x + a^n) \in T_n\)

***T1.3*** 在***T1.2***约定的条件下，不存在\(x \lt y \lt x + a^n\)且\(y \in T_n\)

***T1.1***正确性显然。***T1.2***利用数学归纳法说明如下：

\(n = 1 \)时，结论正确性显然；

假设结论对于\(n \le k - 1\)成立，对于\(n = k\)，由于\(x \in T_k\)，由***T1.1***得\(F(x) \in T_{k-1}\)，而\[F(x + a^k) = \frac{a-1}{a}(x + a^k - 1) = F(x) + \frac{a-1}{a}a^k = F(x) + (a - 1)a^{k-1}\]，由于\(F(x) \in T_{k - 1}\)，由归纳假设得\(F(x) + (a - 1)a^{k-1} \in T_{k-1}\)，即\(F(x + a^k) \in T_{k-1}\)，由***T1.1***得\((x + a^k) \in T_k\)，归纳假设成立。

***T1.3***可利用反证法和数学归纳法说明：假设这样的\(y\)存在，则\[0 < y - x < a^n，F(x) < F(y) < F(x) + (a-1)a^{k-1}\]
设\(t = F(y) - F(x)\)，由\(F\)函数性质可知\((a-1) | t\)。又由于\(t < (a-1)a^{k-1}\)，有\(\frac{t}{a-1} \lt a^{k-1}\)。则由***T1.1***、***T1.2***可知存在\(x' \in T_{k-1}\)满足\(x' \lt F(y) \lt x' + a^{k-1}\)，由归纳假设得\(F(y) \notin T_{k-1}\)，这与\(y \in T_k\)相矛盾。故假设不正确，\(y\)不存在。

***D1.1*** 将\(x\)在\(a\)进制下的表示中从右向左第\(i\)位设为\(x[ i ]\)。即，\(x = \sum_{i}x[ i ] \times a^{i-1}\)，且对于任意正整数\(i\)有\(0 \le x[ i ] \lt a\)。

在***D1.1***定义下，***T1.2***、***T1.3***可等价表述为：对于\(x \in T_n\)，\(x' \in T_n\)的充要条件是对于\(1 \le i \le n\)有\(x[ i ] = x'[ i ]\)，或称在\(a\)进制下它们的后\(n\)位相等。

***T1.4*** \(M_1 = 1, M_k = M_{k-1} + (a - 1) \times a^{k - 1}\) ，或等价表述为：在\(a\)进制下\(M_k\)有\(k\)位，末位为\(1\)，其余各位为\((a-1)\)

不妨用归纳法说明。显然\(M_1 = 1\)。
对于k，由于\(M_k \in T_k\)，显然\(M_k \in T_{k-1}\)，则有归纳假设我们有\(M_k\)末位为\(1\)，第\(2\)至\(k-1\)位均等于\((a-1)\)。设第\(k\)位为\(p\)，更高位为\(0\)（显然当且仅当此时\(M\)为最小值），由\(F\)定义和\(a\)进制下基本运算定义知\(F(M_k) = (M_k - 1) - \frac{1}{a}(M_k - 1)\)，即原数去除末位减去去除末位后右移一位的值，则\(F(M_k)\)第\(k-1\)位值为\((a-1) - 1 - p\)或\((a - 1) - 1 - p + a\)（退位时）。由\(M_k \in T_k\)知\(F(M_k) \in T_{k - 1}\)，由归纳假设得\(F(M_k)\)第\(k-1\)位应为\((a-1)\)，即：
\[(a-1) - 1 - p = a - 1\]或\[(a - 1) - 1 - p + a = a - 1\]

解第一个方程得\(p = -1\)，舍去；解第二个方程得\(p = a - 1\)，即\(M_k\)第\(k\)位取值为\(a-1\)，归纳假设成立。

则根据***T1.4***，所求的答案即\[M_n= 1 + \sum^{i \le n}_{i = 2}(a - 1)a^{i - 1} = a^n - (a - 1)\]