Các phương pháp và kỹ thuật chứng minh trong toán học

Các phương pháp và kỹ thuật chứng minh trong toán học

Các định lý toán học phát biểu về các tính chất của các đối tượng toán học và mối quan

hệ giữa chúng. Và những khẳng định này cần được chứng minh xuất phát từ các tiên đề,

các định lý và tính chất đã được chứng minh trước đó. Và để thực hiện bước chứng minh,

ta cần có những quy tắc suy diễn để chứng minh là chặt chẽ về mặt toán học.

Với các bài toán Olympic cũng vậy, yêu cầu chứng minh một kết quả nào đó luôn hiện

diện, ngay cả trong những bài không có cụm từ “chứng minh rằng”. Chẳng hạn để giải

phương trình x3 – 3x + 1 = 0 có thể ta sẽ phải chứng minh tất cả các nghiệm của chúng

thuộc đoạn [-2, 2], để giải phương trình hàm f(x2 + f(y)) = f2(x) + y có thể ta sẽ phải

chứng minh f là toàn ánh .

pdf 81 trang Người đăng haha99 Lượt xem 2359Lượt tải 0 Download
Bạn đang xem 20 trang mẫu của tài liệu "Các phương pháp và kỹ thuật chứng minh trong toán học", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Tài liệu bồi dưỡng đội tuyển Việt Nam 
tham dự IMO 2010 
Tháng 6 - 2010 
Vietnamese IMO Team Training Camp 2010 
2 | Trần Nam Dũng – 6/2010 
Mục lục 
1. Các phương pháp và kỹ thuật chứng minh 2 
2. Nguyên lý chuồng và thỏ 42 
3. Giải phương trình hàm bằng cách lập phương trình 50 
4. Các bài toán tối ưu về hệ các tập hợp 63 
5. Về kỳ thi chọn đội tuyển Việt Nam dự thi IMO 2010 69 
6. Bất đẳng thức: Một số ví dụ và bài tập chọn lọc 80 
Vietnamese IMO Team Training Camp 2010 
3 | Trần Nam Dũng – 6/2010 
Các phương pháp và kỹ thuật chứng minh 
Trong toán học cũng như trong cuộc sống, cần biết: 
Linh hoạt xử lý tình huống, chọn lựa phương án tối ưu 
Trần Nam Dũng 
Trường Đại học KHTN Tp HCM 
Các định lý toán học phát biểu về các tính chất của các đối tượng toán học và mối quan 
hệ giữa chúng. Và những khẳng định này cần được chứng minh xuất phát từ các tiên đề, 
các định lý và tính chất đã được chứng minh trước đó. Và để thực hiện bước chứng minh, 
ta cần có những quy tắc suy diễn để chứng minh là chặt chẽ về mặt toán học. 
Với các bài toán Olympic cũng vậy, yêu cầu chứng minh một kết quả nào đó luôn hiện 
diện, ngay cả trong những bài không có cụm từ “chứng minh rằng”. Chẳng hạn để giải 
phương trình x3 – 3x + 1 = 0 có thể ta sẽ phải chứng minh tất cả các nghiệm của chúng 
thuộc đoạn [-2, 2], để giải phương trình hàm f(x2 + f(y)) = f2(x) + y có thể ta sẽ phải 
chứng minh f là toàn ánh ... 
Bài viết này nói về hai phương pháp và một số kỹ thuật chứng minh cơ bản: chứng minh 
phản chứng, chứng minh quy nạp, chứng minh phản chứng, dùng mệnh đề phản đảo, 
phản ví dụ nhỏ nhất, ví dụ và phản ví dụ, sử dụng nguyên lý Dirichlet, nguyên lý cực hạn, 
nguyên lý bất biến, sử dụng tô màu, đếm bằng hai cách, sắp xếp thứ tự  
Cách tiếp cận của chúng ta là sẽ thông qua các ví dụ để nói về các phương pháp và kỹ 
thuật. Ở đây sẽ chỉ có các nhận xét, bình luận, các nguyên tắc chung chứ không được 
trình bày hệ thống như một lý thuyết. 
Bài viết này đầu tiên được viết và trình bày trong chương trình “Gặp gỡ gỡ Toán học 
2010”, được tổ chức vào tháng 1 năm 2010, sau đó được bổ sung, hoành chỉnh và trình 
bày tại Hội nghị khoa học “Các chuyên đề chuyên Toán và ứng dụng” tổ chức tại Ba Vì, 
tháng 5/2010. Cuối cùng, để chuẩn bị cho đội tuyển Việt Nam thi Olympic Toán quốc tế, 
bài viết được bổ sung thêm các phần về Đếm bằng hai cách, Nguyên lý cực hạn, Sắp xếp 
thứ tự và ứng dụng của các phương pháp và kỹ thuật chứng minh trong bài toán Tối ưu tổ 
hợp. 
1. Phép chứng minh phản chứng 
Một số ví dụ mở đầu 
Chứng minh phản chứng có thể nói là một trong những vũ khí quan trọng của toán học. 
Nó cho phép chúng ta chứng minh sự có thể và không có thể của một tính chất nào đó, nó 
Vietnamese IMO Team Training Camp 2010 
4 | Trần Nam Dũng – 6/2010 
cho phép chúng ta biến thuận thành đảo, biến đảo thành thuận, nó cho phép chúng ta lý 
luận trên những đối tượng mà không rõ là có tồn tại hay không. Ví dụ kinh điển nhất về 
phép chứng minh phản chứng thuộc về Euclid với phép chứng minh 
Định lý. Tồn tại vô số số nguyên tố. 
Ở đây, Euclid đã giả sử ngược lại rằng tồn tại hữu hạn số nguyên tố p1, p2, , pn. Ông xét 
tích N = p1p2pn + 1. N phải có ít nhất 1 ước số nguyên tố p. Khi đó, do p1, p2, , pn là 
tất cả các số nguyên tố nên tồn tại i sao cho p = pi. Nhưng khi đó p | 1, mâu thuẫn. 
Bài tập 
1. Chứng minh rằng tồn tại vô số số nguyên tố dạng 4k+3. 
2. Chứng minh rằng tồn tại vô số số nguyên tố dạng 4k+1. 
Phương pháp xuống thang 
Một chứng minh nổi tiếng khác bằng phương pháp phản chứng chính là chứng minh của 
Euler cho định lý nhỏ Fermat với trường hợp n = 4. 
Định lý. Phương trình x4 + y4 = z4 (1) không có nghiệm nguyên dương. 
Ông đã giả sử rằng phương trình (1) có nghiệm nguyên dương. Khi đó, theo nguyên lý 
cực hạn, tồn tại nghiệm (x0, y0, z0) với x0 + y0 + z0 nhỏ nhất. Sau đó, bằng cách sử dụng 
cấu trúc nghiệm của phương trình Pythagore x2 + y2 = z2, ông đi đến sự tồn tại của một 
nghiệm (x1, y1, z1) có x1 + y1 + z1 < x0 + y0 + z0. Mâu thuẫn. 
Phương pháp này thường được gọi là phương pháp xuống thang. 
Bài tập 
3. Chứng minh rằng phương trình x3 + 3y3 = 9z3 không có nghiệm nguyên dương. 
4. Chứng minh rằng phương trình x2 + y2 + z2 = 2xyz không có nghiệm nguyên dương. 
Sử dụng mệnh đề phản đảo 
Chứng minh sử dụng mệnh đề phản đảo cũng là một phương án chứng minh phản chứng 
hay được sử dụng. Cơ sở của phương pháp là để chứng minh A  B, ta có thể chứng 
minh AB → . Về mặt bản chất thì hai phép suy diễn này có vẻ giống nhau, nhưng trong 
thực tế thì lại khá khác nhau. Ta thử xem xét 1 vài ví dụ. 
Ví dụ 1. Chứng minh rằng hàm số 
1
)(
2 +
=
x
x
xf là một đơn ánh từ R vào R. 
Vietnamese IMO Team Training Camp 2010 
5 | Trần Nam Dũng – 6/2010 
Ví dụ 2. Chứng minh rằng nếu (p-1)! + 1 là số nguyên tố thì p là số nguyên tố. 
Trong ví dụ 1, rõ ràng việc chứng minh x1 ≠ x2 suy ra f(x1) ≠ f(x2) khó khăn hơn việc 
chứng minh f(x1) = f(x2) suy ra x1 = x2, dù rằng về mặt logic, hai điều này là tương 
đương. 
Trong ví dụ 2, gần như không có cách nào khác ngoài cách chứng minh nếu p là hợp số, p 
= r.s thì (p-1)! + 1 không chia hết cho p. 
Bài tập. 
5. Cho hàm số f: R  R thoả mãn các điều kiện sau 
 1) f đơn điệu ; 
