MathLabs

第3题

设 A(n)A(n) 表示满足 a1+⋯+ak=na_1+\cdots+a_k=n 且每个 ai+1a_i+1（i=1,2,…,ki=1,2,\ldots,k）都是二的幂的正整数数列 a1≥a2≥⋯≥aka_1\ge a_2\ge\cdots\ge a_k 的个数。设 B(n)B(n) 表示满足 b1+⋯+bm=nb_1+\cdots+b_m=n 且每个不等式 bj≥2bj+1b_j\ge2b_{j+1}（j=1,2,…,m−1j=1,2,\ldots,m-1）都成立的正整数数列 b1≥b2≥⋯≥bmb_1\ge b_2\ge\cdots\ge b_m 的个数。证明对每个正整数 nn 都有 A(n)=B(n)A(n)=B(n)。
第 3/4 步：「精妙」阵列由任一种和唯一确定
上一步下一步
marvelous array: rows 2N−1,…,2,1, N non-increasing, row lengths non-increasing\text{marvelous array: rows } 2^{N-1},\ldots,2,1,\ N \text{ non-increasing, row lengths non-increasing}
详细分析

称一个阵列为「精妙的」，如果它的各行是非增数 NN 对应的 2N−1,2N−2,…,2,12^{N-1},2^{N-2},\ldots,2,1 的左对齐副本，且各行长度不增。给定任意 BB 型数列 b1≥⋯≥bmb_1\ge\cdots\ge b_m，可归纳地构造一个精妙阵列：先用 2m−1,…,2,12^{m-1},\ldots,2,1 填 bmb_m 行，再用 2m−2,…,2,12^{m-2},\ldots,2,1 填 bm−1−2bmb_{m-1}-2b_m 行，如此继续，直到用元素 11 填 b1−2b2b_1-2b_2 行；该阵列的列和恰好还原出 b1,…,bmb_1,\ldots,b_m，其行和则是对应的 AA 型数列。精妙阵列由其行和唯一确定（这是显然的，因为可直接读出各行），而由这个归纳构造可知，它也同样由列和唯一确定。