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)。
第 2/4 步：列和构成一个 BB 型数列
上一步下一步
bj=∑i(entry in column j of row i)  ⟹  bj≥2bj+1b_j=\sum_i(\text{entry in column } j \text{ of row } i) \implies b_j\ge2b_{j+1}
详细分析

设 bjb_j 为该阵列第 jj 列所有元素之和。每一列的元素个数都不少于其右侧列，且同一行中大于 11 的每个元素恰好是其右侧元素的两倍，故 bj≥2bj+1b_j\ge2b_{j+1}：所得数列为 BB 型。由于 a1+⋯+aka_1+\cdots+a_k 与 b1+⋯+bmb_1+\cdots+b_m 都等于阵列全部元素之和，数列 (bj)(b_j) 的和也是 nn。