Top 5 # Phương Pháp Chứng Minh Phản Chứng 10 Xem Nhiều Nhất, Mới Nhất 3/2023 # Top Trend

Tính chất.  $A Rightarrow B Leftrightarrow overline{B} Rightarrow overline{A}$ hoặc $A Rightarrow B Leftrightarrow overline{B} Rightarrow S$,  $S$ là mệnh đề hằng sai.

Phương pháp chứng minh phản chứng là một phương pháp chứng minh gián tiếp, để chứng  minh mệnh đề $A Rightarrow B$ ta chứng minh mệnh đề tương đương với nó là $overline{B} Rightarrow overline{A}$.

Điểm mạnh của phương pháp này là ta đã tạo thêm được giả thiết mới $overline{B}$, để từ đó giúp ta suy luận tiếp để giải quyết được bài toán.

Tất nhiên việc viết lại mệnh đề $overline{B}$ một cách chính xác là điều quan trọng, cái này chú ý một số quy tắt về mệnh đề.

Phương pháp này được sử dụng hầu hết trong các phân môn của toán là: đại số, số học, hình học, tổ hợp.

1. Các bài toán tổ hợp

Ví dụ 1. (Nguyên lý Dirichlet) Có $nk + 1$ viên bi, bỏ vào trong $k$ cái hộp. Chứng minh rằng có ít nhất một hộp có ít nhất là là $n+1$ viên bi.

Lời giải

 Giả sử tất cả các hộp chỉ chứa số lượng bị không vượt quá $n$ viên, khi đó tổng số viên bi không vượt quá $k cdot n$, mâu thuẫn với số bi là $kn + 1$.

Vậy phải có một hộp chứa nhiều hơn $n$ viên bi.

Ví dụ 2. Có tồn tại hay không một cách điền các số $0,1, 2, 3, cdots , 9$ vào các đỉnh của một đa giác 10 đỉnh sao cho hiệu hai số ở hai đỉnh kề nhau chỉ có thể nhận một trong các giá trị sau:$-5, -4, -3, 3, 4, 5$.

Lời giải

Giả sử có một cách ghi thỏa đề bài.

Khi đó ta thấy rằng các số $0, 1, 2, 8, 9$ không thể đứng cạnh nhau đôi một. Hơn nữa có đúng 10 số, vậy các số còn lại sẽ đứng xen kẽ giữa các số này.

Khi đó xét số 7, ta thấy số 7 chỉ có thể đứng bên cạnh số 2 trong các số ${ 0, 1, 2, 8, 9 }$, mâu thuẫn. Vậy không tồn tại cách ghi thỏa đề bài.

Ví dụ 3.  Điền các số 1,2,3,…,121 vào một bảng ô vuông kích thước $11 times 11$ sao cho mỗi ô chứa một số. Tồn tại hay không một cách điền sao cho hai số tự nhiên liên tiếp sẽ được điền vào hai ô có chung một cạnh và các tất cả các số chính phương thì nằm trong cùng một cột?

Lời giải

Giả sử tồn tại một cách điền số vào các ô thỏa yêu cầu đặt ra. Khi đó bảng ô vuông được chia thành hai phần ngăn cách nhau bởi cột điền các số chính phương. Một phần chứa $11n$ ô vuông $1 times 1$, và phần còn lại chứa $110-11n$ ô vuông $1 times 1$ , với $0 le n le 5.$

Để ý rằng các số tự nhiên nằm giữa hai số chính phương liên tiếp $a^2$ và $(a+1)^2$ sẽ cùng nằm về một phần và dó đó các số tự nhiên nằm giữa $(a+1)^2$ và $(a+2)^2$ sẽ nằm ở phần còn lại.

Số lượng các số tự nhiên nằm giữa 1 và 4, 4 và 9, 9 và 16,…,100 và 121 lần lượt là $2,4,6,8,…,20$. Do đó một phần sẽ chứa $2+6+10+14+18=50$ số, phần còn lại chứa $4+8+12+16+20=60$ số.

