SẮP THỨ TỰ N + 1 SỐ ĐÃ CHO 1≤A1 <A2 <...<AN+1 <2N(...
Bài 16. Sắp thứ tự n + 1 số đã cho
1
≤
a
1
<
a
2
<
...
<
a
n
+
1
<
2
n
( Nhĩm 1). Xét thêm n số:
b
=
−
=
−
n
=
n
+
−
. Ta cĩ: 1
≤
b
1
<
b
2
<
...
<
b
n
<
2
n
(Nhĩm 2).
1
a
a
;
b
a
a
;...;
b
a
a
2
1
3
Tập 2n số của cả 2 nhĩm trên ( trừ
a
1
của nhĩm 1) nhận 2n -1 giá trị ( chuồng).
Theo nguyên lý Dirichlet cĩ 2 số bằng nhau nhưng khơng cùng một nhĩm 1 hoặc
nhĩm 2 tức là phải thuộc 2 nhĩm. Từ đĩ suy ra điều phải chứng minh!