**Solution of Interesting Math Problems**
Fans of Leaf God 🍃
“先有强哥后有天，知易道君还在前”
# 2022.5.26 立方体随机游走 (Easy Version)
对于如图所示的立方体，在 $0$ 时刻 $A$ 点有一只胖蜗牛，相邻时刻间胖蜗牛会在相邻的三个立方体节点中均匀随机一个，作为下一时刻的位置。
令 $p_n$ 表示对于时刻 $n$，胖蜗牛出现在 $A$ 点的概率，求 $p_n$ 的通项公式。
*********************
* *-----------*
* /| /|
* / | / |
* *-----------* |
* | | | |
* | | | |
* | *--------|--*
* | / | /
* |/ |/
* *-----------*
* A
*********************
## 解析
对立方体节点黑白染色，可得 $\forall\ k,\ 2\not\mid k$，有 $p_k=0$。
定义 $a_n = \left\{\begin{aligned}& \text{该时刻出现在 A 点的概率} & (2\mid n) \\ & \text{该时刻出现在 A 点周围的三个点的概率} & (2\not\mid n)\end{aligned}\right.$。
由古典概型推得 $a_n = \frac 1 3 a_{n-1} + \frac 2 3 a_{n-2}$，化用二阶线性递推的通用方法即可得解。
## 附件
提供的 Python 程序，可用于计算单点的 $p_n$ 值。
```py
n = int(input())
p = [0] * 8
p[0] = 1
r = [0] * 8
for i in range(n):
for j in range(8):
for k in range(3):
r[j ^ (1 << k)] += p[j] / 3
for j in range(8):
p[j] = r[j]
r[j] = 0
print(p[0])
```
# 2022.5.27 一个超级简单的数列题
设数列 $\{a_n\}$ 满足：若 $n=2k-1 \, (k \in \mathbb N^*)$，$a_n=n$；若 $n=2k \, (k \in \mathbb N^*)$，$a_n=a_k$。
1. 若 $S_n=a_1+a_2+a_3+\ldots +a_{2^{n}-1}+a_{2^{n}}$，求证：$S_n=4^{n-1}+S_{n-1}\ (n \ge 2)$。
2. 证明：$\displaystyle \frac 1 {S_1} + \frac 1 {S_2} + \frac 1 {S_3} + \ldots + \frac 1 {S_n} < 1 - \frac 1 {4^n}$。
## 解析
1. $\displaystyle \begin{aligned} S_n &=(a_1+a_3+a_5+\ldots +a_{2^n-3}+a_{2^n-1}) + (a_2+a_4+a_6+\ldots +a_{2^n-2}+a_{2^n}) \\ &=\left(1+3+5+\ldots +(2^n-3)+(2^n-1)\right) + (a_1+a_2+a_3+\ldots +a_{2^{n-1}-1}+a_{2^{n-1}}) \\ &=4^{n-1}+S_{n-1} \end{aligned}$
2. 可得 $S_n$ 通项公式为 $S_n=\dfrac{4^n+2}{3}$，简单放缩：$\dfrac 1 {S_n}=\dfrac 3 {4^n+2}< \dfrac 3 {4^n}$。
$$
\text{原式}
=\sum_{k=1}^n \frac 1 {S_k}
< \sum_{k=1}^n \frac 3 {4^n}
=1-\frac 1 {4^n}
$$
# 2022.5.28 一个有点意思的数列题
设数列 $\{a_n\}$ 满足：$a_1=3,\,a_{n+1}=a_n^2-a_n-\dfrac 5 4$。记 $b_n=\dfrac{2a_n-1+\sqrt{4a_n^2-4a_n-15}} 4$。
1. 求数列 $\{b_n\}$ 的通项公式，并据此写出 $\{a_n\}$ 的通项公式。
2. 设各项都为整数的数列 $\{c_n\}$ 满足：$c_n\le a_n < c_n+1,\, n\in \mathrm N^*$，记 $d_n=\dfrac{c_n}{c_{n+1}-1}$，证明：
$$
d_1+d_2+d_3+\ldots +d_n< \dfrac 4 3 \,,\quad n \in \mathrm N^*
$$
## 解析
1. 由 $b_n=\dfrac{2a_n-1+\sqrt{4a_n^2-4a_n-15}} 4$ 可推得 $a_n=b_n+\dfrac 1 {b_n}+\dfrac 1 2$。
代入 $a_{n+1}=a_{n}^2-a_n-\dfrac 5 4$ 得 $a_{n+1} = b_{n+1}+\dfrac 1 {b_{n+1}}+\dfrac 1 2 =\left(b_n+\dfrac 1 {b_n}\right)^2 - \dfrac 3 2$。
配方得 $\left(\sqrt{b_{n+1}}+\dfrac 1{\sqrt{b_{n+1}}}\right)^2 = \left(b_n+\dfrac 1{b_n}\right)^2$，有 $b_n> 0$，故 $b_{n+1}=b_n^2$。
代入 $a_1=3$ 得 $b_1=2$，可得 $b_n$ 通项公式为 $b_n=2^{2^{n-1}}$，代入得 $a_n=2^{2^{n-1}}+\dfrac 1 {2^{2^{n-1}}}+\dfrac 1 2$。
2. 不难发现 $\displaystyle c_n=\left\{\begin{aligned}& 2^{2^{n-1}}+1 \,& (n=1)\\& 2^{2^{n-1}} & (n\ge 2)\end{aligned}\right.$，只需消除掉首项的影响 $\dfrac 1 3$，即可令 $c_n=2^{2^{n-1}}$。
即证：
$$
\sum_{i=1}^{n} \frac {2^{n-1}} {2^{2{n}}-1} = \sum_{i=1}^{n} \frac 1 {2^{2{n-1}}-\dfrac 1 {2^{2^{n-1}}}} < 1 \,,\quad n \in \mathrm N^*
$$
注意到 $d_1=\dfrac 2 3 =\dfrac {4-\dfrac 2 4-1}{4-\dfrac 1 4} = \dfrac{2^{2^{n}}-\dfrac 2 {2^{2^{n}}}-1}{2^{2^{n}} - \dfrac 1 {2^{2^{n}}}}$，归纳证明：
$$
\begin{aligned}
\sum_{i=1}^n d_i
& = \dfrac{2^{2^{n-1}} - \dfrac 2 {2^{2^{n-1}}} - 1} {2^{2^{n-1}} - \dfrac 1 {2^{2^{n-1}}}} + \frac 1 {2^{2^{n-1}} - \dfrac 1 {2^{2^{n-1}}}} \\
& = \dfrac{\left(2^{2^{n-1}} - \dfrac 2 {2^{2^{n-1}}}\right)\left(2^{2^{n-1}} + \dfrac 1 {2^{2^{n-1}}}\right)} {\left(2^{2^{n-1}} - \dfrac 1 {2^{2^{n-1}}}\right)\left(2^{2^{n-1}} + \dfrac 1 {2^{2^{n-1}}}\right)} \\
& = \dfrac{2^{2^n} - \dfrac 2 {2^{2^n}} - 1} {2^{2^{n}} - \dfrac 1 {2^{2^{n}}}} < 1
\end{aligned}
$$
原命题得证。
## 来源
知乎用户 Way，原文链接：[https://zhuanlan.zhihu.com/p/506311927](https://zhuanlan.zhihu.com/p/506311927)。
第 2. 小问做法由笔者提供。
# 2022.5.29 一道供题人自己做错的简单概率题
对于一个魔方，定义一次随机拧角操作为随机顺时针或逆时针旋转一个角块，问 $n$ 次后此魔方能被还原的概率。
原命题等价于，定义变量 $X$ 的初始值为 $0$，每次随机拧角将分别有 $\dfrac 1 2$ 的概率将 $X$ 加上 $1$ 或 $-1$，若 $n$ 次拧角后魔方能被还原，则 $X \equiv 0 \quad (\bmod 3)$。
## 解析
注意到模 $3$ 余 $1$ 的情况和模 $3$ 余 $-1$ 的情况是对称的，我们可以将原题做以下转化：
* 若当前魔方是可还原的（下面用 $0$ 表示），则经过一次随机拧角后一定是不可还原的
* 若当前魔方是不可还原的（下面用 $1$ 表示），则经过一次随机拧角后，有 $\frac 12$ 的概率变为可还原的，还有 $\frac 1 2$ 的概率变为不可还原的。
定义 $\{a_{i,j}\}$ 来表示状态，有 $a_{0,0}=1,a_{0,1}=0$，
$$
\left\{\begin{aligned}
a_{n,0} &= \dfrac 1 2 a_{n-1,1} \\
a_{n,1} &= a_{n-1,0} + \dfrac 1 2 a_{n-1,1} \\
\end{aligned}\right.
$$
注意到 $a_{n,0}+a_{n,1} = 1$，故 $a_{n,0} = \dfrac 1 2 - \dfrac 1 2 a_{n-1,0}$，待定系数法得 $a_{n,0} - \dfrac 1 3 = -\dfrac 1 2(a_{n-1,0} - \dfrac 1 3)$。
从而得到 $a_{n,0}$ 的通项公式 $a_{n,0} = \dfrac 2 3 \left(-\dfrac 1 2\right)^n + \dfrac 1 3$ 即为答案。
## 来源
507 班董阳同志友情提供题目和一个错误的解法。
# 2022.5.30 一个可能不是数列题的数列题
已知正整数 $m\ge 3$，设数列 $\{a_n\}$ 满足：$a_m=0$，$a_{n+1}=a_1\ln a_n$ $(1\le n\le m-1)$。证明：
1. $a_2\le \dfrac {a_1^2}{e}$
2. $e-\dfrac{e-1}{m-2}< a_1< e$
## 解析
1. 代入递推式得原命题即
$$
\ln a_1\le \frac{a_1}{e}
$$
可用求导证明。
2. 假设 $a_1\ge e$，归纳：
$$
a_{n+1} = a_1 \ln a_n \ge a_1 \ge e
$$
故 $a_m\ge e\neq 0$，与题设矛盾。证得 $a_1< e$。
考虑证明等式左侧，等价于证
$$
\frac{\frac 1e - 1}{m-2} < \frac {a_1}e - 1
$$
由 $\ln x \le x-1$，即证
$$
\frac 1e - 1 < (m-2) \ln \left(\frac {a_1}e \right) \\
$$
类似于第一问的证明，可以得到：
$$
a_n\le \frac {a_1 a_{n-1}} e\le \frac {a_1^2 a_{n-2}} {e^2}\le \ldots \le \frac {a_1^n} {e^{n-1}}
$$
由 $a_m=0$，有 $a_{m-1} = 1$，$a_{m-2} = e^{\frac 1 {a_1}}$，将 $n=m-2$ 代入上式，得
$$
\begin{aligned}
e^{\frac 1 {a_1}} & \leq \frac {a_1^{m-2}} {e^{m-3}} \\
e^{\frac 1{a_1} - 1} & \leq \left(\frac {a_1}{e}\right)^{m-2} \\
\frac 1 {a_1} - 1 & \leq (m-2) \ln \left(\frac {a_1}e \right) \\
\end{aligned}
$$
由于上文已证 $a_1 < e$，故 $\dfrac{1}{a_1}>\dfrac{1}{e}$，原命题得证。
## 来源
知乎用户 Way，原文链接：[https://zhuanlan.zhihu.com/p/506311927](https://zhuanlan.zhihu.com/p/506311927)。
第 2. 小问做法由笔者提供。