2) f(x+y) = f(x) + f(y) với mọi x, y thuộc R. 
6. Cho a, b, c là các số thực không âm thoả mãn điều kiện a2 + b2 + c2 + abc = 4. Chứng minh rằng a + b 
+ c ≤ 3. 
Phương pháp phản ví dụ nhỏ nhất 
Trong việc chứng minh một số tính chất bằng phương pháp phản chứng, ta có thể có 
thêm một số thông tin bổ sung quan trọng nếu sử dụng phản ví dụ nhỏ nhất. Ý tưởng là 
để chứng minh một tính chất A cho một cấu hình P, ta xét một đặc trưng f(P) của P là 
một hàm có giá trị nguyên dương. Bây giờ giả sử tồn tại một cấu hình P không có tính 
chất A, khi đó sẽ tồn tại một cấu hình P0 không có tính chất A với f(P0) nhỏ nhất. Ta sẽ 
tìm cách suy ra điều mâu thuẫn. Lúc này, ngoài việc chúng ta có cấu hình P0 không có 
tính chất A, ta còn có mọi cấu hình P với f(P) < f(P0) đều có tính chất A. 
Ví dụ 3. Cho ngũ giác lồi ABCDE trên mặt phẳng toạ độ có toạ độ các đỉnh đều nguyên. 
a) Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong hoặc nằm trên cạnh của ngũ giác 
(khác với A, B, C, D, E) có toạ độ nguyên. 
b) Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong ngũ giác có toạ độ nguyên. 
c) Các đường chéo của ngũ giác lồi cắt nhau tạo ra một ngũ giác lồi nhỏ A1B1C1D1E1 
bên trong. Chứng minh rằng tồn tại ít nhất 1 điểm nằm trong hoặc trên biên ngũ giác lồi 
A1B1C1D1E1. 
Câu a) có thể giải quyết dễ dàng nhờ nguyên lý Dirichlet: Vì có 5 điểm nên tồn tại ít nhất 
2 điểm X, Y mà cặp toạ độ (x, y) của chúng có cùng tính chẵn lẻ (ta chỉ có 4 trường hợp 
(chẵn, chẵn), (chẵn, lẻ), (lẻ, chẵn) và (lẻ, lẻ)). Trung điểm Z của XY chính là điểm cần 
tìm. 
Sang câu b) lý luận trên đây chưa đủ, vì nếu XY không phải là đường chéo mà là cạnh thì 
Z có thể sẽ nằm trên biên. Ta xử lý tình huống này như sau. Để ý rằng nếu XY là một 
cạnh, chẳng hạn là cạnh AB thì ZBCDE cũng là một ngũ giác lồi có các đỉnh có toạ độ 
đều nguyên và ta có thể lặp lại lý luận nêu trên đối với ngũ giác ZBCDE,  Ta có thể 
Vietnamese IMO Team Training Camp 2010 
6 | Trần Nam Dũng – 6/2010 
dùng đơn biến để chứng minh quá trình này không thể kéo dài mãi, và đến một lúc nào 
đó sẽ có 1 ngũ giác có điểm nguyên nằm trong. 
Tuy nhiên, ta có thể trình bày lại lý luận này một cách gọn gàng như sau: Giả sử tồn tại 
một ngũ giác nguyên mà bên trong không chứa một điểm nguyên nào (phản ví dụ). Trong 
tất cả các ngũ giác như vậy, chọn ngũ giác ABCDE có diện tích nhỏ nhất (phản ví dụ nhỏ 
nhất). Nếu có nhiều ngũ giác như vậy thì ta chọn một trong số chúng. Theo lý luận đã 
trình bày ở câu a), tồn tại hai đỉnh X, Y có cặp toạ độ cùng tính chẵn lẻ. Trung điểm Z 
của XY sẽ có toạ độ nguyên. Vì bên trong ngũ giác ABCDE không có điểm nguyên nào 
nên XY phải là một cạnh nào đó. Không mất tính tổng quát, giả sử đó là AB. Khi đó ngũ 
giác ZBCDE có toạ độ các đỉnh đều nguyên và có diện tích nhỏ hơn diện tích ngũ giác 
ABCDE. Do tính nhỏ nhất của ABCDE (phản ví dụ nhỏ nhất phát huy tác dụng!) nên bên 
trong ngũ giác ZBCDE có 1 điểm nguyên T. Điều này mâu thuẫn vì T cũng nằm trong 
ngũ giác ABCDE. 
Bài tập 
7. Giải phần c) của ví dụ 3. 
8. (Định lý Bezout) Chứng minh rằng nếu (a, b) = 1 thì tồn tại u, v sao cho au + bv = 1. 
9. Trên mặt phẳng đánh dấu một số điểm. Biết rằng 4 điểm bất kỳ trong chúng là đỉnh của một tứ giác lồi. 
Chứng minh rằng tất cả các điểm được đánh dấu là đỉnh của một đa giác lồi. 
Phản chứng trong các bài toán chứng minh sự không tồn tại 
Phương pháp phản chứng thường hay được sử dụng trong các bài toán bất biến hoặc bài 
toán phủ hình để chứng minh sự không thực hiện được. Sau đây chúng ta xem xét 2 ví dụ 
như vậy. 
Ví dụ 4. Xét hình vuông 7 × 7 ô. Chứng minh rằng ta có thể xoá đi một ô để phần còn lại 
không thể phủ kín bằng 15 quân trimino kích thước 1 × 3 và 1 quân trimino hình chữ L. 
Ta chứng minh rằng nếu bỏ đi một ô ở góc trên bên trái thì phần còn lại không thể phủ 
được bằng các quân triminô đã cho. 
Để làm điều này, ta đánh số các ô vuông như sau 
1 2 3 1 2 3 1 
1 2 3 1 2 3 1 
1 2 3 1 2 3 1 
1 2 3 1 2 3 1 
1 2 3 1 2 3 1 
1 2 3 1 2 3 1 
1 2 3 1 2 3 1 
Vietnamese IMO Team Training Camp 2010 
7 | Trần Nam Dũng – 6/2010 
Khi đó, nhận xét rằng 1 quân triminô kích thước 1 × 3 sẽ che 3 số 1, 2, 3 (nếu nó nằm 
ngang) hoặc 3 số giống nhau (nếu nó nằm dọc). Như vậy tổng các số mà một quân 
triminô 1 × 3 che luôn chia hết cho 3. Trong khi đó dễ thấy quân triminô hình chữ L che 
3 số có tổng không chia hết cho 3. 
Bây giờ giả sử ngược lại rằng hình vuông 7 × 7 bỏ đi ô ở góc trên bên trái có thể phủ 
được bằng 15 quân triminô 1 × 3 và 1 quân triminô hình chữ L thì theo lý luận trên, tổng 
số các số mà các quân triminô này che sẽ không chia hết cho 3. Điều này mâu thuẫn vì 
tổng các số trên các ô còn lại bằng 
 20 × 1 + 14 × 2 + 14 × 3 = 90 
chia hết cho 3! 
Mâu thuẫn trên chứng tỏ điều giả sử là sai và ta có điều phải chứng minh. 
Ví dụ 5. Hình tròn được bởi 5 đường kính thành thành 10 ô bằng nhau. Ban đầu trong 
mỗi ô có 1 viên bi. Mỗi lần thực hiện, cho phép chọn 2 viên bi bất kỳ và di chuyển chúng 
sang ô bên cạnh, 1 viên theo chiều kim đồng hồ và 1 viên ngược chiều kim đồng hồ. Hỏi 
sau một số hữu hạn lần thực hiện, ta có thể chuyển tất cả các viên bi về cùng 1 ô được 
không? 
Nếu làm thử thì chúng ta sẽ thấy rằng không thể thực hiện được yêu cầu. Chúng ta có thể 
cùng lắm là dồn 9 viên bi về 1 ô, còn 1 viên bi khác thì không thể dồn được. Nhưng làm 
thế nào để chứng minh điều này? Lời giải hóa ra là khá đơn giản. Ta sẽ dùng phản chứng 
kết hợp với bất biến. 
Ta tô màu các ô bằng hai màu đen trắng xen kẽ nhau. Gọi S là tổng số viên bi nằm ở các 
ô đen thì ở trạng thái ban đầu ta có S = 5. Nếu giả sử ngược lại rằng ta có thể đưa các 
viên bi về cùng 1 ô thì ở trạng thái cuối cùng này, ta sẽ có S = 0 (nếu ta dồn các viên bi 
về một ô trắng) hoặc S = 10 (nếu ta dồn các viên bi về một ô đen). 
Bây giờ ... còn lại 1 đại diện. 
Vietnamese IMO Team Training Camp 2010 
76 | Trần Nam Dũng – 6/2010 
Thật vậy, giả sử có 1 nhóm nào đó nào đó, chẳng hạn nhóm 1 chứa ít nhất 2 người x, y. 
Nếu ta bỏ đi người x khỏi phòng này thì theo các chọn cách chuyển ở trên, điều kiện (*) 
sẽ không còn được thỏa mãn. Tức là tồn tại q nhóm i1, i2, , iq sao cho trong các nhóm 
 1 (đã bỏ người x), i1, i2, , iq (1) 
