Chương 1. Phương pháp quy nạp 2) Quy nạp. Giả sử với n = k khẳng định đã đúng, nghĩa là k đường thẳng tùy ý cùng đi qua một điểm M đã chia mặt phẳng thành 2k phần khác nhau. Xét n = k + 1 đường thẳng khác nhau tùy ý cùng đi qua một điểm.
Kí hiệu các đường này, một cách tương ứng bằng δ1 , δ2 , · · · , δk , δk+1. Theo giả thiết quy nạp k đường thẳng δ1 , δ2 , · · · , δk đã chia mặt phẳng thành 2k phần khác nhau. δs M δk+1 δt Vì các đường thẳng đều khác nhau và cùng đi qua điểm M , nên tồn tại các chỉ số s, t (1 ≤ s, t ≤ k) để δk+1 là đường thẳng duy nhất nằm trong góc được lập nên bởi δs và δt. Khi đó δk+1 chia hai phần mặt phẳng được giới hạn bởi δs và δt thành bốn phần.
Bởi vậy k + 1 đường thẳng δ1 , δ2 , · · · , δk , δk+1 chia mặt phẳng thành 2k − 2 + 4 = 2k + 2 = 2 (k + 1) phần khác nhau. Khẳng định được chứng minh. 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2 Phương pháp chứng minh phản chứng Chứng minh là một nét đặc trưng của toán học, tạo ra sự khác biệt giữa toán học với các môn khoa học khác. Nắm bắt phương pháp và kĩ thuật chứng minh cũng là yêu cầu bắt buộc đối với học sinh nói chung.
Các phương pháp và kĩ thuật chứng minh rất phong phú: Từ chứng minh trực tiếp đến gián tiếp, từ chứng minh bằng quy nạp đến chứng minh bằng phản chứng, từ ví dụ đến phản ví dụ, từ xây dựng đến không xây dựng. Trong bài luận văn này xin được đề cập đến phép chứng minh phản chứng, một trong những phương pháp chứng minh kinh điển và quan trọng nhất của toán học. Chứng minh phản chứng có thể nói là một trong những vũ khí quan trọng nhất của toán học. Nó cho phép chúng ta chứng minh sự có thể và không 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.1 Cơ sở lý thuyết Cơ sở lý thuyết của phương pháp phản chứng là các định luật trong logic: Gọi p, q, r là các mệnh đề toán học nào đó, khi đó Định lý 2. 17 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2. Phương pháp chứng minh phản chứng 2.
Các định luật trên có thể được chứng minh chẳng hạn bằng phương pháp lập bảng chân lý hoặc phương pháp biến đổi tương đương. Chẳng hạn, ta có thể chứng minh (2.1) như sau: (p ∧ q ⇒ r) ⇔ p ∧ q hoặc r (do a⇒b⇔a hoặc b) ⇔p hoặc q hoặc r (do a∧b⇔a hoặc b) ⇔(p hoặc r) hoặc q (giao hoán, kết hợp và r ⇔ r) ⇔p ∧ r hoặc q ⇔(p ∧ r ⇒ q) đpcm.2 Nội dung của phương pháp phản chứng Để chứng minh khẳng định p ⇒ q bằng phương pháp phản chứng ta giả sử q sai, tức là q là mệnh đề đúng. Nếu từ đó thu được một điều vô lý (vl) thì điều đó chứng tỏ giả sử của ta là sai, tức là q đúng. Khi xây dựng mệnh đề phản chứng q ta cần nhớ 1.
Nếu p(x) := f (x)Rg(x), thì p(x) là : f (x)Rg(x) trong đó, R và R được xác định như sau: 18 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2. Phương pháp chứng minh phản chứng R = 6= > ≥ < ≤ R 6= = ≤ < ≥ > Ngoài ra còn có: Định lý 2. Cho A là một công thức logic mà trong đó chỉ chứa các phép toán: Phủ định, ∧, hoặc đối với các mệnh đề: p1 , p2 , · · · , pn. Âm bản của A, kí hiệu là Ad là một công thức thu được từ A bằng cách thay pj ∼ pj ; pj ∼ pj , ∨ ∼ ∧; ∧ ∼ ∨.
Khi đó: A ⇔ Ad Phương pháp phản chứng còn dựa trên nguyên lý Dirichlet do nhà toán học Đức nổi tiếng Peter Dirichlet (1805-1859) đề xuất, mà dạng đơn giản nhất của nguyên lý này được phát biểu như sau: "Không thể nhốt 7 chú thỏ vào 3 cái lồng sao cho mỗi lồng không có quá hai chú thỏ". Nói cách khác "Nếu nhốt 7 chú thỏ vào 3 cái lồng, thì phải có ít nhất một lồng có không ít hơn 3 chú thỏ".3 Trình bày lời giải của phương pháp phản chứng Bài toán: Chứng minh p ⇒ q Lời giải: Giả sử ngược lại, q sai, tức là q. Vậy giả sử của ta là sai, tức là q đúng. Ngoài ra, ta sẽ giải một số bài toán bằng phương pháp phản chứng dựa trên nguyên lý Dirichlet.4 Một số ví dụ minh họa Ví dụ 2.
Cho f (x) = ax2 + bx + c.2) Chứng minh rằng ∃x ∈ [0; 1], |f (x)| > 1 (2.3) Lời giải: Ta sẽ chứng minh bằng phương pháp phản chứng.3) sai, tức là ∀x ∈ [0; 1], |f (x)| ≤ 1 (2.4) 19 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2. Phương pháp chứng minh phản chứng Chọn x = 0; 21 ; 1, từ (2.4) ta được |c| ≤ 1 và: |a + b + c| ≤ 1 a b 4 + 2 +c ≤1 Suy ra |a| + |b| + |c| ≤ 17 Đó là điều vô lý (trái với (2. Vậy giả sử của ta là sai, tức là (2. Chứng minh tập các số nguyên tố P là tập vô hạn.
Giả sử ngược lại, tập P là hữu hạn. Giả sử P = {p1 , p2 , · · · , pn }. Khi đó, tồn tại số nguyên tố lớn nhất. Gọi đó là pn.
Tức là: pn ∈ P và ∀p ∈ P, p ≤ pn. Ta có, x ∈ N; x không chia hết cho các số p1 ; p2 ; .pj nào đó thì 1. Mà hiển nhiên, x > pn. Đó là điều vô lý (trái với cách chọn pn ).
Vậy điều giả sử của ta là sai, tức là P là tập vô hạn. Có thể chia các số tự nhiên từ 1 đến 21 thành các nhóm đôi một rời nhau, sao cho trong mỗi nhóm số lớn nhất bằng tổng các số còn lại hay không? Lời giải: Giả sử chia được. Khi đó tổng các số ở mỗi nhóm là một số chẵn (bằng hai lần số lớn nhất). Vậy tổng của 21 số đã cho là một số chẵn (vì các nhóm đôi một rời nhau và tổng của các số chẵn là số chẵn).
Nhưng tổng của 21 số đó là 21.11 = 231 là số lẻ. Điều vô lý này chứng tỏ giả sử của ta là sai, tức là không chia được thành các nhóm thỏa mãn yêu cầu đề bài. Có thể tìm được hay không 5 số nguyên, sao cho các tổng của hai số một trong 5 số đó lập thành 10 số nguyên liên tiếp? Lời giải: Giả sử tìm được 5 số như vậy. Gọi s là tổng của 5 số đó và n là giá trị nhỏ nhất của tổng các cặp hai số.
Khi đó 10 số nguyên liên tiếp nói trong đề bài là n, n + 1,. , n + 9 20 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2. Phương pháp chứng minh phản chứng Ta tính tổng τ của 10 số đó theo hai cách khác nhau: Một mặt, τ = n + (n + 1) + (n + 2) +. Từ đó suy ra 4s = 5 (2n + 9) là điều vô lý.
Vậy giả sử ban đầu là sai, tức là không thể chọn được 5 số thỏa mãn yêu cầu bài ra. Cho ba điểm A, B, C phân biệt trên mặt phẳng. Chứng minh rằng nếu tồn tại điểm G thuộc mặt phẳng đó thỏa mãn: −→ −−→ −→ − → GA + GB + GC = 0 thì điểm G đó là duy nhất. Lời giải: Ta chứng minh bằng phương pháp phản chứng.
Giả sử còn có điểm O 6= G thỏa mãn yêu cầu bài toán, tức là −→ −−→ −→ − → OA + OB + OC = 0 Ta có −→ −−→ −→ − → GA + GB + GC = 0 −→ −→ −→ −−→ −→ −→ − → ⇔ GO + OA + GO + OB + GO + OC = 0 −→ −→ −−→ −→ − → ⇔ 3GO + OA + OB + OC = 0 −→ −−→ −→ → − Do OA + OB + OC = 0 , suy ra −→ − → 3GO = 0 −→ − → ⇔ GO = 0 ⇔G≡O Vậy G là duy nhất. (IMO 1982) Cho phương trình x3 − 3xy 2 + y 3 = n, n ∈ N∗ (2.5) 1) Chứng minh rằng nếu (2.5) có nghiệm nguyên thì nó không có nghiệm nguyên duy nhất. 2) Tìm nghiệm nguyên của (2. 21 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2.
Phương pháp chứng minh phản chứng Lời giải: 1) Dễ dàng biến đổi x3 − 3xy 2 + y 3 = (y − x)3 − 3 (y − x) x2 + (−x)3 = (−y)3 − 3 (−y) (x − y)2 + (x − y)3 Từ đó ta có: Nếu (x; y) là một nghiệm của (2.5) thì (y − x; −x) , (−y; x − y) cũng là các nghiệm của (2. Ba nghiệm này đôi một khác nhau vì nếu có hai nghiệm nào đó bằng nhau thì ta có x = y = 0 là điều vô lý do n > 0.5) có nghiệm, thì nó có ít nhất ba nghiệm phân biệt, tức là (2.5) không thể có nghiệm duy nhất. 2) Với n = 2005 giả sử (2. Ta viết các nghiệm theo (mod 3), phương trình đã cho trở thành x3 + y 3 = −1 (mod 3) ⇒ x + y = −1 (mod 3).
Do vậy ta có các trường hợp sau: (i)x ≡ 0 (mod 3) và y ≡ −1 (mod 3); (2.8) Trong trường hợp (i) đặt x = 3m, y = 3n − 1, thay vào phương trình đã cho ta được V T ≡ −1 (mod 3) còn V P = 2005 ≡ −2 (mod 9) ⇒ vô lý. Trong trường hợp (ii), do (y − x; −x) cũng là nghiệm, mà y − x ≡ 0 (mod 3) và −x ≡ −1 (mod 3) nên ta cũng thu được một điều vô lý. Tương tự từ trường hợp (iii) ta cũng thu được một điều vô lý. Vậy với n = 2005 phương trình đã cho không có nghiệm nguyên.
Tìm tất cả những hàm số f (x) : R+ → R+ , là toàn ánh và thỏa mãn đồng thời hai điều kiện sau: 1) f (xf (y)) = yf (x), ∀x, y ∈ R+. Lời giải: Do f (x) là toàn ánh và 1 ∈ R+ nên ∃y0 ∈ R+ : f (y0 ) = 1.