Đề thi THPT Quốc gia môn Toán năm 2015, De thi thu THPT Quoc Gia nam 2015

You are here: Home »

Like VNMATH on FACEBOOK để ủng hộ VNMATH.

Phép chứng minh phản chứng

VnMaTh.CoM 31 tháng 1, 2010 , 0

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ó 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ố  p_1, p_2,..., p_n. Ông xét tích N = p_1p_2...p_n + 1. N phải có ít nhất 1 ước số nguyên tố p. Khi đó, do p_1, p_2,..., p_n là tất cả các số nguyên tố nên tồn tại i sao cho p = p_i. Nhưng khi đó p chia hết 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.

Bài tập 2.
Chứng minh rằng tồn tại vô số số nguyên tố dạng 4k+1.

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 x^4 + y^4 = z^4 (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 (x_0, y_0, z_0) với x_0 + y_0 + z_0 nhỏ nhất. Sau đó, bằng cách sử dụng cấu trúc nghiệm của phương trình Pythagore x^2 + y^2 = z^2, ông đi đến sự tồn tại của một nghiệm (x_1, y_1, z_1)x_1 + y_1 + z_1 < x_0 + y_0 + z_0. 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 x^3 + 3y^3 = 9z^3 không có nghiệm nguyên dương.


Bài tập 4. Chứng minh rằng phương trình x^2 + y^2 + z^2 = 2xyz không có nghiệm nguyên dương.

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 \Rightarrow B, ta có thể chứng minh \overline{B} \Rightarrow \overline{A} .

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 một vài ví dụ.

Ví dụ 1. Chứng minh rằng hàm số  f(x) = \frac{x}{\sqrt{x^2+1}} là một đơn ánh từ R vào R.

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 x_1 \ne x_2suy ra f(x_1) \ne f(x_2) khó khăn hơn việc chứng minh f(x_1) = f(x_2) suy ra x_1 = x_2, 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.
Chứng minh rằng tồn tại số thực a sao cho f(x) = ax với mọi x thuộc R.


Bài tập 6. Cho a, b, c là các số thực không âm thoả mãn điều kiện a^2 + b^2 + c^2 + abc = 4. Chứng minh rằng  a + b + c \le 3.

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ỏ A_1B_1C_1D_1E_1 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 A_1B_1C_1D_1E_1.


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

Bài tập 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.

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 x 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 x 3 và 1 quân trimino hình chữ L.

Ví dụ 5. Cho trước các hàm số  f_1(x) = x^2 + 2x, f_2(x) = x + 1/x, f_3(x) = x^2 - 2x. Cho phép thực hiện các phép toán cộng hai hàm số, nhân hai hàm số, nhân một hàm số với một hằng số tuỳ ý. Các phép toán này có thể tiếp tục được thực hiện nhiều lần trên f_i và trên các kết quả thu được. Chứng minh rằng có thể thu được hàm số 1/x từ các hàm số f_1, f_2, f_3 bằng các sử dụng các phép toán trên nhưng điều này không thể thực hiện được nếu thiếu một trong 3 hàm f_1, f_2, f_3.

Bài tập 9. Hình vuông 5 x 5 bỏ đi ô trung tâm. Chứng minh rằng có thể phủ phần còn lại bằng 8 quân trimino 1 x 3 nhưng không thể phủ được bằng 8 quân trimino hình chữ L. Tìm tất cả các giá trị k sao cho có thể phủ phần còn lại bằng k quân trimino 1 x 3 và 8-k trimino hình chữ L. 10. Trên vòng tròn ban đầu theo một thứ tự tuỳ ý có 4 số 1 và 5 số 0. Ở khoảng giữa hai chữ số giống nhau ta viết số 1 và ở khoảng giữa hai chữ số khác nhau ta viết số 0. Các số ban đầu bị xoá đi. Hỏi sau một số lần thực hiện như vậy ta có thể thu được một bộ gồm 9 số 0?

(Trích bài giảng: Các phương pháp và kỹ thuật chứng minh, chương trình Gặp gỡ Toán học tổ chức tại ĐHQG Tp HCM từ ngày 25-31/1/2010)

Nguồn: diendantoanhoc.net

Về VNMATH.COM

VNMATH hoạt động từ năm 2008 với slogan Trao đổi để học hỏi, Sẻ chia để vươn lên. Hiện nay VNMATH.COM là trang web Toán học có lượt truy cập lớn nhất Việt Nam.

Chia sẻ bài viết này


Bài viết liên quan

Không có nhận xét nào :

Để lại Nhận xét