chỉ chứa nhiều nhất đại diện của q nước. 
Tương tự, tồn tại p nhóm j1, j2, , jp sao cho trong các nhóm 
 1 (đã bỏ người y), j1, j2, , jp (2) 
chỉ chứa nhiều nhất đại diện của p nước. 
Trong các chỉ số i và j, giả sử có r chỉ số trùng nhau: i1 = j1, , ir = jr còn các chỉ số kia 
khác nhau. Khi đó do các nhóm i1, i2, , ir chứa đại diện của ít nhất r nước nên có ít nhất 
r nước trùng nhau ở hai danh sách (1) và (2). Do đó, hai danh sách (1) và (2) gộp lại chứa 
nhiều nhất đại diện của q + p – r nước (3). 
Mặt khác, hợp hai danh sách các phòng nói trên lại, ta được danh sách các phòng phân 
biệt 
 1, i1, i2, , ir, ir+1, , ik, jr+1, , jp 
(nhóm 1 thiếu x và nhóm 1 thiếu y hợp lại thành nhóm 1). 
Áp dụng điều kiện (*) ta thấy hợp của hai danh sách này chứa đại diện của ít nhất 1 + q + 
p – r nước, mâu thuẫn với (3). 
Bài toán được giải quyết hoàn toàn. 
Cách 2. Để lời giải tự nhiên, chúng tôi trình bày thêm phần dẫn dắt. Trong lời giải có thể 
bỏ đi phần in nghiêng. 
Để thuận tiện trình bày, ta phát biểu bài toán dưới dạng tập hợp: Cho A1, A2, , An là n 
tập con k phần tử của X = {1, 2, ,n}, trong đó mỗi phần tử xuất hiện đúng k lần. Khi đó 
tìm được a1, a2, , an đôi một khác nhau sao cho ai thuộc Ai. 
Dễ thấy hợp của p tập hợp bất kỳ chứa ít nhất p phần tử. 
Ý tưởng là ta sẽ chọn a1 một cách bất kỳ từ tập A1, a2 là một phần tử khác a1 chọn từ A2. 
Ta cứ chọn ngẫu nhiên theo nguyên tắc như thế cho đến khi không chọn được nữa. Tức là 
ta gặp trường hợp gặp tập hợp Ap+1 trong đó tất cả các phần tử của nó đã được chọn 
trước đó. Giả sử ai thuộc Ai, i = 1, 2, , p là các phần tử đã được chọn. 
Ta đặt J1 = { i ∈ {1, 2, , k}| ai ∈ Ak+1}. Nếu thì ta 
chọn a thuộc B. Giả sử a thuộc Ai1 thì theo định nghĩa, ai1 thuộc Ak+1, khi đó ta đổi lại, 
chọn a từ Ai1 còn ai1 từ Ak+1. Như vậy ta đã mở rộng cách chọn các phần tử phân biệt 
đến Ak+1. 
Trong trường hợp B1 = ∅, ta lại đặt J2 = {i ∈ {1, 2, , k} | }. Nếu 
 thì ta chọn a thuộc B2. Giả sử a thuộc Ai1 thì ai1 sẽ thuộc 
