ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN - CƠ - TIN HỌC
ĐÀO THỊ KIM OANH
NGUYÊN LÝ DIRICHLET
TRONG CÁC BÀI TOÁN SƠ CẤP
LUẬN VĂN THẠC SĨ TOÁN HỌC
Hà Nội - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA TOÁN - CƠ - TIN HỌC
ĐÀO THỊ KIM OANH
NGUYÊN LÝ DIRICHLET
TRONG CÁC BÀI TOÁN SƠ CẤP
Chuyên ngành: Phương pháp Toán sơ cấp
Mã số: 60 46 40
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học: PGS. TS PHAN HUY KHẢI
Hà Nội - 2011
1
Mục lục
1 Một số kiến thức chuẩn bị 4
1.1 Nguyên lý Dirichlet cơ bản . . . . . . . . . . . . . . . . . . . 4
1.2 Nguyên lý Dirichlet mở rộng . . . . . . . . . . . . . . . . . . . 4
1.3 Nguyên lý Dirichlet mở rộng cho tập hữu hạn . . . . . . . . . 4
1.4 Nguyên lý Dirichlet đối với tập vô hạn phần tử . . . . . . . . 6
1.4.1 Tập phần tử là một khoảng trên đường thẳng . . . . . 6
1.4.2 Tập phần tử là miền phẳng giới hạn bởi một đường
cong phẳng khép kín . . . . . . . . . . . . . . . . . . 9
1.4.3 Tập phần tử là khối ba chiều giới hạn bởi các mặt cong
phẳng . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Đào Thị Kim Oanh
3
MỞ ĐẦU
Nguyên lý Dirichlet được phát biểu lần đầu tiên bởi nhà toán học người
Pháp P. L. Dirichlet (1805 − 1859) như sau:
"Nếu nhốt n + 1 chú thỏ được nhốt vào n chuồng thì bao giờ cũng có 2 con
thỏ bị nhốt vào cùng một chuồng".
Tổng quát hơn nếu nhốt n chú thỏ vào k lồng mà phép chia
n
k
được m
còn dư thì tồn tại một lồng chứa m + 1 chú thỏ trở lên.
Nguyên lý Dirichlet là một dạng của phương pháp phản chứng, nó khẳng
định sự tồn tại hoặc không tồn tại của một sự kiện nào đó. Mặc dù đơn giản
nhưng nguyên lý Dirichlet được áp dụng như một công cụ hết sức hiệu quả
để giải nhiều bài toán phức tạp trong số học, hình học tổ hợp và trong nhiều
bài toán khác của toán học. Chính vì vậy, từ rất lâu tại các cuộc thi học sinh
giỏi toán quốc gia và quốc tế, nguyên lý Dirichlet thường xuyên được khai
thác. Tuy nhiên kiến thức về phần này lại không được viết nhiều trong các
sách cơ bản và đối với hầu hết giáo viên, học sinh phổ thông thì đây vẫn là
vấn đề mới mẻ. Vì vậy tôi hy vọng luận văn sẽ là một tài liệu tham khảo nhỏ
giúp ích cho các bạn học sinh trong quá trình học tập cũng như các thầy cô
trong quá trình giảng dạy.
Luận văn này nhằm mục đích tìm hiểu và làm sáng tỏ những áp dụng
của nguyên lý Dirichlet trong những bài toán sơ cấp.
Luận văn gồm bốn chương :
Chương 1. Một số kiến thức chuẩn bị .
Chương 2. Nguyên lý Dirichlet trong các bài toán số học.
Chương 3. Nguyên lý Dirichlet trong các bài toán hình học tổ hợp.
Chương 4. Nguyên lý Dirichlet trong các bài toán khác.
tại ít nhất 2 phần tử của A mà tương ứng với cùng một phần tử của B.
Định lý 4. Nếu A,B là các tập hợp hữu hạn và |A| > k|B| ở đây k là một
số tự nhiên nào đó và nếu mỗi phần tử của A tương ứng với một phần tử
nào đó của B thì tồn tại ít nhất k + 1 phần tử của A mà chúng tương ứng
với cùng một phần tử của B.
Chứng minh. k = 1 hiển nhiên đúng.
Để chứng minh mệnh đề trên chúng ta giả sử mỗi phần tử của B chỉ
tương ứng với nhiều nhất k phần tử của A. Khi đó |A| ≤ k|B| trái với giả
thiết |A| > k|B|.
Định lý 5. (Nguyên lý Dirichlet cho tập hữu hạn)
Cho tập hữu hạn S = ∅ và S
1
, S
2
, S
3
, , S
n
là các tập con của S sao cho
|S
1
| + |S
2
| + + |S
n
| > k.|S|. Khi đó tồn tại một phần tử x ∈ S sao cho x
là phần tử chung của k + 1 tập S
i
với i = 1, 2, , n.
Định lý 6. Định lý tương đương
) được phân vào hộp i với i = 1, 2, , m và j = 1, , n.
Khi đó theo nguyên lý Dirichlet tồn tại ít nhất một hộp i có ít nhất k + 1
phần tử.
Từ đó suy ra tồn tại phần tử x
i
là phần tử chung của k + 1 tập S
i
với
i = 1, 2, , n.
Ngược lại chứng minh đảo, kí hiệu n phần tử là j = 1, 2, , n. Ta phân
bố các phần tử j = 1, 2, , n vào m hộp H
i
, i = 1, 2, , m.
Kí hiệu S = {H
i
|i = 1, 2, , m}, S
j
= {H
i
|j ∈ H
i
} với mọi j = 1, 2, , n.
Hiển nhiên |S
j
| = 1 với mọi j và |S| = m.
Suy ra |S
1
| + |S
2
| + + |S
Cho A là một khoảng giới nội, A
1
, A
2
, , A
n
là các khoảng sao cho A
i
⊂
A(i = 1, 2, , n) và d(A) < d(A
1
) + d(A
2
) + + d(A
n
) .Khi đó có ít nhất
2 khoảng trong số các khoảng trên có một điểm trong chung.
Chứng minh. Thật vậy, giả sử không có cặp nào trong những khoảng đã cho
có điểm trong chung. Khi đó, d(
n
i=1
A
i
) = d(A
1
) + d(A
2
) + . . . + d(A
n
i
B
i
có điểm trong chung.
Tổng quát :
- Nếu b < ka thì bên trong đoạn AB tồn tại điểm M không thuộc quá
k −1 đoạn con.
7
- Nếu b > ka và đoạn AB chứa tất cả các đoạn A
i
B
i
thì có ít nhất k + 1
đoạn con A
i
B
i
có điểm trong chung.
Phát biểu trừu tượng của phát biểu tổng quát như sau:
Định lý 8. (Nguyên lý Dirichlet cho đoạn thẳng mở rộng)
Cho A là một khoảng giới nội, A
1
, A
2
, A
n
là những khoảng con của A, k
là số tự nhiên thỏa mãn
k.d(A) < d(A
1
i
⊂ A, nên d(A
i
) ≤ d(A) với (i = 1, 2, . . . , n), từ đó suy ra
d(A
1
) + d(A
2
) + . . . + d(A
n
) ≤ n.d(A).
Theo (1.1) ta có (k + 1).d(A) < d(A
1
) + d(A
2
) + . . . + d(A
n
) < n.d(A).
Suy ra: k + 1 < n.
Vì vậy n ≥ k + 2.
Ta chứng minh tồn tại điểm chung cho ít nhất k + 2 tập A
1
, A
2
, . . . , A
n
thỏa mãn (1) bằng quy nạp theo n.
Ta bắt đầu từ n = k + 2, tức là
(k + 1).d(A) < d(A
1
Suy ra : A
i
⊂ A
và A”
i
⊂ A”(i = 1, 2, . . . , k + 1).
Vì có tất cả k + 1 tập hợp A
i
, từ bao hàm thức trên ta được
(k + 1).d(A
) ≥ d(A
1
) + d(A
2
) + . . . + d(A
k+1
). (1.7)
Nếu lấy (1.2) trừ đi (1.7) ta có
(k + 1).d(A”) < d(A
k+2
) + d(A”
1
) + d(A”
, . . . , A
k+1
∩ A
k+2
có điểm trong chung, điều này có nghĩa
là tập hợp A
1
, A
2
, . . . , A
k+2
có điểm trong chung. Như vậy với n = k + 2 từ
(1.3) suy ra ít nhất k + 2 tập hợp thỏa (1.1) có điểm trong chung.
Bây giờ chúng ta giả thiết với n ≥ k + 2 có ít nhất k + 2 tập hợp thỏa (1.1)
có điểm trong chung.
Ta sẽ phải chứng minh rằng từ
(k + 1).d(A) < d(A
1
) + d(A
2
) + . . . + d(A
n
) + d(A
n+1
). (1.10)
Suy ra có ít nhất k + 2 tập hợp trong dãyA
1
, A
2
, . . . , A
∪A”
i
= A
i
, A
i
∩A”
i
= ∅(i = 1, 2, . . . , n) và A
∪A” = A, A
∩A” = ∅
nên
d(A
i
) + d(A”
i
) = d(A
i
)(i = 1, 2, . . . , n), (1.15)
d(A
) + d(A”) = d(A). (1.16)
Chúng ta sẽ chứng minh một trong các bất đẳng thức sau là đúng:
(k + 1).d(A
) < d(A
n
).
Và k.d(A
) ≥ d(A”
1
) + d(A”
2
) + . . . + d(A”
n
).
Cộng hai vế lại và do(1.15), (1.16) ta có
d(A
) + k.d(A) ≥ d(A
1
) + d(A
2
) + . . . + d(A
n
). (1.19)
9
Cộng hai vế (1.19)với d(A”) và từ (1.15), (1.16) ta có
(k + 1).d(A) ≥ d(A
1
) + d(A
2
) + . . . + d(A
n
) + d(A
có điểm trong chung và cùng với (1.12) chỉ ra rằng tồn tại một điểm mà nó
là điểm trong k + 1 tập hợp của A
1
, A
2
, . . . , A
n
, A
n+1
.
Như vậy từ (1.10) suy ra k + 2 tập hợp trong dãy A
1
, A
2
, . . . , A
n
có điểm
trong chung. Suy ra kết luận đúng với n + 1. Từ phương pháp quy nạp, suy
ra điều phải chứng minh.
Nhận xét: Hoàn toàn tương tự ta có thể phát biểu nguyên lý Dirichlet
đối với diện tích một hình (A) và các hình (A
1
), (A
2
), , (A
n
) nằm trong
một mặt phẳng hoặc trên mặt cầu cũng như đối với thể tích V (A) và các
V (A
1
, , A
n
là các bề mặt từng đôi một không có điểm
trong chung thì S(A
1
∪ A
2
∪ ∪A
n
) = S(A
1
) + S(A
2
) + + S(A
n
).
Định lý 12. (Nguyên lý Dirichlet cho diện tích)
Nếu A là một miền giới hạn bởi một đường cong phẳng khép kín, còn A
1
, A
2
, , A
n
là các miền sao cho A
i
⊂ A(i = 1, 2, n) và S(A) < S(A
1
) + S(A
2
) + +
, A
2
, , A
n
là các
khối sao cho A
i
⊂ A(i = 1, 2, n) và V (A) < V (A
1
) + V (A
2
) + + V (A
n
)
thì ít nhất có hai khối trong số các khối trên có điểm trong chung.
Chứng minh. Chứng minh tương tự định lý 7.
Định lý 15. (Nguyên lý Dirichlet cho thể tích mở rộng)
Cho A là một khối giới hạn bởi các mặt cong phẳng, A
1
, A
2
, , A
n
là các khối
sao cho A
i
⊂ A(i = 1, 2, n) còn k là số tự nhiên mà thỏa mãn k.V (A) <
V (A
1
) + V (A
rằng a chia hết cho b kí hiệu là b|a khi tồn tại một số nguyên q sao cho đẳng
thức a = bq đúng. Trong trường hợp này a là bội của b còn b là ước của a,
số q gọi là thương số của phép chia a cho b. Trong trường hợp ngược lại nếu
không tồn tại một số q nào cả thì chúng ta nói rằng a không chia hết cho b
và kí hiệu là b a.
Các tính chất suy từ định nghĩa:
1. Với mọi số nguyên a > 0 thì a|a tức phép chia có tính phản xạ.
2. Nếu b|a và a|c thì b|c tức phép chia hết có tính bắc cầu.
3. Nếu b|a và b|c thì b|ac.
13
4. Nếu a, b, m, n là các số nguyên và nếu c|a và c|b thì c|(ma + nb).
Định lý 16. Với 2 số nguyên bất kì a và b sao cho b > 0, tồn tại duy nhất
những số nguyên q và r thỏa mãn a = bq + r và 0 ≤ r < b.
Sau đây là các bài toán tiêu biểu.
2.1 Nguyên lý Dirichlet trong các bài toán
trùng lặp
Bài toán 2.1. Trong 45 học sinh làm bài kiểm tra không có ai bị dưới điểm
2, chỉ 2 học sinh được điểm 10. Chứng minh rằng ít nhất cũng tìm được 6
học sinh có điểm kiểm tra bằng nhau.
Lời giải:
Có 45 −2 = 43 học sinh phân chia vào 8 loại điểm từ 2 đến 9. Giả sử mỗi
loại trong 8 loại điểm đều là điểm của không quá 5 học sinh thì lớp học có
không quá 5.8 = 40 học sinh, ít hơn 43 học sinh. Vậy tồn tại 6 học sinh có
điểm kiểm tra bằng nhau.
Nhận xét: Trong bài toán này, "thỏ" là 43 điểm kiểm tra từ 2 đến 9, lồng
là 8 loại điểm nói trên. Phép chia 43 cho 8 được 5 còn dư. Tồn tại 5 + 1 = 6
học sinh có điểm kiểm tra bằng nhau.
Bài toán 2.2. Có 5 đấu thủ thi cờ, mỗi người đấu một trận với một đối thủ
khác. Chứng minh rằng trong suốt thời gian thi đấu, luôn tồn tại hai đấu thủ
có số trận đấu đã đấu bằng nhau.
5 lồng nhốt 38 thỏ, vậy theo nguyên lý Dirichlet có ít nhất một lồng nhốt
không ít hơn 8 thỏ, bài toán được chứng minh.
Bài toán 2.5. (Đề thi vô địch Nam Tư, 1970)
Cho trước 20 số tự nhiên a
1
< a
2
< a
3
< < a
20
không vượt quá 70.
Chứng minh rằng giữa các hiệu a
j
− a
k
(j > k) luôn tìm được ít nhất 4 hiệu
bằng nhau.
Lời giải:
Giả sử kết luận của bài toán không đúng, khi đó nói riêng trong 19 hiệu
sau: a
20
−a
19
, a
19
−a
18
, , a
3
1
> 70.
Mặt khác: 1 ≤ a
i
≤ 70(i = 1, 2, , 20) nên a
20
− a
1
≥ 70 −1 = 69.
Ta nhận được mâu thuẫn. Vậy giả thiết phản chứng là sai, từ đó ta có
điều phải chứng minh.
15
Bài toán 2.6. (Đề thi Olympic toán thế giới lần thứ 14)
Cho M là tập hợp bất kì gồm 10 số tự nhiên, mỗi số không lớn hơn 100.
Chứng minh rằng tồn tại hai tập hợp con của M mà tổng của các phần tử
trong chúng bằng nhau.
Lời giải:
Có thể chứng minh nếu tồn tại thoả mãn kết luận của bài toán, thì ta có
thể chọn được hai tập con cùng tính chất ấy nhưng không giao nhau.
Thật vậy, cho X, Y là hai tập con của M có tổng các phần tử bằng nhau.
Chúng ta kí hiệu X
1
gồm các phần tử của X mà không thuộc Y .
Tương tự như vậy Y
1
gồm các phần tử của Y mà không thuộc X. Rõ ràng
X
1
và Y
1
Để làm xuất hiện khái niệm "thỏ", "lồng", ta thành lập dãy số mới như
16
dưới đây. Đặt
B
1
= a
1
B
2
= a
1
+ a
2
B
3
= a
1
+ a
2
+ a
3
B
4
= a
1
+ a
2
+ a
3
+ a
1
, a
2
, , a
n
mà không thoả
mãn khẳng định của bài toán. Khi đó không có số nào trong các số :
S
1
= a
1
S
2
= a
1
+ a
2
S
n
= a
1
+ a
2
+ + a
n
chia hết cho n.
Vì số các số dư khác không trong phép chia cho n là n − 1 nên theo
nguyên lí Dirichlet ta tìm được hai số S
i
i
(i = 1, 2, 3, 4, 5). Xét tích:
P = (a
1
− a
2
)(a
1
− a
3
)(a
1
− a
4
)(a
1
− a
5
)(a
2
− a
3
)(a
2
− a
4
)(a
2
− a
5
theo nguyên lý Dirichlet tại 2 số có cùng số dư khi
chia cho 3.
Giả sử a
1
đồng dư a
2
(mod 3)thì a
1
− a
2
chia hết cho 3.
Lại xét a
2
, a
3
, a
4
, a
5
theo nguyên lý Dirichlet trong 4 số này lại tồn tại 2
số có cùng số dư khi chia cho 3.
Suy ra P chia hết cho 9.
b) Chứng minh P chia hết cho 2
5
:
Trong 5 số đã cho theo nguyên lý Dirichlet chí ít có 3 số cùng tính chẵn
lẻ.
i) Nếu có 4 số chẵn, chẳng hạn a
1
= 2k
)(k
2
− k
4
)(k
2
− k
3
)
(a
2
− a
5
)(a
3
− a
4
)(a
3
− a
5
)(a
4
− a
5
)
chia hết cho 32.
ii) Nếu có 3 số chẵn, 2 số lẻ thì đặt:
a
1
3
).M.
Trong 3 số k
1
, k
2
, k
3
có 2 số cùng tính chẵn lẻ theo nguyên lý Dirichlet.
18
Giả sử k
1
đồng dư k
1
(mod 2) thì k
1
− k
2
chia hết cho 2 nên P chia hết
cho 32.
iii) Nếu có 3 số lẻ là a
1
, a
2
, a
3
còn a
4
, a
5
Lời giải:
Xét: 1 , 11, 111, , 11 1
n
và những số dư khi chia dãy số trên cho n.
Vì dãy số đã cho gồm n phần tử nên những số dư dương khác nhau khi
chia chúng cho n có số lượng n − 1.
Có thể giả thiết không có một số nào trong dãy trên chia hết cho n vì nếu
ngược lại thì bài toán đã giải quyết xong. Khi đó sẽ có hai số trong chúng
ví dụ 111 111
k
và 111 111
l
(l > k) , mà khi chia chúng cho n sẽ cùng một số
dư. Do đó l −k = 111 000
l−k số 1,k số 0
sẽ chia hết cho n.
Bài toán 2.12. Chứng minh rằng tồn tại một số tự nhiên gồm toàn chữ số
1 chia hết cho 2007.
Lời giải:
Xét 2008 số có dạng 1,11, ,11 11. Theo nguyên lý Dirichlet thì tồn tại
hai số có cùng số dư khi chia cho 2007. Giả sử hai số đó là:
A = 11 1
n số
vàB = 11 1
2
b
2
, , a
n+1
= 2
k
n+1
b
n+1
Trong đó b
1
, b
2
, , b
n+1
là các số lẻ.
Ta có: 1 ≤ b
1
, b
2
, , b
n+1
≤ 2n −1.
Mặt khác trong khoảng từ 1 đến 2n − 1 có đúng n số lẻ nên tồn tại hai
số m ≤ n sao cho b
n
= b
m
. Khi đó, trong hai số a
.
. 1000, do đó 3
n
(3
m−n
− 1)
.
.
. 1000).
Ta lại có (3
n
, 1000) = 1 suy ra
3
m−n
− 1
.
.
. 1000 tức là 3
m−n
tận cùng bằng 001.
Bài toán 2.15. a) Viết 20 số tự nhiên vào 20 tấm bìa. Chứng minh rằng ta
có thể chọn một hay nhiều tấm bìa để tổng các số trên đó chia hết cho 20.
b) Anh Nam là một vận động viên chơi cờ. Để tập luyện, mỗi ngày anh chơi
ít nhất một ván. Để khỏi mệt, mỗi tuần anh chơi không quá 12 ván. Chứng
minh rằng tồn tại một số ngày liên liếp trong đó anh chơi đúng 20 ván.
Lời giải:
a) Gọi các số trên 20 ván bìa là a
1
, a
2
2
+ + a
20
.
Nếu không tồn tại tổng nào chia hết cho 20 thì tồn tại hai tổng có cùng số
dư khi chia cho 20, vì có 20 tổng, chỉ có 19 số dư = 0 là 1, 2, , 19. Hiệu của hai
tổng đó chia hết cho 20. Chẳng hạn hai tổng đó là s
m
và s
n
(1 ≤ n < m ≤ 20)
thì s
m
−s
n
= (a
1
+a
2
+ +a
m
)−(a
1
+a
2
+ +a
n
) = a
n+1
+a
2
+ a
3
,
s
20
= a
1
+ a
2
+ + a
20
.
Ta có s
1
< s
2
< < s
20
< 36 vì trong 20 ngày anh Nam chơi ít hơn
12.3 = 36 ván cờ.
Theo câu a) tồn tại s
k
.
.
. 20 hoặc s
m
−s
n
18 số
. Khi đó có 18 số mà phép chia cho 17
chỉ gồm 17 số dư (0, 1, 2, , 16) nên tồn tại hai số có cùng số dư. Gọi 2 số đó
là 11 1
m số
và 11 1
n số
(1 ≤ n < m ≤ 18). Hiệu của chúng bằng 11 1
m−n số
00 0
n số
chia
hết cho 17, hiệu này gồm toàn các chữ số 1 và 0.
b) Theo câu a) tồn tại một bội của 17 có dạng A= 11 1
m−n số
00 0
n số
=
11 1
m−n số
.10
n
mà (10
2
, a
3
, a
4
, a
5
, a
6
sao cho
(a
1
− a
2
)(a
3
− a
4
)(a
5
+ a
6
)
.
.
. 1800.
Lời giải:
Vì ba số nguyên tố đầu tiên là 2, 3, 5, do đó trong 12 số nguyên tố phân
biệt đã cho luôn có ít nhất 9 số lớn hơn 5. Vì là số nguyên tố lớn hơn 5 nên:
1. Chín số trên khi chia cho 3 có dư 1 hoặc 2. Theo nguyên lí Dirichlet
.
.
. 2. Do (2, 15) = 1 nên suy ra a
1
− a
2
.
.
. 30.
2. Xét 7 số còn lại : Theo nguyên lí Dirichlet tồn tại bốn số đồng dư với
nhau theo mod 3 . Đem 4 số này chia cho 5 có hai khả năng xảy ra:
Trường hợp 1: Nếu có hai số chẳng hạn là a
3
, a
4
mà a
3
≡ a
4
(mod 5).
Từ đó suy ra a
3
− a
4
.
.
. 5.
Rõ ràng a
3
− a
Do a
5
, a
6
lẻ và do nguyên tố nên a
5
+ a
6
.
.
. 2.
Từ đó suy ra
(a
1
− a
2
)(a
3
− a
4
)(a
5
+ a
6
)
.
.
. 30.30.2 = 1800.
Trường hợp 2: Nếu 4 số này khi chia cho 5 các số dư khác nhau là 1, 2, 3, 4.
Giả sử a
4
, a
5
, a
6
lẻ nên a
5
+ a
6
.
.
. 2, a
3
− a
4
.
.
. 2.
Từ đó suy ra a
5
+ a
6
.
.
. 10 và a
3
− a
4
.
.
− a
4
)(a
5
+ a
6
)
.
.
. 1800.
Bài toán 2.19. (Đề thi vô địch Anh, 1966)
Chứng minh rằng từ 52 số nguyên bất kì luôn có thể chọn ra được hai số
mà tổng hoặc hiệu của chúng chia hết cho 100.
Lời giải:
Tất cả các số dư trong phép chia cho 100, được chia thành từng nhóm
như sau: 0, 1, 99, 2, 98, , 49, 51, 50.
Vì có tất cả 51 nhóm, mà lại có 52 số, nên theo nguyên lí Dirichlet giữa
chúng phải có hai số mà các số dư trong phép chia cho 100 rơi vào một nhóm.
Hai số này là hai số cần tìm vì nếu số dư của chúng bằng nhau thì hiệu của
chúng chia hết cho 100, còn nếu số dư của chúng khác nhau thì tổng của
chúng chia hết cho 100.
Bài toán 2.20. (Trích đề chọn đội tuyển Việt Nam dự thi IMO, 1999)
Cho A = {a
1
; a
2
; a
3
; } ⊂ N
∗
.Và với mỗi j ∈ N
∗
: A(i; 1), A(i; 2), , A(i; 1999) là 1999 số nguyên dương
liên tiếp (không bé hơn a
1
) do đó theo giả thiết của bài toán về tập hợp A
thì tồn tại j
i
∈ Z ∩ [1; 1999] để A(i; j
i
) ∈ A.
Vì j
1
, j
2
, , j
2000
∈ Z ∩ [1; 1999] nên theo nguyên lý Dirichlet có hai chỉ
23
số nguyên dương m < n ≤ 2000 mà j
m
= j
n
=: j ; với chúng ta tìm được
cặp chỉ số p < q sao cho
a
p
= A(m; j
m
) = A(m; j)|A(n; j) = A(n; j
Không mất tính tổng quát, giả sử A đã đấu với B,C,D.
1. Nếu B,C,D từng cặp chưa đấu với nhau thì bài toán được chứng minh.
2. Nếu B,C,D có 2 đội đã đấu với nhau, ví dụ B và C thì 3 đội A,B,C
từng cặp đã đấu với nhau.
Như vậy bất cứ lúc nào cũng có 3 đội trong đó từng cặp đã đấu với nhau
hoặc chưa đấu với nhau trận nào.
Copyright: Tài liệu đại học ©