Cho 2n+1 số nguyên , trong đó có đúng một số 0 và các số 1,2,3,...,n mỗi số xuất hiện 2 lần. CMR với mọi số tự nhiên n ta luôn sắp xếp được 2n+1 số nguyên trên thành 1 dãy sao cho với mọi m=1,2,...,n có đúng m số nằm giữa hai số m
Quảng cáo
1 câu trả lời 393
Ta nhận xét rằng với hai tập, mỗi tập có các số lẻ từ 1 đến 2k + 1, ta có thể sắp xếp sao cho thỏa mãn yêu cầu bài toán với một ô trống giữa gồm 2k + 1; 2k – 1;…; 3; 1; (ô trống); 3;…; 2k – 1; 2k + 1.
Với hai tập, mỗi tập gồm các số chẵn từ 2 đến 2k + 2, ta có thể sắp xếp sao cho thỏa mãn yêu cầu bài toán với hai ô trống giữa gồm 2k; 2k – 2;…; 4; 2; (ô trống 1); (ô trống 2); 2; 4;,….; 2k – 2; 2k.
Xét 2 trường hợp:
Với n = 2k + 1 ta sắp xếp sau là thỏa mãn bài toán :
2k + 1; 2k – 1;………, 3; 1; 2k; 1; 3;……..; 2k – 1; 2k + 1; 2k – 2; 2k – 4;….; 4; 2; 2k; 0; 2; 4;……; 2k – 2.
Với n = 2k ta sắp xếp như sau sẽ thỏa mãn bài toán:
2k – 1; 2k – 3;….; 3; 1; 2k; 1; 3; ….; 2k – 3; 2k – 1; 2k – 2; 2k – 4; ….; 4; 2; 0; 2k; 2; 4; ….; 2k – 4; 2k – 2.
Vậy ta có điều phải chứng minh.
Quảng cáo
Bạn muốn hỏi bài tập?
Câu hỏi hot cùng chủ đề
-
13666
-
13599
-
6085
-
5432
-
4446