Ai2 với i2 nào đó thuộc J1, suy ra do đó ai2 thuộc Ak+1. Bây giờ ta chọn a từ Ai1, ai1 từ Ai2 
và ai2 từ Ak+1. Như vậy ta đã mở rộng cách chọn các phần tử phân biệt đến Ak+1. 
Vietnamese IMO Team Training Camp 2010 
77 | Trần Nam Dũng – 6/2010 
Nếu B2 = ∅ thì ta lại tiếp tục thực hiện quá trình trên . 
Bây giờ vào lời giải chính. 
Ta xét đồ thị có hướng G gồm p+1 đỉnh: 1, 2, , p, p+1. Đỉnh i được nối đến đỉnh j nếu 
ai thuộc Aj. Ta đặt 
 J = { i ∈ {1, 2,, p+1}| có đường đi từ i đến p+1} 
Với mọi i ∈ {1, 2,, p}, ta có ai ∈ A  ai thuộc Aj với j nào đó thuộc J  có cạnh nối 
từ i đến j ∈ J  G chứa đường đi từ i đến p+1  i ∈ J. 
Từ đó {i | i ∈ {1, 2,, p}, ai ∈ A} = J \ {p+1} = J*. 
Đặt B = A \ {ai| i ∈ J*}. Khi đó B ∩ {a1, a2,, ap} = ∅ và |B| = |A| - |J*| = |A| - |J| + 1 ≥ 
1. 
Xét a ∈ B. Khi đó a ∈ Aj với j ∈ J nào đó. Rõ ràng j ≠ p+1. Như vậy có 1 đường đi từ j 
đến p+1. Giả sử đó là j0=j, j1,, jl = p+1. Chú ý rằng I = {j0, j1,, jl} ⊆ J. Bây giờ nếu 
đặt bj0, bj1, , bjl tương ứng là a, aj0, , aj(l-1) thì rõ ràng bi ∈ Ai với mọi i thuộc I. Đặt 
bp+1 = ajl, bi = ai với mọi i ∉ I. Khi đó b1, b2, , bk+1 là các phần tử phân biệt lấy từ A1, 
A2, , Ap+1 tương ứng. 
Như vậy ta đã mở rộng được cho p+1 tập hợp. Bài toán được chứng minh hoàn toàn. 
Cách 3. Lời giải này sử dụng định lý Hall sau đây: 
Bổ đề: Cho A1, A2, , An là một họ các tập con của một tập hợp X thỏa mãn điều kiện 
 | với mọi I ⊆ X. (*) 