Cả 50 và 60 đều không chia hết cho 11, mâu thuẫn. Vậy không tồn tại cách điền số thỏa yêu cầu đề bài.

Ví dụ 4. Cho $F ={E_1, E_2, …, E_k }$ là một họ các tập con có $r$ phần tử của tập $X$. Nếu giao của $r+1$ tập bất kì của $F$ là khác rỗng, chứng minh rằng giao của tất cả các tập thuộc $F$ là khác rỗng.

Lời giải

Giả sử ngược lại, giao tất cả các tập thuộc $F$ bằng rỗng.

Xét tập $E_1 = {x_1, cdots, x_r}$. Do giao tất cả các tập thuộc $F$ là rỗng, nên với $x_k$ tồn tại một tập $E_{i_k}$ mà $x notin E_{i_k}, forall k = overline{1,r}$.

Khi đó xét giao của họ gồm $r+1$ tập $E_1, E_{i_1}, cdot, E_{i_r}$ thì bằng rỗng, mâu thuẫn.Vậy giao của tất cả các tập thuộc $F$ là khác rỗng.

Lời giải

Nếu $A$ hoặc $B$ là tập hợp hữu hạn phần tử thì chỉ cần chọn $a, b$ lớn hơn phần tử lớn nhất của $A$ hoặc $B$ ta có điều cần chứng minh.

Nếu $A, B$ là tập vô hạn, giả sử tồn tại $n$ sao cho với mọi $a, b$ thì $a, b, a+b$ không cùng thuộc $A$ hoặc $B$. (1)

Do (1) nên các số $y-x, z-y,z-x in B$, suy ra $z-y+y-x = z-x in A$ (mâu thuẫn). Vậy điều giả sử là sai, tức là ta có điều cần chứng minh.

Bài tập rèn luyện.

Bài 1. Trong mặt phẳng tọa độ thì một điểm mà hoành độ và tung độ đều là các số nguyên được gọi là điểm nguyên. Chứng minh rằng không tồn tại tam giác đều nào mà các đỉnh đều là điểm nguyên.

Bài 2. Cho $S$ là tập vô hạn các phần tử và $P(S)$ là họ các tập con của $S$. Chứng minh rằng không tồn tại một song ánh từ $S$ và $P(S)$.

Bài 3. Cho $A$ là tập con có 19 phần tử của tập ${1, 2, cdots, 106}$ sao cho không có hai phần tử nào có hiệu bằng $6, 9, 12, 15, 18$. Chứng minh rằng có 2 phần tử thuộc $A$ có hiệu bằng 3.

Bài 4. Một hình vuông $n times n$ ô được tô bởi hai màu đen trắng, sao cho trong 4 ô góc thì 3 ô được tô màu đen, 1 ô được tô màu trắng. Chứng minh rằng trong hình vuông có ô vuông $2 times 2 $ mà có số ô màu đen là số lẻ.

Bài 5.  Tập $S$ được gọi là một tập cân nếu lấy từ $S$ ra một phần tử bất kì thì các phần tử còn lại của $S$ có thể chia ra làm hai phần có tổng bằng nhau. Tìm số phần tử nhỏ nhất của một tập cân.

(còn nữa)

Like this:

Like

Loading…

Related

Điều hướng bài viết

Chuyên đề 10:

