Đề bài:(bài V,đề thi hsg toán tp Hà Nội,2017):
Gọi các số k là loại n với $n \in \{1;2;3\}$ nếu $k=0$ hoặc k là phần tử của dãy $(n+2)^a$ hoặc k là tổng một số phần tử của dãy trên(chú ý là phân biệt).CMR:Mọi số nguyên dương đều viết được dưới dạng tổng của một số loại 1,một số loại 2 và một số loại 3.
Dựa trên lời giả của nhóm các thầy,bài toán là hệ quả trực tiếp của bổ đề sau:
Cho dãy số nguyên dương $a_n$,$a_0$=1 và $a_n <=a_0+a_1+...+a_{n-1}$
CMR:mọi số tự nhiên đều biểu diễn được dưới dạng tổng của các số $a_k$ phân biệt
Bổ đề trên có thể chứng minh dễ dàng bằng phương pháp quy nạp mạnh,và từ đó ta có thể áp dụng vào bài toán với dãy $a_{3k}=3^k,a_{3k+1}=4^k,a_{3k+2}=5^k$
Thế nhưng với không phải ai cũng biết bổ đề trên (kể cả tác giả bài viết này),nên tác giả đưa ra một lời giải khác,và sẽ nhắc đến việc sử dụng thuật toán:
Lời giải:
Xét quá trình sau:
(A):Với số nguyên dương n,gọi k là số tự nhiên thỏa:$3^{k+1}>n>=3^k$,đặt $n_1=n-3^k$
tương tự ta có $4^{t+1}>n_1>=4^t$,đặt $n_2=n_1-4^t$, và $5^{s+1}>n_2>=5^s$,$n_3=n_2-5^s$
Nếu $n_3<3^k$,ta có thể tiếp tục (A),ngược lại thực hiện (B):
(B):Xét $n_4=n-3^k-5^{s+1}$,nếu $n_4<0$ thì số $n-5^{s+1}$ thỏa,còn $n_4$>0 thì số $n_4$ thỏa
Ta sẽ chứng minh thuật toán trên đúng:
Giả sử (A) dừng ở một điểm nào đó.Khi đó ta có:
$2.3^k+4^t+5^s=<n<min\{3^k+4^t+5^{s+1};3^k+4^{t+1};3^{k+1}\}$
=>$4^t+5^s<3^k;3^k+5^s<3.4^t;3^k<4.5^s$
Nếu $4^t=<5^s$ thì $3^k<24^t$ và từ đây có vô lí
vậy $4^t>5^s$ và ta có $n>2.3^k+4^t+5^s>2(4^t+5^s)+5^s>5^{s+1}$,tới đây xét $a=n-3^k-5^{s+1}$
Nếu a>0 thì số $n-5^{s+1}$,ngược lại thì $a<2.3^k-3^k-3^k=3^k$,đúng
Vậy thuật toán luôn chạy và giảm n.
Không có nhận xét nào:
Đăng nhận xét