Khi đó tồn tại a1, a2, , an phân biệt sao của X sao cho ai ∈ Ai với mọi i = 1, 2, , n. 
Chứng minh. 
Ta chứng minh bằng quy nạp theo n. Với n = 1, kết luật của bổ đề là hiển nhiên. 
Giả sử bổ đề đúng với mọi họ tập con F có |F| < n. Xét họ F = (A1, A2, , An). Ta xét hai 
trường hợp. 
Trường hợp 1: Tồn tại một tập chỉ số I ⊂ {1, 2, , n}, | I | < n sao cho | . 
Đặt J = {1, 2, , n} \ I, , Aj* = Aj \ A với mọi j ∈ J. Ta chứng minh họ các 
Aj* thỏa mãn điều kiện (*). Từ đó áp dụng giả thiết quy nạp cho các họ Ai, i ∈ I, Aj*, j ∈ 
J ta suy ra điều phải chứng minh. 
Giả sử ngược lại, tồn tại K ⊂ J sao cho | 
Khi đó, do nên ta có 
 | | 
Mặt khác, do nên vế trái của đẳng thức trên bằng 
| Mâu thuẫn. 
Vietnamese IMO Team Training Camp 2010 
78 | Trần Nam Dũng – 6/2010 
Trường hợp 2: Với mọi I ⊂ {1, 2, , n}, | I | < n, ta có | . Khi đó chọn một 
phần tử bất kỳ a1 từ A1. Đặt Ai* = Ai \{a1} với mọi i = 2, 3, , n. Khi đó với mọi I ⊂ { 2, 
, n}, ta có 
 | 
Như vậy họ (A2*, , An*) thỏa mãn điều kiện (*) và theo giả thiết quy nạp, ta có thể 
chọn được các phần tử phân biệt a2, a3, , an sao cho ai ∈ Ai* với mọi i = 2, , n. Kết 
hợp với a1 ta được các phần tử phân biệt a1, a2, , an trong đó ai ∈ Ai. 
Quay trở lại bài toán, bằng cách mô hình hóa các đại diện của các nước như các phần tử, 
các nhóm như các tập con, bằng cách lý luận tương tự như ở lời giải 1, ta thấy các tập con 
này thỏa mãn điều kiện (*) và do đó tìm được cách chọn thỏa mãn yêu cầu bài toán. 
Nhận xét. Với k=1 và k = n, kết luận của bài toán là hiển nhiên. Với k = 2, ta có một 
cách giải khá đơn giản như sau: Ở nhóm 1, ta lấy ra 1 đại diện bất kỳ thuộc nước i1, tiếp 
theo, ta đến nhóm có người còn lại của nước i1, lấy người còn lại trong nhóm đó (thuộc 
nước i2) làm đại diện cho nhóm này, lại chuyển sang nhóm có người còn lại của nước i2 
 Nếu quá trình này có thể kéo dài mãi đến hết n nhóm thì xong. Nếu không sẽ xảy ra 