PHƯƠNG PHÁP PHẢN CHỨNG VÀ CÁCH CHỨNG MINH BẰNG PHƯƠNG PHÁP PHẢN CHỨNGI – Lý thuyết: (1 tiết )( Phương pháp chứng minh bằng phản chứng có thể tóm tắt như sau:– Để chứng minh một mệnh đề P là đúng, ta giả sử ngược lại rằng mệnh đề P là sai. Từ giả sử P sai, kết hợp với giả thiết, bằng cách suy luận từ những kiến thức đã học, ta suy ra được một kết quả vô lí (trái với giả thiết hoặc trái với các tiên đề, hoặc trái với định lí mà ta đã học). Như vậy, ta kết luận P đúng.– Ví dụ: Chứng minh rằng hai đường thẳng phân biệt cùng song song với một đường thẳng thứ ba thì song song với nhau.

Giải

KL a

– Giả sử a và b không song song với nhau, nghĩa là chúng cắt nhau tại một điểm M. Như vậy, qua điểm M ta có hai đường thẳng phân biệt a và b cùng song song với đường thẳng c. Điều này trái với với tiên đề Ơclit (vì nội dung tiên đề Ơclit là: Qua một điểm ở ngoài một đường thẳng chỉ có một đường thẳng song song với đường thẳng đó).– Vậy: a phải song song với b (a

II – Bài tập: (4 tiết)Bài 1: Cho hai đường thẳng xx’ và yy’ giao nhau tại một điểm O. Ta nhận thấy chúng tạo thành bốn góc, kề bù với ; kề bù với . Như vậy, ta có: + + + = 2.1800 = 360o. Chứng minh rằng trong bốn góc , , và phải có một góc không lớn hơn 900.

Bài 2: Cho một góc nhọn . Chứng minh rằng nếu qua một điểm A thuộc miền trong của góc ta kẻ một đường thẳng a song song với Oy thì đường thẳng này phải cắt cạnh Ox tại một điểm.

Bài 3: Cho đoạn thẳng AB, gọi I là trung điểm của AB. Lấy một điểm M ngoài đường thẳng AB. Giả sử MA < MB. Chứng minh rằng:a) và không bằng nhau.b) Nối MI thì đường thẳng MI không vuông góc với đường thẳng AB.

Bài 4: Cho tam giác ABC có 3 góc đều là góc nhọn. Đường cao AD kẻ từ đỉnh A cắt trung tuyến BE kẻ từ đỉnh B và phân giác CF của góc C theo thứ tự tại các điểm M, N; BE và CF cắt nhau tại P. Chứng minh rằng tam giác MNP không phải là tam giác đều.

III. Bài giải:Bài 1: (1 tiết)

GT x’x cắt y’y tại điểm O

KL Trong các góc tạo ra có ít nhất một góc < 900

– Giả sử không có góc nào trong bốn góc trêncó số đo nhỏ hơn 900. Như vậy tổng số đo củacả bốn góc phải lớn hơn 4.900 = 3600.– Điều này vô lí.– Vậy: phải có ít nhất một góc không lớn hơn 900.

Bài 2: (1 tiết)

GT Góc nhọn xOy; A thuộc miền trong. a qua A và a

KL a cắt Ox

– Giả sử a không cắt Ox. Vậy thì có hai khả năng xảy ra:a/ Đường thẳng a cắt tia đối của tia Ox tại điểm A’. Như vậy hai điểm A, A’ nằm trong hai nửa mặt phẳng đối nhau bờ là đường thẳng chứa tia Oy. Đường thẳng a đi qua A, A’ phải cắt Oy. Điều này trái với giả thiết là a// Oy.b/ Đường thẳng a không cắt đường thẳng Ox. Như vậy vì điểm A thuộc miền trong của góc xOy, nên A không thuộc Ox. Vậy A

Bài 3: (1 tiết)

GT I là trung điểm của AB. M AB, MA < MB.

KL 1. không = 2. MI không với AB.

– Giả sử = . – Hai tam giác MIA và MIB có:IA = IB = IM: cạnh chung – Vậy: MIA = MIB (trường hợp c-g-c). MA = MB– Điều này trái với giả thiết MA <

1). Kiến thức: Học sinh hiểu được phương pháp chứng minh phản chứng dựa trên suy luận toán họcsau:

