Ta dùng tương đương logic sau $A \Rightarrow B \Leftrightarrow \overline{B} \Rightarrow \overline{A}$ để thiết lập phương pháp chứng minh Phản chứng.
Để chứng minh mệnh đề $A \Rightarrow B$ đúng, ta có thể thực hiện các bước sau (Phương pháp phản chứng)
- Giả sử mệnh đề $B$ sai.
- Chứng minh $A$ sai, hoặc một điều vô lý.
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. Cho $n$ là số tự nhiên $n>3$. Chứng minh rằng $2^n+1$ không chia hết cho $2^m-1$ với mọi số tự nhiên $m$ sao cho $2 < m \leq n$.
Lời giải
Giả sử tồn tại $m,n$ sao cho $2^n+1$ chia hết cho $2^m-1$ với $2 < m < n$.
Ta có $2^{n-m}(2^m-1) \vdots 2^m-1$, suy ra $2^n -2^{n-m} \vdots 2^m-1$, mà $2^n+1 \vdots 2^m-1$ suy ra $2^{n-m} +1$ chia hết cho $2^m-1$.
Lý luận tương tự ta có $2^{n-km} + 1$ chia hết cho $2^m-1$.\\ Giả sử $n = km + q, 0\leq q <m$. Chọn $k$ như trên ta có $2^q +1$ chia hết cho $2^m-1$. Mà $q < m$ nên $2^q + 1 =2^m-1$,giải ra $q = 1, m=2$ (vô lý).
Ví dụ 3. Cho tập $B = {1, 2, 3, …, 16}$. Người ta ghi các số của tập B thành một vòng tròn (mỗi số ghi một lần). Hỏi có cách ghi để tổng thỏa:
a) Tổng của hai số kế nhau bất kì lớn hơn hoặc bằng 17 được không? Tại sao?
b) Tổng của ba số kế nhau bất kì lớn hơn 24 được không? Tại sao?
Lời giải
a) Giả sử có cách ghi thỏa đề bài xét hai số đứng kề số 1, gọi là $a, b$ như sau $a1b$, khi đó $a+1 \geq 17, b+1 \geq 17$, suy ra $a = b= 16$ vô lí. Do đó không có cách ghi thỏa đề bài.
b) Giả sử có cách ghi thỏa đề bài: 3 số liên tiếp bất kì có tổng lớn hơn 24. Khi đó bỏ số 16 ra, còn lại 15 số chia làm 5 nhóm rời nhau thì tổng lớn hơn $24 \times 5 = 120$, trong khi đó $1 + 2 + \cdots + 15 = 120$ vô lí.
Ví dụ 4. 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ụ 5. Đ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ụ 6. 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.
Ví dụ 7. 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$.
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)
- Ta chọn các số $x, y, z \in A$ sao cho $x < y < z$ và $z-y, y-x > n$.
- 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.
Ví dụ 8. 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.
Lời giải
- Giả sử tồn tại tam giác đều có các đỉnh là các điểm nguyên.
Xét hình chữ nhật có các đỉnh là các điểm nguyên, sao cho đỉnh của tam giác đều thuộc cạnh của hình chữ nhật. Khi đó dễ dàng suy ra diện tích tam giác đều là số hữu tỷ.
- Mặt khác diện tích tam giác đều $S = \dfrac{a^2\sqrt{3}}{4}$ là số vô tỷ, vì $a$ là số nguyên, $\sqrt{3}$ là số vô tỷ.
Ví dụ 9. 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.
Lời giải
- Xét các phần tử thuộc $A$ theo mod 3 thì có ít nhất 7 phần tử có cùng 0, 1, 2 mod 3. Xét tập B có 7 hoặc nhiều hơn phần tử có cùng số dư khi chia cho 3. Khi đó hiệu 2 số bất kì là số chia hết cho 3.
- Giả sử không có hai số có hiệu bằng 3, khi đó hiệu hai số sẽ từ 21 trở đi. Giả sử $a_1 < a_2 < a_3 < a_4 < a_5 < a_6 < a_7 \in B$. Ta có $a_2 – a_1 \geq 21, \cdots, a_7 – a_6 \geq 21$, suy ra $a_7 \geq 1 + 21\times 6 = 127$ mâu thuẫn.
- Vậy có 2 số có hiệu bằng 3.
Ví dụ 10. 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ẻ.
Lời giải
- Giả sử ngược lại, không có hình vuông $2 \times 2$ nào mà số ô đen là lẻ mà đều là số chẵn.
- Lấy tổng các ô đen của các hình vuông $2\times 2$, khi đó ta được một số chẵn các ô đen.
- Mặt khác, mỗi ô vuông trên cạnh (khác ô góc) được tính 2 lần (vì có 2 hình vuông $2 \times 2$ chứa nó, các ô vuông bên trong được tính 4 lần, các ô góc được tính 1 lần, do đó số ô đen là một số lẻ. Mâu thuẫn.
- Vậy có ít nhất một hình vuông $2 \times 2$ ô đen là một số lẻ.
Bài tập rèn luyện
Bài 1. Giải các bài toán sau bằng phương pháp phản chứng
a) Chứng minh rằng $\sqrt{2}$ là một số vô tỷ.
b) Chứng minh rằng tổng của một số hữu tỷ và một số vô tỷ là số vô tỷ.
c) Chứng minh tích của một số hữu tỷ và một số vô tỷ là số vô tỷ.
d) Tổng, tích hai số vô tỷ có luôn là số vô tỷ không? Tại sao?
e) Cho 15 số thỏa mãn tổng của 8 số bất kì lớn nhơn tổng của 7 số còn lại. Chứng minh tất cả các số đã cho đều dương.
f) Từ 8 số nguyên dương không lớn hơn 20, chứng minh rằng có thể chọn ra 3 số $x, y, z$ là độ dài 3 cạnh của một tam giác.
Bài 2. Có thể chia tập $X = {1, 2, …, 17}$ thành hai tập rời nhau sao cho tích các phần tử thuộc tập này bằng tổng các phần tử thuộc tập kia?
Bài 3. Có tồn tại hay không cách chia tập hợp $X = {1, 2, …, 2017}$ thành các tập hợp sao cho trong mỗi tập đó thì phần tử lớn nhất bằng tổng các phần tử còn lại.
Bài 4. Một tập hợp có ít nhất 3 số nguyên dương phân biệt được gọi là \textbf{tập đều} nếu có ít nhất một số lẻ và khi bỏ đi một phần tử bất kì thì các số còn lại có thể chia thành hai tập hợp mà tổng các số trong hai tập hợp đó bằng nhau.
a) Chứng minh không có tập đều nào có 3 phần tử.
b) Chứng minh số phần tử của tập đều luôn là một số lẻ.
c) Có tồn tại hay không một tập đều có 5 phần tử? Tại sao?