trường hợp sau khi chọn đại diện cho nhóm k thuộc nước ik thì người cùng nước với còn 
lại trong nhóm này lại thuộc nhóm 1. Như thế các nhóm 1, 2, , k tạo thành một xích, ta 
loại xíc này đi và làm việc với những nhóm còn lại bằng cách tương tự. 
Bài 6. 
Ta có . 
So sánh hệ số của ở 2 bên ta có 
. 
Tiếp theo ta chứng minh không chia hết cho . 
Giả sử 2n có biểu diễn tam phân là 
với ai ∈{0, 1, 2}. 
Trường hợp 1: các ai thuộc tập {0, 1}, Khi đó a0 + a1 +  + ak = 2p. 
4n có biểu diễn tam phân là (do ai = 0 hoặc 1) và theo định lý Lucas, ta 
có 
Trường hợp 2: tồn tại i nhỏ nhất mà ai = 2, khi đó hệ số tương ứng của 4n là 1. Do 
Vietnamese IMO Team Training Camp 2010 
79 | Trần Nam Dũng – 6/2010 
nên 
Nhận xét. 
• Vì định lý Lucas không được sử dụng nên thí sinh khi sử dụng phải chứng minh 
lại định lý này. 
• Cũng có thể trình bày lời giải trực tiếp không thông qua định lý Lucas, tuy nhiên 
có lẽ không thể tránh khỏi việc sử dụng hệ tam phân và lý luận tổ hợp dưới đây. 
• Cách tiếp cận của đề bài, yêu cầu chứng minh S2n + 1 không chia hết cho 3 có hai 
mục đích: 1) Kiểm tra xem thí sinh có tính được S2n không? Và đây cũng là chỗ để 
cho điểm. 
2) Đưa ra bản chất tổ hợp của từ đó gợi ý đến cách khai triển đa thức 
theo mô-đun. 
 * Để hoàn chỉnh lời giải, chúng tôi trình bày cách chứng minh định lý Lucas. 
Định lý Lucas. Cho m và n là các số nguyên không âm, p là số nguyên tố và 
m = mkpk + mk-1pk-1 +  + m1p + m0 
n = nkpk + nk-1pk-1 +  + n1p + n0 
là các biểu diễn p phân của m và n tương ứng. Khi đó 
 . 
Chứng minh. Ta làm việc trên các đa thức với hệ số được xét theo modulo p. Do 
 với mọi k = 1, 2, , p-1 nên ta có 
 (1+ x)p ≡ 1 + xp (mod p) 
Từ đó bằng quy nạp ta suy ra 
 (mod p) 
Như vậy ta có 
 (mod p) 
Hệ số của xn ở vế trái là . Do biểu diễn p phân của n là duy nhất nên hệ số của xn ở 
vế phải là Từ đây ta có điều phải chứng minh. 
Lời giải trên đây có sử dụng đáp án chính thức, lời giải và ý tưởng của các bạn LTL, 
Phạm Minh Khoa, Võ Quốc Bá Cẩn, Traum và một số thảo luận khác trên diễn đàn 
www.mathscope.org. 
Vietnamese IMO Team Training Camp 2010 
80 | Trần Nam Dũng – 6/2010 
Bất đẳng thức: Một số ví dụ và bài tập chọn lọc 
1. (USA MO 2004) Cho a, b, c là các số thực dương. Chứng minh rằng 
 (a5 – a2 + 3)(b5 – b2 + 3)(c5 – c2 + 3) ≥ (a+b+c)3 
2. (IMO 2005) Chứng minh rằng nếu a, b, c là các số dương có tích lớn hơn hay bằng 1 
thì 
 0225