Nhờ phương pháp này việc chứng minh một số mệnh đề toán học được đơn giản hóa .

2). Kỹ năng: Từ sự nắm vững cơ sở lý luận của phép chứng minh phản chứng, học sinh sử dụng được

phương pháp này một cách thành thạo và chính xác .

II . Phương tiện dạy học :

III . Tiến trình dạy học trên lớp :

1). Ổn định lớp và kiểm tra bài củ : bài 13 tr. 30 , bài 14 tr. 31 trong SGK .

2). Phần mở bài : Trong toán học , việc chứng minh trực tiếp mệnh đề P đúng đôi khi gặp nhiều khó

vướng mắc này , người ta dùng phương pháp chứng minh phản chứng .

Tiết 4 : PHƯƠNG PHÁP CHỨNG MINH PHẢN CHỨNG . I . Mục tiêu : 1). Kiến thức: Học sinh hiểu được phương pháp chứng minh phản chứng dựa trên suy luận toán họcsau: Nhờ phương pháp này việc chứng minh một số mệnh đề toán học được đơn giản hóa . 2). Kỹ năng: Từ sự nắm vững cơ sở lý luận của phép chứng minh phản chứng, học sinh sử dụng được phương pháp này một cách thành thạo và chính xác . II . Phương tiện dạy học : III . Tiến trình dạy học trên lớp : 1). Ổn định lớp và kiểm tra bài củ : bài 13 tr. 30 , bài 14 tr. 31 trong SGK . 2). Phần mở bài : Trong toán học , việc chứng minh trực tiếp mệnh đề P đúng đôi khi gặp nhiều khó vướng mắc này , người ta dùng phương pháp chứng minh phản chứng . 3).Nghiên cứu bài học mới : Thời lượng Kiến thức cơ bản VD 1 : (SGK) _ Phương pháp : + GS : A đúng , B sai . + dùng giả thiết và kiến thức toán học để lập luận và suy ra A sai II.Chứng minh mệnh đề P đúng : VD: ( SGK ) _ Phương pháp : + GS : sai . + suy ra điều mâu thuẫn . + KL : P đúng . Hoạt động của GV và HS Thầy :_hướng dẫn HS các bước suy luận của phép chứng minh trong ví dụ 1. Trò : _ từ sự gợi ý của thầy ,biết tổng quát hóa vấn đề từ đó suy ra phương pháp chung của phép chứng minh . Trò : _ dùng phương pháp để tự chứng minh vd 4). Củng cố : Chứng minh các mệnh đề sau bằng phương pháp phản chứng : 2) Cho n ỴN* : CM nếu : lẻ thì n lẻ . 3) Nếu a+b < 2 thì một trong hai số a và b nhỏ hơn 1 . 4) Một tam giác không phải là tam giác đều thì nó có ít nhất một góc (trong) nhỏ hơn 60 độ , 5) Nếu x ¹ -1 và y ¹ -1 thì x + y + xy ¹ -1

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

4.doc

Trong bài này, chúng ta tiếp tục tìm hiểu thêm và phương pháp quy nạp. Ngoài dạng quy nạp như đã biết ta còn một số dạng quy nạp khác như: Quy nạp mạnh, quy nạp bước nhảy, quy nạp lùi.

Quy nạp mạnh được phát biểu như sau: Để chứng minh mệnh đề $P(n)$ đúng với mọi số tự nhiên $n$, ta thực hiện theo hai bước sau:

Chứng minh $P(n)$ đúng với $n=1$.

Giả sử $P(n)$ đúng với $1, 2, cdots, n$. Chứng minh $P(n+1)$ đúng.

Ví dụ 1. Cho $x$ thỏa $x+dfrac{1}{x}$ là số nguyên. Chứng minh rằng $x^n+dfrac{1}{x^n}$ là số nguyên với mọi $n$.

Lời giải. 

Ta có $x + dfrac{1}{x}$ là số nguyên  đúng (theo giả thiết).

