MathLabs

Bài 5

Cho một số nguyên N≥2N \ge 2. Có N(N+1)N(N+1) cầu thủ bóng đá, không ai có cùng chiều cao với ai khác, đứng thành một hàng. Ngài Alex muốn loại bỏ N(N−1)N(N-1) cầu thủ khỏi hàng này để còn lại một hàng mới gồm 2N2N cầu thủ sao cho NN điều kiện sau đây được thỏa mãn: không ai đứng giữa hai cầu thủ cao nhất, không ai đứng giữa cầu thủ cao thứ ba và cầu thủ cao thứ tư, …\ldots, không ai đứng giữa hai cầu thủ thấp nhất. Chứng minh rằng điều này luôn luôn thực hiện được.
Bước 1 trên 7: Quy bài toán về một phép quy nạp theo NN
Bước trướcBước tiếp
Hiểu nôm na

Vì việc loại bỏ cầu thủ có tính đơn điệu, chiến lược tự nhiên là tách ra một cặp liền kề mỗi lần rồi quy nạp trên một phiên bản nhỏ hơn của đúng bài toán đó.

N(N+1)=2N+N(N−1)N(N+1)=2N+N(N-1)
Phân tích chi tiết

Ta chứng minh bằng quy nạp mạnh theo NN rằng với mọi số nguyên N≥1N\ge 1, một hàng gồm N(N+1)N(N+1) cầu thủ có chiều cao đôi một khác nhau luôn cho phép loại bỏ N(N−1)N(N-1) người để còn lại 2N2N người sống sót mà các cặp thứ hạng chiều cao liên tiếp (2k−1,2k)(2k-1,2k) với k=1,…,Nk=1,\ldots,N đều đứng liền kề nhau trong hàng thu được; phạm vi N≥2N\ge 2 mà đề bài yêu cầu chỉ là một trường hợp riêng. Trường hợp cơ sở N=1N=1 không cần loại bỏ ai cả: chỉ có 22 cầu thủ, nên cặp duy nhất cần có hiển nhiên liền kề.