Math Labs

Bài 6

Cho a1,…,ana_1,\ldots,a_n là các số nguyên dương đôi một khác nhau và MM là một tập gồm n−1n-1 số nguyên dương không chứa s=a1+⋯+ans=a_1+\cdots+a_n. Một con châu chấu bắt đầu ở 00 và thực hiện nn lần nhảy sang phải, với độ dài a1,…,ana_1,\ldots,a_n theo một thứ tự nào đó. Chứng minh rằng có thể chọn thứ tự để châu chấu không bao giờ đáp xuống một điểm thuộc MM.
Bước 1 trên 5: Tăng cường mệnh đề quy nạp và đặt ký hiệu
Bước trướcBước tiếp
Hiểu nôm na

Bước nhảy dài nhất là bước cuối tự nhiên. Điểm ngay trước bước đó là mốc then chốt.

a1<⋯<an,s=a1+⋯+an,x=s−ana_1<\cdots<a_n,\quad s=a_1+\cdots+a_n,\quad x=s-a_n
Phân tích chi tiết

Ta chứng minh bằng quy nạp theo nn mệnh đề mạnh hơn một chút: với mọi tập gồm không quá n−1n-1 điểm cấm dương mà tổng ss không bị cấm, có thể sắp thứ tự các bước nhảy an toàn. Sắp các độ dài thành a1<⋯<ana_1<\cdots<a_n, viết s=a1+⋯+ans=a_1+\cdots+a_n, và đặt x=s−anx=s-a_n. Trường hợp n=1n=1 là hiển nhiên.