Giả sử $x^k + dfrac{1}{x^k}$ là số nguyên với mọi $k = overline{1,n}$. Ta cần chứng minh $x^{n+1} + dfrac{1}{x^{n+1}}$.

$(x^{n+1} + dfrac{1}{x^{n+1}} = (x+dfrac{1}{x})(x^n + dfrac{1}{n})  – (x^{n-1}+dfrac{1}{x^{n-1}})$.

Theo giả thiết quy nạp thì $x^{n+1} + dfrac{1}{x^{n+1}}$ là số nguyên.

Vậy ta có $x^n + dfrac{1}{x^n}$ là số nguyên với mọi $n$.

Dạng kế tiếp là Quy nạp bước nhảy  được phát biểu như sau: Chứng minh mệnh đề $P(n)$ đúng với mọi $n$, ta làm như sau:

Chứng minh $P(1), P(2), cdots, P(k)$ đúng.

Giả sử $P(n)$ đúng. Ta chứng minh $P(n+k)$ đúng.

Ví dụ 2. Chứng minh rằng với mọi số tự nhiên $M$ tồn tại số tự nhiên $n$ và cách chọn các dấu $+$ hoặc $-$ sao cho

$M = pm 1^2 pm 2^2 cdots pm n^2$.

Lời giải.

Khi $M = 1, 2, 3, 4$ ta có $1 = 1^2$, $2 = -1^2-2^2-3^2+4^2$, $3 = -1^2+2^2$ và $4 = 1^2-2^2-3^2+4^2$.

Giả sử đúng với $M$, tức là tồn tại $n$ thỏa $M = pm 1^2 pm 2^2 cdots pm n^2$, khi đó $M + 4 = pm 1^2 pm 2^2 cdots pm n^2 +(n+1)^2-(n+2)^2-(n+3)^2 + (n+4)^2$.

Ví dụ 3.  Chứng minh rằng với mọi số tự nhiên $n$ thì phương trình $a^2 + b^2 = c^n$ luôn có nghiệm trong tập các số nguyên dương.

Lời giải. 

Rõ ràng nếu $n=1, 2$ thì phương trình luông có nghiệm nguyên dương.

Giả sử phương trình có nghiệm nguyên dương là $a, b, c$ với $n$ nào đó, tức là $a^2 + b^2 = c^n$.

Khi đó với $n+2$ thì xét $(ac), (bc), c$: $(ac)^2+(bc)^2 = c^2 (a^2+b^2) = c^{n+2}$.

$(ac, bc, c$ là nghiệm.

Vậy phương trình luôn có nghiệm với mọi $n$.

Dạng kế tiếp là Quy nạp lùi được phát biểu như sau:

Chứng minh $P(a_i)$ đúng với dãy $(a_i)$ là dãy con tăng thực sự của tập các số tự nhiên.

Giả sử $P(n)$ đúng, chứng minh $P(n-1)$ đúng.

Ví dụ 4. 

a) Hãy chỉ ra cách sắp 8 số nguyên dương đầu tiên 1, 2, …, 8 thành một dãy $a_1, a_2 ,…, a_8$ sao cho 2 số $a_i, a_j$ bất kì $(i < j)$ thì mọi số trong dãy nằm giữa $a_i$ và $a_j$ đều khác $dfrac{a_i + a_j}{2}$. b) Chứng minh rằng với $N$ số nguyên dương đầu tiên $1, 2, …, N$ luôn tìm được cách sắp thành dãy $a_1, a_2, …, a_N$ sao cho dãy thỏa mãn điều kiện như câu a). Lời giải.

a) Một cách xếp thỏa đề bài là 26481537. b)

Bước 1.Ta chứng minh bằng quy nạp với $n = 2^k$ thì luôn tồn tại một cách xếp thỏa đề bài.

