第3問

A(n)

を、

a_1+\cdots+a_k=n

かつ各

a_i+1

（

i=1,2,\ldots,k

）が二のべきであるような正整数の数列

a_1\ge a_2\ge\cdots\ge a_k

の個数とする。

B(n)

を、

b_1+\cdots+b_m=n

かつ各不等式

b_j\ge2b_{j+1}

（

j=1,2,\ldots,m-1

）が成り立つような正整数の数列

b_1\ge b_2\ge\cdots\ge b_m

の個数とする。すべての正整数

n

に対して

A(n)=B(n)

であることを証明せよ。

ステップ 3/4: 「見事な」配列はどちらの和からも一意に定まる

前のステップ次のステップ

\text{marvelous array: rows } 2^{N-1},\ldots,2,1,\ N \text{ non-increasing, row lengths non-increasing}

詳しい解説

配列が「見事」であるとは、その行が非増加な $N$ に対する $2^{N-1},2^{N-2},\ldots,2,1$ の左揃えの複製であり、行の長さも非増加であることをいう。任意の型 $B$ の数列 $b_1\ge\cdots\ge b_m$ が与えられたとき、帰納的に見事な配列を作る： $b_m$ 個の行を $2^{m-1},\ldots,2,1$ で埋め、次に $b_{m-1}-2b_m$ 個の行を $2^{m-2},\ldots,2,1$ で埋め、以下同様にして $b_1-2b_2$ 個の行を要素 $1$ だけで埋める。この配列の列和はちょうど $b_1,\ldots,b_m$ を復元し、その行和は対応する型 $A$ の数列である。見事な配列はその行和によって（行を直接読み取れるので明らかに）一意に定まり、この帰納的構成により列和によっても等しく一意に定まる。