2009 IMO Shortlist C3

RUS Let $n$ be a positive integer. Given a sequence $\varepsilon_{1}, \ldots, \varepsilon_{n-1}$ with $\varepsilon_{i}=0$ or $\varepsilon_{i}=1$ for each $i=1, \ldots, n-1$, the sequences $a_{0}, \ldots, a_{n}$ and $b_{0}, \ldots, b_{n}$ are constructed by the following rules: $$\begin{gathered} a_{0}=b_{0}=1, \quad a_{1}=b_{1}=7, \\ a_{i+1}=\left\{\begin{array}{ll} 2 a_{i-1}+3 a_{i}, & \text { if } \varepsilon_{i}=0, \\ 3 a_{i-1}+a_{i}, & \text { if } \varepsilon_{i}=1, \end{array} \text { for each } i=1, \ldots, n-1,\right. \\ b_{i+1}=\left\{\begin{array}{ll} 2 b_{i-1}+3 b_{i}, & \text { if } \varepsilon_{n-i}=0, \\ 3 b_{i-1}+b_{i}, & \text { if } \varepsilon_{n-i}=1, \end{array} \text { for each } i=1, \ldots, n-1 .\right. \end{gathered}$$ Prove that $a_{n}=b_{n}$.

RUS 令$n$ 为正整数。给定序列 $\varepsilon_{1}, \ldots, \varepsilon_{n-1}$，其中 $\varepsilon_{i}=0$ 或 $\varepsilon_{i}=1$，对于每个 $i=1, \ldots, n-1$，构造序列 $a_{0}, \ldots, a_{n}$ 和 $b_{0}, \ldots, b_{n}$遵循以下规则： \begin{gathered} a_{0}=b_{0}=1, \quad a_{1}=b_{1}=7, \\ a_{i+1}=\left\{\begin{array}{ll} 2 a_{i-1}+3 a_{i}, & \text { if } \varepsilon_{i}=0, \\ 3 a_{i-1}+a_{i}, & \text { if } \varepsilon_{i}=1, \end{array} \text { 对于每个 } i=1, \ldots, n-1,\right。 \\ b_{i+1}=\left\{\begin{array}{ll} 2 b_{i-1}+3 b_{i}, & \text { if } \varepsilon_{n-i}=0, \\ 3 b_{i-1}+b_{i}, & \text { if } \varepsilon_{n-i}=1, \end{array} \text { 对于每个 } i=1, \ldots, n-1 .\右。 \end{聚集}证明$a_{n}=b_{n}$。