JMO2006予選12
まえがき
aogera と一緒にJMO予選2006-12を解いていたらかなり激ヤバな方法で解けたので紹介します．一緒に解説を執筆してくれたaogera,校閲をしてくれた rapca に感謝します．
$20$個の正整数の組$(p_1, p_2, \cdots, p_{10}, q_1, q_2, \cdots, q_{10})$であって，$p_1 = q_{10} = 1$を満たし，かつ各$i = 1, 2, \cdots, 9$について$p_{i+1}q_i-p_iq_{i+1} = 1$が成り立つものはいくつあるか．
<ネタバレ防止用スペース>
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
$\space\\$
お気持ち
・$p_{i+1}q_i-p_iq_{i+1}=1$という条件が、ファレイ数列を思い起こさせる．
・ファレイ数列をうまく扱うために，試行錯誤するとStern–Brocot木に行き着く．
・考察を進めると経路に帰着でき，カタラン数になる！！
有理数列であって，$i$項目を既約分数で$F_i=\dfrac{p_i}{q_i}$と表したときに，任意の正整数$i$について
$$p_{i+1}q_i-p_iq_{i+1}=1$$
が成立するものを類似ファレイ数列と呼ぶ．
一般のファレイ数列の定義はこれとは全く異なりますが，ファレイ数列の性質として
$$p_{i+1}q_i-p_iq_{i+1}=1$$
があるのでこれを本記事では便宜的に類似ファレイ数列と呼ぶことにしています．
次のように定められる完全二分木をStern-Brocot木と呼ぶ．
・各頂点には非負整数の$4$つ組$(a,b,c,d)$が対応し，その頂点の値は$\dfrac{a+c}{b+d}$である．
・各頂点について，親が$(a,b,c,d)$に対応するとき，左の子は$(a,b,a+c,b+d)$，右の子は $(a+c,b+d,c,d)$が対応する．
・根に対応する$4$つ組は$(0,1,1,0)$である．
Stern-Brocot木
解説
$r_i=\dfrac{p_i}{q_i}$とする．$\gcd(p_i,q_i)=d$とすると，$d \mid p_{i+1}q_i-p_iq_{i+1}=1$となるから，$d = 1$であり，$r_i$は既約分数である．
次のように「操作」を定義する．
操作$1$: Stern-Brocot木上で，ある点から，左に親がいる限り左の親に上り，そうでないとき右の親に$1$回だけ上る．
操作$2$: Stern-Brocot木上で，ある点から，$1$回だけ右の子へ下り，左の子へ好きなだけ下る．
主張:$\{r_i\}$が問題の条件を満たすことと，$i$=$1,2,\cdots,9$で$r_i$から$r_{i+1}$に一回の操作でたどり着けることは同値である.
Stern-Brocot木の性質で，根を深さ$0$としたとき，任意の正整数$k$について，根から深さ$k$までの頂点のラベルを左から右まで順番に並べた数列は，類似ファレイ数列となる．
たとえば，$k=3$とすると$\dfrac14,\dfrac25,\dfrac35,\dfrac34,\dfrac43,\dfrac53,\dfrac52,\dfrac41$となり確かに類似ファレイ数列となっている．
二分木の性質により，頂点$u$から操作によってたどり着ける頂点は，ある深さまでの頂点を左から右まで順番に並べた数列の中で頂点$u$のちょうどひとつ右になる．
類似ファレイ数列の定義から，$r_{i+1}$が$r_i$から操作によってたどり着ける時，$p_{i+1}q_i-p_iq_{i+1}=1$となるため，条件を満たす．
逆を示す．
Stern-Brocot木の特徴で，任意の整数$k$について「根から深さ$k$までの頂点を左から右へ順番に並べた数列の中で隣り合う$u,v$(($u$の深さ)<($v$の深さ))について，$v$の子のうち頂点$u$側のもののラベルは，$u$のラベルを$\frac{u_1}{u_2}$,$v$のラベルを$\frac{v_1}{v_2}$とすれば，$\frac{u_1+v_1}{u_2+v_2}$」というものがある．
$p_i,q_i$を固定した時，$p_{i+1},q_{i+1}$は次の一次不定方程式の解となる．
$$p_{i+1}q_i-p_iq_{i+1}=1$$
したがって，整数$a,b,m,n$を用いて$p_{i+1}=a+mp_i$, $q_{i+1}=b+nq_i$のようにかける．
$r_i$から操作1でたどり着ける頂点は，類似ファレイ数列で隣り合うので先程の一次不定方程式を満たす．また，この頂点の深さは，$r_i$の頂点の深さより小さいので，この頂点のラベルの分子と分母は一次不定方程式の正整数解のうち最小のものである．したがって，すべての正整数解の組は，$r_i$から操作1でたどりつける頂点のラベルの分子と分母にそれぞれ$p_i$,$q_i$を$0$回以上足したものに限られる．これは，操作2でたどり着ける頂点であることが，Stern-Brocot木の特徴によってわかる．したがって示された．(証明終)
したがって，分数の書き込みは忘れることができ，問題は次のように言い換えられる．
「無限に続く完全二分木がある．これは，根がラベル$1$の頂点となる木で，ラベル$i$の頂点の左の子はラベル$2i$，右の子はラベル$2i+1$とする．このとき，$9$回の操作で，ある正整数$k$を用いて$2^k$と表されるラベルを持つ頂点から，ある正整数$l$を用いて$2^l - 1$と表されるラベルを持つ頂点まで移動する経路はいくつあるか」
頂点のラベルを二進数で表すことにする．
「左の子に下る」は二進数で末尾に$0$を追加することに，
「右の子に下る」は二進数で末尾に$1$を追加することに，
「左の親に上る」は二進数の末尾の$1$を削除することに，
「右の親に上る」は二進数で末尾の$0$を削除することに対応する．
二進数の末尾が$1$でないとき，「左の親に上る」ことはできず，
二進数の末尾が$0$でないとき，「右の親に上る」ことはできないことに注意する．
さて操作$1$によって，二進数の$0$の個数はちょうど$1$つ減る．
操作$2$によって，二進数の$0$の個数は$0$以上増える．
$p_1 = q_{10} = 1$より，始点の二進数の$0$の個数は$0$以上．終点の二進数の$0$の個数は$0$になる．
また，二進数の$0$の個数はつねに非負であることに注意すると，二進数の$0$の個数に着目した数列を考えることで問題はさらに言い換えられる．
「非負整数列$a_1,a_2,\dots a_{10}$であって，$1$以上$9$以下の全ての整数$i$で$a_{i+1}-a_i \ge -1$で，$a_{10}=0$となるものはいくつ存在するか」
ここで，$b_n = a_n + n$とおくと，
「広義単調増加する正整数列$b_1,b_2,\dots b_{10}$であって，$1$以上$9$以下の全ての整数$i$について$b_i \ge i$で，$b_{10}=10$となるものはいくつ存在するか」
という問題に帰着できる．
この問題の答えは，カタラン数の$10$項目に等しい．
よって，答えは，$C_{10}=16796$である．
(加筆予定あり)
この記事を高評価した人
この記事に送られたバッジ
投稿者
