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 4 trên 4: Kết luận song ánh
A(n)=B(n)A(n)=B(n)
Phân tích chi tiết

Ánh xạ tổng-hàng (từ kiểu AA sang kiểu BB, qua việc đọc tổng theo cột của mảng dựng từ các hàng) và ánh xạ tổng-cột (từ kiểu BB sang kiểu AA, qua việc đọc tổng theo hàng của mảng kỳ diệu dựng từ các cột) là nghịch đảo của nhau, vì một mảng kỳ diệu được khôi phục duy nhất từ tổng theo hàng hoặc tổng theo cột của nó. Do đó hai ánh xạ này cho một song ánh giữa các dãy kiểu AA có tổng nn và các dãy kiểu BB có tổng nn, nên A(n)=B(n)A(n)=B(n) với mọi số nguyên dương nn.