綺麗で奇妙な3つの解法　ISL2009 C3

問題

ISL2009 C3

$n$を正の整数とする。$\epsilon_1,\cdots,\epsilon_{n-1}$は$0,1$のいずれかである。$a_0,a_1,\cdots,a_n,b_0,b_1,\cdots,b_n$を以下のように定める。
$$a_0=b_0=1,~~a_1=b_1=7$$
$i=1,2,\cdots,n-1$に対して
$$ a_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} 2a_{i-1}+3a_i~~~\mathrm{if}~ \epsilon_i=0\\ 3a_{i-1}+a_i~~~~~\mathrm{if}~\epsilon_i=1 \end{array} \right. \end{eqnarray} $$
$$ b_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} 2b_{i-1}+3b_i~~~\mathrm{if}~ \epsilon_{n-i}=0\\ 3b_{i-1}+b_i~~~~~\mathrm{if}~\epsilon_{n-i}=1 \end{array} \right. \end{eqnarray} $$
このとき$a_n=b_n$を示せ。

AoPSを漁っていたところ面白い解法を見つけたので紹介します。 IMO Shortlist 2009 - Problem C3

解法１　14色のペンキとn個の部屋

$A_n=2^na_n,B_n=2^nb_n$と定めると、$A_0=B_0=1,A_1=B_1=14,$
$$A_{i+1}\in \lbrace 8A_{i-1} +6A_i,12A_{i-1}+2A_i\rbrace $$
である。

ここで上のようなつながった部屋と壁を考える。左から壁$1,2,\cdots,n-1$、部屋$1,2,\cdots,n$であり壁にはそれぞれ$\epsilon_i$、すなわち$0,1$のいずれかがラベリングされている。この壁を色$1,2,\cdots,13$と色$X$を用いて、以下の任意の壁に対して成り立つ規則に則って壁をペンキで塗ることを考える。ただし、部屋は一色で塗られている。

壁の両面の色を$i,j$とする。
・$i,j \neq X$のとき
壁に$0$がラベリングされてるとき
$$i-j \equiv -2,-1,0,1,2 \pmod{13} $$
壁に$1$がラベリングされてるとき
$$i=j$$
である。
・$i=X$または$j=X$のとき
規則を与えない。

このとき、部屋$1,\cdots,i$のみを塗る塗り方の通り数は$A_i$である。また部屋$n-i+1,\cdots,n$のみを塗る塗り方の通り数は$B_i$である。
これを示す。$A_i$のみを考える。
部屋$i+1$を新たに塗るときを考える。部屋$1$を新たに塗るとき、塗り方は$ A_1=14$通りである。$i \geq 1$で考える。
・$\epsilon_i=0$のとき
部屋$i$の色が$X$でないならば、規則より$X$を含めた$6$色でしか部屋$i+1$を塗ることができない。このとき、色の塗り方は$6(A_i-A_{i-1})$通りである。部屋$i$の色が$X$ならば、$14$色で部屋$i+1$を塗ることができる。このとき、色の塗り方は$14A_{i-1}$通りである。よって、$A_{i+1}=6(A_i-A_{i-1})+14A_{i-1}=6A_i+8A_{i-1}$を得る。
・$\epsilon_i=1$のとき
同様に考えることで、$A_{i+1}=2(A_i-A_{i-1})+14A_{i-1}=2A_i+12A_{i-1}$を得る。
　よって示された。
明らかに$A_n=B_n$が成り立つので$a_n=b_n$となり示された。

解法２　多変数多項式

$n-1$変数多項式$F_n$を以下のように定める。
$$ F_0=1,F_1=7$$
$$F_{i+1}(x_1,\cdots,x_i)=(2+x_{i})F_{i-1}(x_1,\cdots,x_{i-2})+(3-2x_i)F_i(x_1,\cdots,x_{i-1})~~\cdots(\ast)$$
このとき、
$$a_n=F_n(\epsilon_1,\cdots,\epsilon_{n-1}),~~b_n=F_n(\epsilon_{n-1},\cdots,\epsilon_{1})$$
である。特に任意の$n-1$個の実数$x_1,\cdots,x_{n-1}$に対して
$$F_{n}(x_1,\cdots,x_{n-1})=F_{n}(x_{n-1},\cdots,x_{1})$$
を示せば十分である。ここで以下の補題を示す。

$s,t$を相異なる実数とし$P$を$n$変数多項式とする。各変数$x_i$に対し、$x_i$を変数、それ以外の変数を定数とみなしたとき次数は$1$以下であるという。各$i$に対し$\alpha_i\in \lbrace s,t \rbrace$が成り立つすべての実数の組に対して$P(\alpha_1,\cdots,\alpha_n)=0$が成り立つとき、$P$は恒等的に$0$である。