25
225
25
225
25
≥
++
−
+
++
−
+
++
−
bac
cc
acb
bb
cba
aa
3. (Kvant) Cho a, b, c là các số thực dương thoả mãn điều kiện a + b + c = 1. Chứng minh 
rằng ta luôn có 
 25)(48111 ≥+++++ cabcab
cba
4. (Mathlinks) Cho a, b, c, x, y, z là các số thực thỏa mãn điều kiện 
 (a+b+c)(x+y+z) = 3, (a2+b2+c2)(x2+y2+z2) = 4 
Chứng minh rằng ax + by + cz ≥ 0. 
5. (Việt Nam 2002) Cho x, y, z là các số thực thoả mãn điều kiện x2 + y2 + z2 = 9. Chứng 
minh rằng 2(x+y+z) – xyz ≤ 10. 
6. Cho x, y, z là các số thực thoả mãn điều kiện x + y + z = 0 và x2 + y2 + z2 = 6. Tìm giá 
trị lớn nhất của biểu thức F = x2y + y2z + z2x. 
7. (Vasile Cirtoaje) Cho các số thực không âm thỏa mãn điều kiện a + b + c = 4. Chứng 
minh rằng 
a2b + b2c + c2a + abc ≤ 4. 
8. (IMO 1999) Cho n ≥ 2 là một số nguyên dương cố định, tìm hằng số C nhỏ nhất sao 
cho với mọi số thực không âm x1, x2, , xn 
 ∑ ∑
≤<≤ =





≤+
nji
n
i
ijiji xCxxxx
1
4
1
22 )( 
9. Cho a, b, c là các số thực dương cho trước và x, y, z là các số thực dương thay đổi 
thoả mãn điều kiện xyz = ax + by + cz. Chứng minh rằng giá trị nhỏ nhất của x + y + z 
bằng dabbadcaacdbccb /2/2/2 ++++++++ , trong đó d là số thực dương xác 
định bởi phương trình 
 1=
+
+
+
+
+ dc
c
db
b
da
a
. 
Vietnamese IMO Team Training Camp 2010 
81 | Trần Nam Dũng – 6/2010 
10. (Romanian TST 2007) Cho n ≥ 2 và x1, , xn ; y1, , yn là 2n số thực thoả mãn điều 
kiện 
 ∑ ∑∑
= ==
===
n
i
n
i
iii
n
i
i baba
1 1
2
1
2
,0,1,1 
Chứng minh rằng .
2
1
2
1
nba
n
i
i
n
i
i ≤





+





∑∑
==
11. (IMO Shortlist 2007) Cho a1, a2, , a100 là các số thực không âm thoả mãn điều kiện 
a1
2
 + a2
2
 +  + a100
2
 = 1. Chứng minh rằng 
 a1
2a2 + a2
2a3 +  + a100
2a1 < 12/25. 
12. IMO Short List 2003) Cho n ≥ 2 là số nguyên dương và x1, x2, , xn, y1, y2, , yn là 
2n số thực dương. Giả sử z2, z3, , z2n là các số thực dương sao cho z2i+j ≥ xiyj với mọi i, 
j thuộc {1, 2,,n}. Đặt M = max{z2, z3,, z2n}. Chứng minh rằng 
 




 ++





 ++≥




 ++++
n
yy
n
xx
n
zzzM nnn ......
2
... 11232
13. Cho a1, a2, , an là các số thực sao cho a12 + a22 +  + an2 = 1. Tìm giá trị lớn nhất 
của biểu thức a1a2 + a2a3 +  + an-1an. 
14. Cho x1, x2, , xn là các số dương. Gọi A là số nhỏ nhất trong các số 
,
1
,
1
,...,
1
,
1
,
12
3
1
21
nn
n
xx
x
x
x
x
xx
−
+++ còn B là số lớn nhất trong các số này. Chứng minh 
rằng giá trị lớn nhất của A bằng giá trị nhỏ nhất của B và hãy tìm giá trị này. 
15. Tổng n số thực dương x1, x2, x3, ..., xn bằng 1. Gọi S — là số lớn nhất trong các số 
x1/(1 + x1), x2/(1 + x1 + x2), ..., xn/(1 + x1 + x2 + ... + xn). Tìm giá trị nhỏ nhất của S. Với 
những giá trị nào của x1, x2, x3, ..., xn thì giá trị này đạt được? 

Tài liệu đính kèm:

  • pdfLuyen thi IMOTuan AnhNga Dien.pdf