Nếu $k = 1$, hiển nhiên đúng. Giả sử luôn tồn tại một cách xếp thỏa đề bài với $n = 2^k$, cách xếp đó là $a_1, a_2, …, a_n$. Ta chứng minh tồn tại một cách xếp với $n = 2^{k+1}$. Thật vậy xét hoán vị $(2a_1, 2a_2,…, 2a_n, 2a_1-1, 2a_2-1, …, 2a_n-1)$ là một hoán vị của $1, 2, …, 2^{k+1}$. Ta chứng minh hoán vị trên thỏa đề bài.

Ta có nếu $a_i, a_j in {2a_1, 2a_2, …, 2a_n}$ theo giả thiết quy nạp không có số nào nằm giữa $a_i, a_j$ bằng $dfrac{1}{2}(a_i+a_j)$.

Nếu $a_i in {2a_1, …, 2a_n}, a_j in {2a_1-1, 2a_2-1, …, 2a_n-1}$ thì $dfrac{1}{2}(a_i +a_j)$ không phải số nguyên.

Nếu $a_i, a_j in {2a_1-1, 2a_2-1, …, 2a_n-1}$ theo giả thiết quy nạp thì cũng có số nào nằm giữa $a_i, a_j$ bằng $dfrac{1}{2}(a_i + a_j)$.

Vậy bài toán đúng với $n = 2^k$.(1) Bước 2. Nếu bài toán đúng với $n$, ta chứng minh bài toán đúng với $n-1$.

Xét các số $a_1, a_2, …, a_n$ là một hoán vị thỏa đề bài của $1,2,…,n$.

Khi đó nếu xóa bất kì số nào trong các số $a_1, …, a_n$ thì dãy còn lại vẫn thỏa điều kiện. (2) Từ (1) và (2) ta có điều cần chứng minh.

Quy nạp lùi cũng là một trong những cách chứng minh bất đẳng thức Cauchy tổng quát: $dfrac{a_1+a_2 + cdots+a_n}{n} geq sqrt[n]{a_1a_2cdots a_n}$.

Bài tập rèn luyện.

Bài 1. Ta gọi tổng các số tự nhiên từ 1 đến n là số tam giác. Chứng minh rằng tồn tại vô hạn các số tam giác đồng thời là số chính phương.

Bài 2. (Chọn đội tuyển PTNK 2014)Tìm số nguyên dương $n$ lớn nhất thỏa mãn các điều kiện sau:

$n$ không chia hết cho 3;

Bảng vuông $n times n$ ô không thể được phủ kín bằng 1 quân tetramino $1 times 4$ và các quân trimino kích thước $1 times 3$. Trong phép phủ các quân tetramino và trimino được phép quay dọc nhưng không được phép chườm lên nhau hoặc nằm ngoài ra bảng vuông.

Bài 3. Có $n$ số tự nhiên từ 1 đến $n$ được viết thành một dòng theo một thứ tự nào đó. Mỗi bước thực hiện biến đổi như sau: nếu số đầu tiên là $k$ thì $k$ số đầu tiên sẽ được viết theo thứ tự ngược lại. Chứng minh rằng sau hữu hạn bước thì số đầu tiên của dòng là số 1.

Bài 4. Trong cuộc họp có $2n$ ($n geq 2$) người, một số người bắt tay nhau và người ta đếm được có $n^2+1$ cái bắt tay. Chứng minh rằng có $n$ bộ ba, mà mỗi bộ ba đôi một bắt tay nhau.

Bài 5. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số nguyên $x, y, z$ phân biệt sao cho $x^2+y^2+z^2 = 14^n$.

Bài 6. Trong một giải đấu tennis có 10 người tham dự, hai đối thủ gặp nhau đúng một trận. Chứng minh rằng, sau khi kết thúc giải có thể sắp xếp các tay vợt thành một hàng mà người đứng trước thắng người đứng sau.

Like this:

Like

Loading…

Related

Điều hướng bài viết