$n$についての帰納法で示す。
$n=1$のときは明らかである。条件より、
$$P=x_nQ+R$$
を満たす$n-1$変数多項式$Q,R$が存在する。このとき
$$0=P(\alpha_1,\cdots,\alpha_{n-1},s)=sQ(\alpha_1,\cdots,\alpha_{n-1})+R(\alpha_1,\cdots,\alpha_{n-1})$$
$$0=P(\alpha_1,\cdots,\alpha_{n-1},t)=tQ(\alpha_1,\cdots,\alpha_{n-1})+R(\alpha_1,\cdots,\alpha_{n-1})$$
がなりたつため、$s \neq t$より
$$Q(\alpha_1,\cdots,\alpha_{n-1})=R(\alpha_1,\cdots,\alpha_{n-1})=0$$
帰納法の仮定より、$Q,R$は恒等的に$0$であるから$P$も恒等的に$0$である。

$$ P(x_1,\cdots,x_{n-1})=F_n(x_1,\cdots,x_{n-1})-F_{n}(x_{n-1},\cdots,x_{1})$$と定めると、この$P$は補題の条件を満たすので$\delta_i\in\lbrace-2,\dfrac 3 2\rbrace$を満たす任意の$n-1$個の組において
$$ F_n(\delta_1,\cdots,\delta_{n-1})=F_{n}(\delta_{n-1},\cdots, \delta_{1})$$
が成り立つことを示せば十分である。
$$c_i=F_i(\delta_1,\cdots,\delta_{i-1})~~~~i=1,\cdots,n$$
$$d_i=F_i(\delta_{i-1},\cdots,\delta_{1})~~~~i=1,\cdots,n$$
と定めると、$(\ast)$より
$$ \delta_i=-2 \Longrightarrow c_{i+1}=7c_i,~~~~ \delta_i=\dfrac 3 2 \Longrightarrow c_{i+1}=\dfrac 7 2 c_{i-1}$$
$$ \delta_{n-i}=-2 \Longrightarrow d_{i+1}=7d_i,~~~~ \delta_{n-i}=\dfrac 3 2 \Longrightarrow d_{i+1}=\dfrac 7 2 d_{i-1}$$
よってこの問題は以下の問題に置き換えられる。

$\delta_1,\cdots,\delta_{n-1}$は$-2,\dfrac 3 2$のいずれかである。
$$c_0=d_0=1,~~c_1=d_1=7$$
$i=1,2,\cdots,n-1$に対して
$$ c_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} 7c_i~~~~~~~\mathrm{if}~ \delta_i=-2\\ \dfrac 7 2 c_{i-1}~~\mathrm{if}~\delta_i=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
$$ d_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} 7d_i~~~~~~~\mathrm{if}~ \delta_{n-i}=-2\\ \dfrac 7 2 d_{i-1}~~\mathrm{if}~\delta_{n-i}=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
このとき$c_n=d_n$を示せ。

$c_i$は整数$e_i,f_i$を用いて
$$c_i=\dfrac {7^{e_i}}{2^{f_i}}$$
と表せる。このとき、$e_0=f_0=0,e_1=1,f_1=0$
$$ e_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} e_i+1~~~~~\mathrm{if}~ \delta_i=-2\\ e_{i-1}+1~~\mathrm{if}~\delta_i=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
$$ f_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} f_i~~~~~~~~~~~~\mathrm{if}~ \delta_{i}=-2\\ f_{i-1}+1~~\mathrm{if}~\delta_{i}=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
このふたつの数列を含む以下の数列を考えればよい。
$$ g_0=0,g_1=u \neq \dfrac 1 2$$
$$ g_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} g_i+u~~~~~\mathrm{if}~ \delta_i=-2\\ g_{i-1}+1~~\mathrm{if}~\delta_i=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
$(-2u+1)p_i=g_i-iu,~$とおき、$\delta_i$を逆順にしたものを$q_i$とする。以下の問題を示せばよい。

