Tài liệu bồi dưỡng đội tuyển Việt Nam tham dự IMO 2010

 vế phải đều biểu diễn số số 1 của M. 
Nếu ta xét đồ thị G = (V, E) trên tập đỉnh V như một họ các tập con 2 phần tử của V thì ta 
có định lý Euler. 
Định lý 2. (Euler, 1736) Trong mọi đồ thị, tổng bậc các đỉnh của nó bằng hai lần số cạnh 
của nó và như thế, luôn là một số chẵn. 
Định lý sau có thể được chứng minh bằng cách tương tự 
Định lý 3. với mọi Y ⊆ X. 
(Hai tổng ở đẳng thức đầu ứng với số số 1 trên các hàng Y. Các tổng ở đẳng thức thứ hai 
đếm số lần xuất hiện của x trong các tập có dạng A ∩ B). 
Trường hợp đặc biệt khi F = E là tập con 2 phần tử, ta có 
Định lý 4. Với đồ thị G = (V, E), ta có 
(Xem thêm bài Các bài toán tối ưu về hệ các tập hợp) 
5. Nguyên lý cực hạn 
Một tập hợp hữu hạn các số thực luôn có phần tử lớn nhất và phần tử nhỏ nhất. Một tập 
con bất kỳ của N (hoặc Nk) luôn có phần tử nhỏ nhất. Nguyên lý đơn giản này trong 
nhiều trường hợp rất có ích cho việc chứng minh. Hãy xét trường hợp biên! Đó là khẩu 
quyết của nguyên lý này. 
Một số ví dụ mở đầu 
Ta xem xét một số ví dụ sử dụng nguyên lý cực hạn 
Ví dụ 1. Cã 3 tr−êng häc, mçi tr−êng cã n häc sinh. Mçi mét häc sinh quen víi Ýt nhÊt 
n+1 häc sinh tõ hai tr−êng kh¸c. Chøng minh r»ng ng−êi ta cã thÓ chän ra tõ mçi tr−êng 
mét b¹n sao cho ba häc sinh ®−îc chän ®«i mét quen nhau. 
Giải. 
Gäi A lµ häc sinh cã nhiÒu b¹n nhÊt ë mét tr−êng kh¸c. Gäi sè nµy lµ k. Gi¶ sö A ë 
tr−êng 1 vµ nh÷ng b¹n quen A lµ B1, B2, ..., Bk ë tr−êng 2. Ta cã .2
1+≥ nk Còng theo gi¶ 
thiÕt, cã Ýt nhÊt 1 häc sinh C ë tr−êng 3 quen víi A. Gi¶ sö C kh«ng quen víi Bi víi mäi 
i=1, 2, ..., k th× C quen víi nhiÒu nhÊt n - k häc sinh cña tr−êng 2. Suy ra C quen víi Ýt 
nhÊt n+1 - (n-k) = k+1 häc sinh ë tr−êng 1, ®iÒu nµy m©u thuÉn víi c¸ch chän A. VËy C 
ph¶i quen víi mét Bi nµo ®ã. Khi ®ã A, Bi vµ C chÝnh lµ 3 häc sinh cÇn t×m. 
Vietnamese IMO Team Training Camp 2010 
36 | Trần Nam Dũng – 6/2010 
Ví dụ 2. Chứng minh rằng không tồn tại số n lẻ, n > 1 sao cho 15n + 1 chia hết cho n 
Giải. Giả sử tồn tại một số nguyên lẻ n > 1 sao cho 15n + 1 chia hết cho n. Gọi p là ước số 
nguyên tố nhỏ nhất của n, khi đó p lẻ. Giả sử k là số nguyên dương nhỏ nhất sao cho 15k 
– 1 chia hết cho p. 
Vì 152n – 1 = (15n-1)(15n+1) chia hết cho p. Mặt khác, theo định lý nhỏ Fermat thì 15p-1 – 
1 chia hết cho p. Theo định nghĩa của p, suy ra k là ước số của các số p-1 và 2n. Suy ra k | 
(p-1, 2n). Do p là ước số nguyên tố nhỏ nhất của n nên (n, p-1) = 1. Suy ra (p-1, 2n) = 2. 
Vậy k | 2. Từ đó k = 1 hoặc k = 2. Cả hai trường hợp này đều dẫn tới p = 7. Nhưng điều 
này mâu thuẫn vì 15n + 1 luôn đồng dư 2 mod 7 
Bài tập 
1. Cho n điểm xanh và n điểm đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh 
rằng ta có thể nối 2n điểm này bằng n đoạn thẳng có đầu mút khác màu sao cho chúng đôi một không 
giao nhau. 
2. Trªn ®−êng th¼ng cã 2n+1 ®o¹n th¼ng. Mçi mét ®o¹n th¼ng giao víi Ýt nhÊt n ®o¹n th¼ng kh¸c. Chøng 
minh r»ng tån t¹i mét ®o¹n th¼ng giao víi tÊt c¶ c¸c ®o¹n th¼ng cßn l¹i. 
3. Trong mÆt ph¼ng cho n > 1 ®iÓm. Hai ng−êi ch¬i lÇn l−ît nèi mét cÆp ®iÓm ch−a ®−îc nèi b»ng mét 
vÐc-t¬ víi mét trong hai chiÒu. NÕu sau n−íc ®i cña ng−êi nµo ®ã tæng c¸c vÐc t¬ ®· vÏ b»ng 0 th× ng−êi 
thø hai th¾ng; nÕu cho ®Õn khi kh«ng cßn vÏ ®−îc vÐc t¬ nµo n÷a mµ tæng vÉn ch−a cã lóc nµo b»ng 0 th× 
ng−êi thø nhÊt th¾ng. Hái ai lµ ng−êi th¾ng cuéc nÕu ch¬i ®óng? 
Nguyên lý cực hạn và bất đẳng thức 
Nguyên lý cực hạn thường được áp dụng một cách hiệu quả trong các bất đẳng thức có 
tính tổ hợp, dạng chứng minh tồn tại k số từ n số thỏa mãn một điều kiện này đó. 
Ví dụ 1. (Moscow MO 1984) Trên vòng tròn người ta xếp ít nhất 4 số thực không âm có 
tổng bằng 1. Chứng minh rằng tổng tất cả các tích các cặp số kề nhau không lớn hơn . 
Giải. 
Ta cần chứng minh rằng với mọi n ≥ 4 số thực không âm а1, ..., аn, có tổng bằng 1, ta có 
bất đẳng thức 
a1a2 + a2a3 + ... + an - 1an + ana1 ≤ 1/4. 
Với n chẵn n (n = 2m) điều này có thể chứng minh dễ dàng: đặt a1 + a3 + ... + a2m - 1 = a; 
khi đó, rõ ràng, 
a1a2 + a2a3 + ... + an - 1an + ana1 ≤ (a1 + a3 + ... + a2m−1) × (a2 + a4 + ... + a2m) = a(1 − a) ≤ 
1/4. 
Vietnamese IMO Team Training Camp 2010 
37 | Trần Nam Dũng – 6/2010 
Giả sử n lẻ và ak – là số nhỏ nhất trong các số đã cho. (Để thuận tiện, ta giả sử 1 < k < n 
− 1 – điều này không làm mất tính tổng quát khi n ≥ 4.) Đặt bi = аi, với i = 1,..., k − 1, bk 
= ak + ak + 1 và bi = ai + 1 với i = k + 1,..., n − 1. Áp dụng bất đẳng thức của chúng ta cho 
các số b1,..., bn - 1, ta được: 
a1a2 + ... + ak - 2ak - 1 + (ak - 1 + ak + 2) bk + ak + 2ak + 3 + ... + an - 1an + ana1 ≤ 1/4. 
Cuối cùng, ta sử dụng bất đẳng thức 
ak - 1ak + akak + 1 + ak + 1ak + 2 ≤ ak - 1ak + ak - 1ak + 1 + ak + 1ak + 2 ≤ (ak - 1 + ak + 2) bk. 
để suy ra điều phải chứng minh. 
Đánh giá trên đây là tốt nhất; dấu bằng xảy ra khi 2 trong n số bằng 1/2, còn các số còn 
lại bằng 0. 
Ví dụ 2. Cho n ≥ 4 và các số thực phân biệt a1, a2, , an thoả mãn điều kiện 
 .1,0
