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 .
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: