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 3 trên 4: Mảng kỳ diệu được xác định bởi mỗi loại tổng
Bước trướcBước tiếp
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}
Phân tích chi tiết

Gọi một mảng là kỳ diệu nếu các hàng của nó là bản sao canh trái của 2N−1,2N−2,…,2,12^{N-1},2^{N-2},\ldots,2,1 với các giá trị NN không tăng và độ dài hàng không tăng. Cho một dãy kiểu BB bất kỳ b1≥⋯≥bmb_1\ge\cdots\ge b_m, ta dựng một mảng kỳ diệu theo quy nạp: điền bmb_m hàng với 2m−1,…,2,12^{m-1},\ldots,2,1, rồi bm−1−2bmb_{m-1}-2b_m hàng nữa với 2m−2,…,2,12^{m-2},\ldots,2,1, và cứ thế cho đến b1−2b2b_1-2b_2 hàng chỉ chứa số 11; tổng theo cột của mảng này khôi phục chính xác b1,…,bmb_1,\ldots,b_m, và tổng theo hàng của nó là dãy kiểu AA tương ứng. Một mảng kỳ diệu được xác định duy nhất bởi tổng theo hàng (hiển nhiên, vì các hàng đọc trực tiếp ra) và, theo cách dựng quy nạp này, cũng duy nhất bởi tổng theo cột.