1
2
1
== ∑∑
==
n
i
i
n
i
i aa 
Chứng minh rằng tồn tại 4 số a, b, c, d thuộc {a1, a2, , an} sao cho 
 .
1
3
nabddbaanabccba
n
i
i +++≤≤+++ ∑
=
Ví dụ 3. Tổng bình phương của một 100 số thực dương lớn hơn 10000. Tổng của chúng 
nhỏ hơn 300. Chứng minh rằng tồn tại 3 số trong chúng có tổng lớn hơn 100. 
Giải. Giả sử 100 số đó là C1 ≥ C2 ≥...≥ C100 > 0. Nếu như C1 ≥ 100, thì C1 + C2 + C3 > 
100. Do đó ta có thể giả sử rằng C1 0, 100 - C2 > 0, C1 - C2 ≥ 0 
и C1 - C3 ≥ 0, vì vậy 
100(C1 + C2 + C3)≥ 100(C1 + C2 + C3) - (100 - C1)(C1 - C3) - (100 - C2)(C2 - C3) = 
 = C12 + C22 + C3(300 - C1 - C2) > 
 > C12 + C22 + C3(C3 + C4 + ... + C100) ≥ 
 ≥ C12 + C22 + C32 + ... + C1002 > 10000. 
Suy ra, C1 + C2 + C3 > 100. 
Bài tập 
1. Trong mỗi ô của bảng 2 x n ta viết các số thực dương sao cho tổng các số của mỗi cột bằng 1. Chứng 
minh rằng ta có thể xoá đi ở mỗi cột một số sao cho ở mỗi hàng, tổng của các số còn lại không vượt quá 
.
4
1+n
2. 40 tên trộm chia 4000 euro. Một nhóm gồm 5 tên trộm được gọi là nghèo nếu tổng số tiền mà chúng 
được chia không quá 500 euro. Hỏi số nhỏ nhất các nhóm trộm nghèo trên tổng số tất cả các nhóm 5 tên 
trộm bằng bao nhiêu? 
Nguyên lý cực hạn và phương trình Diophant 
Vietnamese IMO Team Training Camp 2010 
38 | Trần Nam Dũng – 6/2010 
Nguyên lý cực hạn ứng dụng trong phương trình Diophant đã được nhắc tới trong bài 
phương pháp chứng minh phản chứng. Trong phần này, ta trình bày chi tiết ba ví dụ áp 
dụng nguyên lý cực hạn trong phương trình Fermat, phương trình Pell và phương trình 
dạng Markov. 
Ví dụ 1. Chứng minh rằng phương trình x4 + y4 = z2 (1) không có nghiệm nguyên dương. 
Giả sử ngược lại, phương trình (1) có nghiệm nguyên dương, và (x, y, z) là nghiệm của 
(1) với z nhỏ nhất. 
(1) Dễ thấy x2,y2,z đôi một nguyên tố cùng nhau 
(2) Từ nghiệm của phương trình Pythagore, ta có tồn tại p, q sao cho 
x
2
 = 2pq 