$\delta_1,\cdots,\delta_{n-1}$は$-2,\dfrac 3 2$のいずれかであり、
$$p_0=q_0=p_1=q_1=0$$
$i=1,2,\cdots,n-1$に対して
$$ p_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} p_i~~~~~~~~~~~~\mathrm{if}~ \delta_i=-2\\ p_{i-1}+1~~\mathrm{if}~\delta_i=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
$$ q_{i+1}= \begin{eqnarray} \left\{ \begin{array}{l} q_i~~~~~~~~~~~~~\mathrm{if}~ \delta_{n-i}=-2\\ q_{i-1}+1~~~\mathrm{if}~\delta_{n-i}=\dfrac 3 2 \end{array} \right. \end{eqnarray} $$
このとき$p_n=q_n$を示せ。

$r_i=p_i-p_{i-1}$とし、$\delta_m=\cdots=\delta_{m+k-1}=\dfrac 3 2,\delta_{m-1}=\delta_{m+k}=-2$となるとき、
$$r_{i+1}+r_i=1~~~i=m,\cdots,m+k-1$$
かつ$r_m=0$であるから、$r_{m+1},\cdots,r_{m+k}$は$1,0,1,0,\cdots$となる。よって、
$$ \sum_{i=m+1}^{m+k}r_i= \bigg\lbrack \frac {k+1} 2 \bigg\rbrack $$
また、$\delta_m=\cdots=\delta_{m+k-1}=-2$のとき
$$ \sum_{i=m+1}^{m+k}r_i=0 $$
であるから、$\delta=\dfrac 3 2$の連続する長さ（上でいう$k$）を添え字の小さい順から、$k_1,\cdots,k_l$とすると
$$p_n=p_1+ \sum_{i=2}^{n} r_i= \sum_{i=1}^{l} \bigg\lbrack \frac {k_i+1} 2 \bigg\rbrack $$
$(\delta_1,\cdots,\delta_{n-1})\rightarrow (\delta_{n-1},\cdots,\delta_{1})$としたとき、$k_i$の定め方から$k_i\rightarrow k_{l+1-i}$に変化するだけなので$p_n=q_n$が示された。

解法３　行列と写像

$A= \begin{eqnarray} \left( \begin{array}{cc} 3 & 2 \\ 1 & 0 \end{array} \right) \end{eqnarray},~ $ $B= \begin{eqnarray} \left( \begin{array}{cc} 1 & 3 \\ 1 & 0 \end{array} \right) \end{eqnarray}$と定め、$K_i=(1-\epsilon_i)A+\epsilon_iB$とすると、
$$ \begin{pmatrix} a_{i+1} \\ a_{i} \end{pmatrix} =K_i \begin{pmatrix} a_i \\ a_{i-1} \end{pmatrix}$$
となるので帰納的に
$$ \begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix} =K_{n-1}\cdots K_1 \begin{pmatrix} a_2 \\ a_{1} \end{pmatrix}=K_{n-1}\cdots K_1 \begin{pmatrix} 7 \\ 1 \end{pmatrix}$$
$$\therefore a_n=\begin{pmatrix} 1 & 0 \end{pmatrix}K_{n-1}\cdots K_1 \begin{pmatrix} 7 \\ 1 \end{pmatrix}$$
同様の計算から
$$ b_n=\begin{pmatrix} 1 & 0 \end{pmatrix}K_{1}\cdots K_{n-1} \begin{pmatrix} 7 \\ 1 \end{pmatrix}$$
$~$
ここで$f:M_2( \mathbb{R} )\rightarrow M_2( \mathbb{R} )$
$$f(P)=UP^{ {\mathrm{T}} }U^{-1}~~~~~U= \begin{pmatrix} 7 & 1 \\ 1 & 2 \end{pmatrix} $$
と定めると以下の3つが成り立つ。

$１,f(A)=A,f(B)=B$

$２,$任意の$X,Y\in M_2(\mathbb R)$に対して$f(XY)=f(Y)f(X)$

$３,$任意の$P\in M_2(\mathbb R)$に対して$\begin{pmatrix} 1 & 0 \end{pmatrix}P \begin{pmatrix} 7 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 \end{pmatrix}f(P) \begin{pmatrix} 7 \\ 1 \end{pmatrix} $

$１$

計算するだけなので省略。

$２$

$$f(XY)=U(XY)^{\mathrm T}U^{-1}=UY^{\mathrm T}X^{\mathrm T}U^{-1}=(UY^{\mathrm T}U^{-1})(UX^{\mathrm T}U^{-1})=f(Y)f(X)$$

$３ $

両辺がスカラーであることより転置しても変わらないことに注意する。
$$\begin{pmatrix} 1 & 0 \end{pmatrix}f(P) \begin{pmatrix} 7 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 \end{pmatrix}UP^{\mathrm T} U^{-1}\begin{pmatrix} 7 \\ 1 \end{pmatrix}=\begin{pmatrix} 7 & 1 \end{pmatrix}P^{\mathrm T}\begin{pmatrix} 1 \\ 0 \end{pmatrix}=\begin{pmatrix} 1 \\ 0 \end{pmatrix}^{\mathrm T}P\begin{pmatrix} 7 & 1 \end{pmatrix}^{\mathrm T}=\begin{pmatrix} 1 & 0 \end{pmatrix}P \begin{pmatrix} 7 \\ 1 \end{pmatrix}$$

$３$に$P=K_{n-1}\cdots K_1$を代入すると
$$\begin{pmatrix} 1 & 0 \end{pmatrix}K_{n-1}\cdots K_1 \begin{pmatrix} 7 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 \end{pmatrix}f(K_{n-1}\cdots K_1 )\begin{pmatrix} 7 \\ 1 \end{pmatrix} $$
$$\therefore\begin{pmatrix} 1 & 0 \end{pmatrix}K_{n-1}\cdots K_1 \begin{pmatrix} 7 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 \end{pmatrix}f(K_1)\cdots f(K_{n-1})\begin{pmatrix} 7 \\ 1 \end{pmatrix} ~~~~(\because ２)$$
$$\therefore\begin{pmatrix} 1 & 0 \end{pmatrix}K_{n-1}\cdots K_1 \begin{pmatrix} 7 \\ 1 \end{pmatrix}=\begin{pmatrix} 1 & 0 \end{pmatrix}K_1\cdots K_{n-1}\begin{pmatrix} 7 \\ 1 \end{pmatrix} ~~~~(\because １)$$
$$\therefore a_n=b_n$$
よって示された。

投稿日：15時間前

更新日：15時間前