MathLabs

Bài 3

Gọi A(n)A(n) là số dãy a1≥a2≥⋯≥aka_1\ge a_2\ge\cdots\ge a_k các số nguyên dương sao cho a1+⋯+ak=na_1+\cdots+a_k=n và mỗi ai+1a_i+1 là một lũy thừa của hai (i=1,2,…,ki=1,2,\ldots,k). Gọi B(n)B(n) là số dãy b1≥b2≥⋯≥bmb_1\ge b_2\ge\cdots\ge b_m các số nguyên dương sao cho b1+⋯+bm=nb_1+\cdots+b_m=n và mỗi bất đẳng thức bj≥2bj+1b_j\ge2b_{j+1} đúng (j=1,2,…,m−1j=1,2,\ldots,m-1). Chứng minh rằng A(n)=B(n)A(n)=B(n) với mọi số nguyên dương nn.
Bước 2 trên 4: Tổng theo cột tạo một dãy kiểu BB
Bước trướcBước tiếp
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}
Phân tích chi tiết

Gọi bjb_j là tổng các phần tử ở cột jj của mảng này. Mỗi cột có nhiều phần tử ít nhất bằng cột bên phải nó, và mỗi phần tử lớn hơn 11 đều bằng đúng hai lần phần tử bên phải nó trên cùng hàng, nên bj≥2bj+1b_j\ge2b_{j+1}: dãy thu được là kiểu BB. Vì cả a1+⋯+aka_1+\cdots+a_k lẫn b1+⋯+bmb_1+\cdots+b_m đều bằng tổng tất cả các phần tử của mảng, dãy (bj)(b_j) cũng có tổng bằng nn.