y2 = p2 - q2 
z = p2 + q2 
(3) Từ đây, ta lại có một bộ ba Pythagore khác, vì y2 + q2 = p2. 
(4) Như vậy, tồn tại a,b sao cho 
q = 2ab 
y = a2 - b2 
p = a2 + b2 
a,b nguyên tố cùng nhau 
(5) Kết hợp các phương trình này, ta được: 
x
2
 = 2pq = 2(a2 + b2)(2ab) = 4(ab)(a2 + b2) 
(6) Vì ab và a2 + b2 nguyên tố cùng nhau, ta suy ra chúng là các số chính phương. 
(7) Như vậy a2 + b2 = P2 và a = u2, b = v2. Suy ra P2 = u4 + v4. 
(8) Nhưng bây giờ ta thu được điều mâu thuẫn với tính nhỏ nhất của z vì: 
P2 = a2 + b2 = p < p2 + q2 = z < z2. 
(9) Như vậy điều giả sử ban đầu là sai, suy ra điều phải chứng minh. 
Ví dụ 2. Tìm tất cả các cặp đa thức P(x), Q(x) thỏa mãn phương trình 
 P2(x) = (x2-1)Q2(x) + 1 (1) 
Giải. Không mất tính tổng quát, ta chỉ cần tìm nghiệm trong tập các đa thức có hệ số khởi 
đầu dương. 
Nếu )(1)()1( 22 xQxxPxx nnn −+=−+ (2) thì )(1)()1( 22 xQxxPxx nnn −−=−− (3) 
Vietnamese IMO Team Training Camp 2010 
39 | Trần Nam Dũng – 6/2010 
Nhân (2) và (3) vế theo vế, ta được 
)()1()(
))(1)())((1)(()1()1(1
222
2222
xQxxP
xQxxPxQxxPxxxx
nn
nnnn
nn
−−=
−−−+=−−−+=
Suy ra cặp đa thức Pn(x), Qn(x) xác định bởi (2) (và (3)!) là nghiệm của (1). Ta chứng 
minh đây là tất cả các nghiệm của (1). Thật vậy, giả sử ngược lại, tồn tại cặp đa thức 
P(x), Q(x) không có dạng Pn(x), Qn(x) thỏa mãn (1). Ta xét cặp đa thức (P, Q) như vậy 
với degQ nhỏ nhất. 
Đặt )(*1)(*)1))((1)(( 222 xQxxPxxxQxxP −+=−−−+ (4) 
Thì rõ ràng 
 )(*1)(*)1))((1)(( 222 xQxxPxxxQxxP −−=−+−− 
Suy ra (P*, Q*) cũng là nghiệm của (1). 
Khai triển (4), ta thu được P*(x) = xP(x) – (x2-1)Q(x), Q*(x) = xQ(x) – P(x). Chú ý là từ 
(1) ta suy ra (P(x) – xQ(x))(P(x)+xQ(x)) = - Q2(x) + 1. Vì P(x) và Q(x) đều có hệ số khởi 
đầu > 0 và degP = degQ + 1 nên ta có deg(P(x)+xQ(x)) = degQ + 1. Từ đây, do deg(-
Q2(x) + 1) ≤ 2deg(Q) nên ta suy ra deg(Q*(x)) ≤ deg(Q) – 1 < deg Q. 
Như vậy, theo cách chọn cặp (P, Q) thì tồn tại n sao cho (P*, Q*) = (Pn, Qn). 
Nhưng khi đó từ (4) suy ra 
1222
222
)1()1()1(
)1))((*1)(*()(1)(
+
−+=−+−+=
−+−+=−+
nn xxxxxx
xxxQxxPxQxxP
Suy ra (P, Q) = (Pn+1,Qn+1), mâu thuẫn. 
Vậy điều giả sử là sai và ta có điều phải chứng minh. 
Ví dụ 3. Tìm tất cả các giá trị k sao cho phương trình (x+y+z)2 = kxyz có nghiệm nguyên 
dương. 
Ví dụ 4. (CRUX, Problem 1420) Nếu a, b, c là các số nguyên dương sao cho 
 0 < a2 + b2 – abc ≤ c 
Chứng minh rằng a2 + b2 – abc là số chính phương. 
Giải. Giả sử ngược lại rằng tồn tại các số nguyên dương a, b, c sao cho 0 < a2 + b2 – abc 
≤ c và k = a2 + b2 – abc (1) không phải là số chính phương. 
Bây giờ ta cố định k và c và xét tập hợp tất cả các cặp số nguyên dương (a, b) thỏa mãn 
phương trình (1), tức là ta xét 
 S(c, k) = {(a, b) ∈ (N*)2: a2 + b2 – abc = k} 
Giả sử (a, b) là cặp số thuộc S(c, k) có a + b nhỏ nhất. Không mất tính tổng quát có thể 
giả sử a ≥ b. Ta xét phương trình 
Vietnamese IMO Team Training Camp 2010 
40 | Trần Nam Dũng – 6/2010 
 x
2
 – bcx + b2 – k = 0 
Ta biết rằng x = a là một nghiệm của phương trình. Gọi a1 là nghiệm còn lại của phương 
trình này thì a1 = bc – a = (b2 – k)/a. 
Ta có thể chứng minh được rằng (bạn đọc tự chứng minh!) a1 nguyên dương. Suy ra 
(a1, b) cũng thuộc S(c, k). 
Tiếp theo ta có a1 = (b2-k)/a < a2/a = a, suy ra a1 + b < a + b. Điều này mâu thuẫn với cách 
chọn (a, b). 
Bài tập 
1. (IMO 88) Nếu a, b, q = (a2+b2)/(ab+1) là các số nguyên dương thì q là số chính phương. 
2. (PTNK 03). Tìm tất cả các số nguyên dương k sao cho phương trình x2 - (k2-4)y2 = - 24 có nghiệm 
nguyên dương. 
3. (Mathlinks) Cho A là tập hợp hữu hạn các số nguyên dương. Chứng minh rằng tồn tại tập hợp hữu hạn 
các số nguyên dương B sao cho A ⊂ B và ∏x∈B x = Σ x∈B x2. 
4. (AMM 1995) Cho x, y là các số nguyên dương sao cho xy + x và xy + y là các số chính phương. 
Chứng minh rằng có đúng một trong hai số x, y là số chính phương. 
5. (IMO 2007) Cho a, b là các số nguyên dương sao cho 4ab – 1 chia hết (4a2-1)2. Chứng minh rằng a = b. 
6. Sắp thứ tự 
Sắp thứ tự là một cách để giảm số trường hợp cần xét và tạo ra các điều kiện bổ sung 
giúp chúng ta có thể làm việc dễ dàng hơn. 
Ví dụ 1. Cho x1, x2, , xn là n số thuộc đoạn [0, 2]. Chứng minh rằng 
 ∑∑
= =
≤−
n
i
n
j
ji nxx
1
2
1
.|| 
Ví dụ 2. (Bất đẳng thức Schur mở rộng) Cho x, y, z là các số thực không âm, r là một số 
thực dương bất kỳ. Chứng minh rằng ta có bất đẳng thức 
 ar(a-b)(a-c) + br(b-a)(b-c) + cr(c-a)(c-b) ≥ 0 
Ví dụ 3. Cho a, b, c là các số thực đôi một khác nhau. Chứng minh rằng 
( )
2
9
)(
1
)(
1
)(
1
222
222 ≥





−
+
−
+
−
++
accbba
cba
Bài tập 
1. Cho x, y, z thuộc [0, 1]. Chứng minh rằng (x+y+z)((x-y)2+(y-z)2+(z-x)2) ≤ 4. 
Vietnamese IMO Team Training Camp 2010 
41 | Trần Nam Dũng – 6/2010 
2. (IMO 2006) Tìm số thực M nhỏ nhất sao cho bất đẳng thức 
|ab(a2 - b2) + bc(b2 - c2) + ca(c2 - a2)| < M(a2 + b2 + c2)2 
đúng với mọi số thực a, b, c. 
3. (Vietnam MO 2008) Cho x, y, z là các số thực không âm khác nhau. Chứng minh rằng 
 .4)(
1
)(
1
)(
1)( 222 ≥





−
+
−
+
−
++
xzzyyx
zxyzxy 
Tài liệu tham khảo 
1. Đoàn Quỳnh, Doãn Minh Cường, Trần Nam Dũng, Đặng Hùng Thắng, Tài liệu giáo 
khoa chuyên toán, Đại số 10, Nhà xuất bản Giáo dục 2009. 
2. Đoàn Quỳnh, Doãn Minh Cường, Trần Nam Dũng, Đặng Hùng Thắng, Tài liệu giáo 
khoa chuyên toán, Bài tập Đại số 10, Nhà xuất bản Giáo dục 2009. 
3. Nguyễn Văn Mậu, Trần Nam Dũng, Vũ Đình Hòa, Đặng Huy Ruận, Chuyên đề chọn 
lọc Tổ hợp và Toán rời rạc, Nhà xuất bản Giáo dục 2008. 
4. Arthur Engel, Problem Solving Strategies, Springer 1998. 
5. N.Agakhanov, Các bài thi Olimpic Toán toàn Nga 1996-2006, Nhà xuất bản MCCME 
2007. 
6. A. Kovaldzi và A. Kanel-Belov, Giải bài toán không mẫu mực như thế nào, Nhà xuất 
bản MCCME 2006. 
7. Stasys Jukna, Extremal Combinatorics, Springer 2001. 
Vietnamese IMO Team Training Camp 2010 
42 | Trần Nam Dũng – 6/2010 
Nguyên lý chuồng và thỏ 
Nguyên lý chuồng và thỏ (hay còn được gọi là nguyên lý Dirichlet) khẳng định một sự 
kiện “hiển nhiên” rằng n+1 con thỏ không thể được xếp vào n chuồng sao cho mỗi con 
thỏ đều ở riêng một chuồng. Một cách tổng quát hơn, nguyên lý chuồng và thỏ khẳng 
định rằng: 
Nếu một tập hợp gồm nhiều hơn kn đối tượng được chia thành n nhóm, thì có một nhóm 
nào đó có nhiều hơn k đối tượng. 
Chân lý này rất dễ kiểm tra: nếu nhóm nào cũng có nhiều nhất k đối tượng thì tổng cộng 
chỉ có nhiều nhất kn đối tượng được chia ra. 
Đây là một trong những nguyên lý không xây dựng (non-constructive) lâu đời nhất: nó 
chỉ nói đến sự tồn tại của một chuồng trong đó có nhiều hơn k vật mà không nói gì đến 
cách tìm ra chuồng này. Ngày nay chúng ta đã có những tổng quát hóa rất mạnh của 
nguyên lý này (các định lý kiểu Ramsey, phương pháp xác suất). 
Mặc dù nguyên lý chuồng và thỏ được phát biểu rất đơn giản, nó có hàng loạt các ứng 
dụng không tầm thường. Cái khó của việc ứng dụng nguyên lý này là xác định được xem 
thỏ là gì và chuồng là gì. Chúng ta sẽ minh họa điều này bằng một số ví dụ. 
1. Một số ví dụ mở đầu 
Để khởi động, chúng ta sẽ bắt đầu bằng những ứng dụng đơn giản nhất. Bậc của một đỉnh 
trong đồ thị G là số d(x) các cạnh của G kề với x. 
Mệnh đề 1. Trong mọi đồ thị tồn tại hai đỉnh có cùng bậc. 
Chứng minh. Giả sử ta có đồ thị G có n đỉnh. Ta tạo ra n cái chuồng được đánh số từ 0 
đến n-1 và xếp đỉnh x vào chuồng thứ k khi và chỉ khi d(x) = k. Nếu như trong một 
chuồng nào đó có nhiều hơn 1 đỉnh thì ta có đpcm. Vì thế ta có thể giả sử rằng không có 
chuồng nào chứa hơn 1 đỉnh. Có tất cả n đỉnh được chia vào n cái chuồng, nhưng vậy mỗi 
một chuồng có đúng 1 đỉnh. Gọi x và y là các đỉnh nằm trong các chuồng đánh số 0 và n-
1 tương ứng. Đỉnh x có bậc 0 vì vậy nó không được nối với các đỉnh khác, trong đó có y. 
Nhưng y có bậc n-1 nên nó lại được nối với tất cả các đỉnh, trong đó có x, mâu thuẫn. 
Nếu G là một đồ thị hữu hạn, chỉ số độc lập (independent number) α(G) là số lớn nhất 
các đỉnh đôi một không kề nhau của G. Sắc số (chromatic number) χ(G) của G là số nhỏ 
nhất các màu cần dùng để tô các màu của G sao cho không có hai đỉnh kề nhau được tô 
cùng màu. 
Vietnamese IMO Team Training Camp 2010 
43 | Trần Nam Dũng – 6/2010 
Mệnh đề 2. Trong mọi đồ thị G với n đỉnh ta có n ≤ α(G).χ(G). 
Chứng minh. Ta chia các đỉnh của G thành χ(G) nhóm (các tập hợp các đỉnh có cùng 
màu). Theo nguyên lý chuồng và thỏ, một trong các nhóm đó có chứa ít nhất n/χ(G) đỉnh, 
và các đỉnh này đôi một không kề nhau. Như vậy α(G) ≥ n/χ(G) và đó chính là điều cần 
chứng minh. 
Một đồ thị là liên thông nếu giữa hai đỉnh bất kỳ của nó có một đường đi. 
Mệnh đề 3. Cho G là một đồ thị n đỉnh. Nếu mọi đỉnh của G có bậc ít nhất là (n-1)/2 
thì G liên thông. 
Chứng minh. Ta xét hai đỉnh x, y bất kỳ. Nếu hai đỉnh này không kề nhau thì có ít nhất n-
1 đỉnh nối chúng với các đỉnh còn lại, vì cả x và y đều có bậc ít nhất là (n-1)/2. Vì chỉ còn 
n-2 đỉnh khác, nguyên lý chuồng và thỏ suy ra rằng phải có một trong các đỉnh đó nối với 
cả x và y. Ta đã chứng minh được rằng mọi cặp đỉnh thì hoặc kề nhau, hoặc có đỉnh kề 
chung, và như vậy G liên thông. 
Ghi chú. Một kết quả là tốt nhất nếu như kết luận không còn đúng khi ta làm yếu đi một 
điều kiện. Ví dụ, trong kết quả trên: giả sử n là chẵn và G là hợp của hai đồ thị đầy đủ 
với n/2 đỉnh thì bậc của mỗi đỉnh bằng (n-2)/2 nhưng đồ thị không liên thông. 
Bài tập 1. Giả sử 5 điểm được chọn trong hình vuông cạnh 1. Chứng minh rằng tồn tại ít nhất 1 cặp điểm 
cách nhau không quá 1/2. 
Bài tập 2. Các viên đá của 8 màu khác nhau được xếp vào 6 cái hộp. Có 20 viên đá cho mỗi màu. Chứng 
minh rằng tìm được một hộp chứa hai cặp có cùng màu khác nhau. 
Bài tập 3. Chứng minh rằng một tập hợp bất kỳ gồm n+1 phần tử được chọn từ {1, 2,,2n} đều chứa 
một cặp phần tử có tổng bằng 2n+1. Hãy chứng minh kết quả này là tốt nhất. 
Bài tập 4. Chứng minh rằng một tập hợp bất kỳ gồm n+1 số nguyên được chọn từ {1, 2,, 2n} chứa hai 
số mà số này chia hết cho số kia. 
2. Định lý Erdos-Szekeres 
Cho A = (a1, a2,, an) là dãy gồm n số phân biệt. Một dãy con k phần tử của A là dãy B 
gồm k số hạng phần tử của A xuất hiện theo đúng thứ tự mà chúng xuất hiện trong A. Có 
nghĩa là B = (ai1, ai2,, aik) với i1 < i2 < < ik. Dãy con B được gọi là tăng nếu ai1 < ai2 
 ai2 >> aik. 
Ta quan tâm đến độ dài lớn nhất của dãy con tăng và giảm của A. Suy luận trực quan cho 
thấy phải có một sự cân đối nhất định giữa hai độ dài này. Nếu như dãy con tăng dài nhất 
là ngắn, chẳng hạn có chiều dài là s, thì mọi dãy con của A có độ dài s+1 phải chứa cặp 
Vietnamese IMO Team Training Camp 2010 
44 | Trần Nam Dũng – 6/2010 
phần tử giảm, như vậy có rất nhiều cặp phần tử giảm. Vì thế ta trông đợi rằng dãy con 
giảm dài nhất sẽ lớn. Một trường hợp cực biên xảy ra khi s = 1. Khi đó cả dãy số A là 
giảm. 
Làm sao ta có thể số hóa điều dự cảm rằng độ dài của dãy con tăng dài nhất và dãy con 
giảm dài nhất không thể cùng nhỏ ? Kết quả nổi tiếng của Erdos và Szekeres (1935) cho 
chúng ta câu trả lời cho câu hỏi này và đây là một trong những kết quả đầu tiên của tối ưu 
tổ hợp. 
Định lý 4 (Erdos-Szekeres 1935). Cho A = (a1, a2,, an) là dãy gồm n số thực phân biệt. 
Nếu n ≥ rs + 1 thì hoặc A có dãy con tăng độ dài s+1 hoặc A có dãy con giảm độ dài r+1 
(hay cả hai). 
Chứng minh. (của Seidenberg 1959). Ta cho tương ứng mỗi phần tử ai của A với cặp 
“điểm số“ (xi, yi) trong đó xi là số phần tử của dãy con tăng dài nhất kết thúc tại ai và yi là 
số phần tử của dãy con giảm dài nhất bắt đầu từ ai. Chú ý rằng không có hai phần tử nào 
có cùng điểm số, tức là (xi, yi) ≠ (xj, yj) với mọi i ≠ j. Thật vậy, nếu ta có ... ai ... aj ..., thì 
hoặc ai < aj và dãy con tăng dài nhất kết thúc tại ai có thể kéo dài đến aj (và do đó xi < xj), 
hoặc ai > aj và dãy con giảm dài nhất bắt đầu từ aj có thể được bắt đầu từ ai (và như thế yi 
> yj). 
Bây giờ ta tạo ra một lưới gồm n chuồng thỏ. 
n 
s 
1 
1 r n 
Ta đặt mỗi phần tử ai vào chuồng với tọa độ (xi, yi). Mỗi một phần tử của A có thể được 
đặt vào một chuồng vì 1 ≤ xi, yi ≤ n với mọi i = 1, 2, ..., n. Hơn nữa, không có chuồng 
nào được chứa nhiều hơn một phần tử, vì (xi, yi) ≠ (xj, yj) với mọi i ≠ j. Vì |A| = n ≥ rs + 
1, ta có nhiều vật hơn là số chuồng thỏ được tô đậm trong hình vẽ trên. Như vậy phải có 
một phần tử ai nằm ngoài miền tô đậm. Nhưng điều này có nghĩa là xi ≥ s+1 hoặc yi ≥ r + 
1 (hoặc cả hai), đúng điều chúng ta cần. 
Tập hợp các số thực được sắp toàn phần. Điều này có nghĩa là với hai số phân biệt x, y 
thì hoặc x < y hoặc y < x. Bổ đề dưới đây, thuộc về Dilworth, sẽ tổng quát hóa định lý 
Erdos-Szekeres cho các tập hợp mà trong đó hai phần tử có thể không so sánh được. 
Vietnamese IMO Team Training Camp 2010 
45 | Trần Nam Dũng – 6/2010 
Một thứ tự bộ phận (yếu) trên tập hợp P là quan hệ hai ngôi < giữa các phần tử của P. Ta 
nói hai phần tử x và y là so sánh được nếu x <