Phương pháp chứng minh phản chứng

Nguyễn Tăng Vũ

Phương pháp phản chứng trong toán học còn được gọi là phương pháp chứng minh bằng mâu thuẫn. Nếu ta muốn chứng minh kết luận của bài toán là đúng thì cần phải chứng minh điều ngược lại với giả thiết là sai.

1/ Ví dụ:

Vd 1. 

Chứng minh rằng $\sqrt{2}$ là một số vô tỷ.

Lời giải

Giả sử $\sqrt{2}$ là số hữu tỉ. Khi đó tồn tại $a,b\in \mathbb{N}^*$ sao cho $\sqrt{2}= \dfrac{a}{b}$ với $(a,b)=1$

Ta có: $(\sqrt{2})^2=\left(\dfrac{a}{b}\right)^{2}$ hay $a^{2}=2 b^{2}\quad (1)$

Suy ra a là số chẵn, ta có: $\mathrm{a}=2 \mathrm{c}$ với $c\in Z$

Thay $\mathrm{a}=2 \mathrm{c}$ vào (1) ta được: $(2 c)^{2}=2 b^{2}$ hay $b^{2}=2 c^{2}$

Do đó, b là số chẵn

Hai số a và $b$ đều số chẵn $\Rightarrow$ Mâu thuẫn với $(1)$

Vậy $\sqrt{2}$ là số vô tỉ.

Vd 2. 

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

Lời giải

Giả sử tổng của số hữu tỉ a vs số vô tỉ b là số hữu tỉ c, ta có: $\mathrm{b}=\mathrm{c}-\mathrm{a}$

Mà hiệu của 2 số hữu tỉ phải là số hữu tỉ nên $b$ là số hữu tỉ

$\Rightarrow$ Mâu thuẫn vs giả thiết

Vậy tổng của 1 số hữu tỉ với 1 số vô tỉ là 1 số vô tỉ.

Vd 3. (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 đều chứa số bi không vượt quá $n$ viên, khi đó tổng số bi không vượt quá $nk$, mâu thuẫn. Vậy phải có một hộp chứa nhiều hơn $n$ viên bi $\Rightarrow$ đpcm.

2/ Bài tập

Bài 1. 

Cho 15 số thỏa mãn tổng của 8 số bất kì lớn hơn tổng của 7 số còn lại. Chứng minh tất cả các số đã cho đều dương.

Lời giải

Gọi 15 số đã cho là $a_1<a_2<a_3<\cdots <a_{15}$. Theo giả thiết, ta có:

$$a_9+a_10+\cdots +a_{15}<a_1+a_2+\cdots +a_8$$

Mà $$a_9+a_10+\cdots +a_{15}>a_2+\cdots +a_8$$

nên $0<a_1\Rightarrow 15$ số đã cho đều dương.

Bài 2. 

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.

Lời giải

Gọi 8 số nguyên dương không lớn hơn 20 là $a_{1}, a_{2}, a_{3}, \ldots, a_{8}$

$$ \text { với } 1 \leq a_{1} \leq a_{2} \leq a_{3} \leq a_{4} \leq \ldots \ldots \leq a_{8} \leq 20 $$

Nhận thấy rằng với ba số nguyên dương $a, b, c$ thỏa mãn $a \geq b \geq c$ và $b+c>a$ thì khi đó $a, b, c$ là độ dài 3 cạnh tam giác.

Giả sử trong các số $a_{1}, a_{2}, a_{3}, a_{4}, \ldots . a_{8}$ không chọn được 3 số nào là độ dài 3 cạnh của tam giác thì ta có:

$$a 3 \geq a 1+a 2 \geq 1+1=2$$

$$a 4 \geq a 2+a 3 \geq 1+2=3$$

$$a 5 \geq a 3+a 4 \geq 2+3=5$$

$$a 6 \geq a 4+a 5 \geq 3+5=8$$

$$a 7 \geq a 5+a 6 \geq 5+8=13$$

$$a 8 \geq a 6+a 7 \geq 13+8=21$$

$\Rightarrow$ Trái với giả thiết

Vậy điều giả sử là sai

$\Rightarrow$ đpcm.

Bài 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ử tồn tại cách ghi thỏa mãn. Khi đó, gọi 2 số kề với 1 là a và b.

Theo giả thiết, ta có:

$\left\{\begin{array}{l} 1 + a \geqslant 17  \\1 + b \geqslant 17  \end{array} \right. \Rightarrow \left\{\begin{array}{l}  a \geqslant 16 \\ b \geqslant 16 \end{array} \right. \Rightarrow$ Mâu thuẫn.

Vậy không tồn tại cách ghi thỏa mãn.

b/ Giả sử tồn tại cách ghi thỏa mãn.

Khi đó, ta tách số 16 ra và chia 15 số còn lại thành 5 bộ 3 số kề nhau. Và tổng của 16 số này phải lớn hơn hoặc bằng: $16+5\cdot 25=141$

Mà $1+2+3+\cdots 16=136 \Rightarrow $ Mâu thuẫn

Vậy không tồn tại cách ghi thỏa mãn.

Bài 4. 

Có thể chia tập $X = {1, 2, …, 2023}$ thành hai tập rời nhau sao cho tổng các phần tử thuộc tập này bằng 2 lần tổng các phần tử thuộc tập kia?

Lời giải

Giả sử có thể chia tập $X$ thành hai tập rời nhau $A$ và $B$ sao cho tổng các phần tử thuộc A bằng 2 lần tổng các phần tử thuộc B.

Khi đó, tổng các phần tử của 2 tập hợp này phải chia hết cho 3.

Mà ta có: $1+2+3+\cdots +2023=\dfrac{2023\cdot 2024}{2}=1012\cdot 2023 \not \vdots \ 3 \Rightarrow$ Mâu thuẫn

Vậy không thể chia tập $X$ thành hai tập rời nhau $A$ và $B$ sao cho tổng các phần tử thuộc $A$ bằng 2 lần tổng các phần tử thuộc $B$.

Bài 5. 

Một bảng vuông $8 \times 8$ khuyết các ô vuông ở hai góc đối diện. Hỏi có thể phủ các ô của bảng vuông bằng các hình Domino $1 \times 2$ mà không có quân Domino nào chồng lên nhau được không? Tại sao?

Lời giải

Không có mô tả.

Giả sử có thể phủ các ô của bảng vuông bằng các hình Domino $1 \times 2$ mà không có quân Domino nào chồng lên nhau.

Mỗi quân Domino lát vào bàn cờ luôn chiếm một ô trắng và một ô đen. Do đó, để lát được phần còn lại của bàn cờ thì số ô trắng và số ô đen bằng nhau. Mà số ô màu trắng và số ô màu đen trong phần còn lại của bàn cờ không bằng nhau. Điều này mâu thuẫn.

Vậy không thể lát được phần còn lại của bàn cờ bằng các quân Domino.

Leave a Reply

Your email address will not be published. Required fields are marked *