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.
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$.
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?
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.
Ví dụ 5. Cho $A$ và $B$ là các tập phân biệt và hợp của $A$ và $B$ là tập các số tự nhiên. Chứng minh rằng với mọi số tự nhiên $n$ tồn tại các số phân biệt $a,b > n$ sao cho ${a,b,a + b } \subset A$ hoặc ${a,b,a+b} \subset B$.
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)
