Tag Archives: PhanChung

Suy luận phản chứng

Leave a reply

Bài viết này dành cho các em lớp 5, 6, 7

Các nhà toán học trong quá khứ đã làm việc chăm chỉ để khám phá bản chất của các chứng minh, và một loạt các kỹ thuật chứng minh đã được phát triển qua nhiều thế kỷ. Hôm nay, chúng tôi sẽ giới thiệu một phương pháp chứng minh quan trọng được gọi là bằng chứng do mâu thuẫn.

Ta thường gặp bài toán kiểu: Có A là đúng và cần suy ra X cũng đúng, trong một số trường hợp ta suy luận trực tiếp như sau: có A đúng thì có C đúng, có C đúng thì có D đúng, …, rồi suy ra X đúng, ở đây ta dùng A làm giả thiết để cho các suy luận sau. Tuy vậy một số tình huống ta không sử dụng được giả thiết A đúng, ta có thể dùng kĩ thuật suy luận phản chứng như sau: Giả sử X sai, tức là ta chấp nhận một giả thiết mới là X sai, từ giả thiết này ta dẫn đến một điều gì đó vô lí, hoặc dẫn đến A sai; khi đó điều giả sử đó là không đúng, tức là ta có điều cần chứng minh. Thế mạnh của suy luận phản chứng là mình có thêm một giả thiết để giúp trong việc suy luận dễ dàng hơn.

Ví dụ 1. Có tồn tại hay không số nguyên lẻ lớn nhất?

Lời giải Giả sử tồn tại số nguyên lẻ lớn nhất là $m$.

khi đó $m+2$ cũng là số lẻ và $m+2 > m$ nên mâu thuẫn vì theo giả sử thì $m$ là lớn nhất.

Vậy không có số nguyên lẻ lớn nhất.

Ví dụ 2. 5 cầu thủ bóng đá đã cùng nhau ghi được 14 bàn thắng, với mỗi cầu thủ ghi ít nhất 1 bàn. Chứng minh rằng ít nhất 2 trong số họ ghi được số bàn thắng như nhau. số bàn thắng.

Lời giải. Giả sử không có ai ghi số bàn thắng bằng nhau.

Khi đó người ghi ít nhất là 1 bàn, người kế tiếp ghi ít nhất là 2 bàn, người thứ 3 ghi ít nhất 3 bàn, cứ như thế người ghi nhiều nhất có số bàn thắng ít nhất là 5 bàn, khi đó tổng số bàn thắng của 5 người ít nhất là $1+2+3+4+5 = 15$ (mâu thuẫn).

Vậy có hai người ghi số bàn thắng bằng nhau.

Ví dụ 3. Quốc hội của một quốc gia được thành lập bởi các nghị sĩ đại diện từ 8 tỉnh. Năm mươi trong số các nghị sĩ này quyết định thành lập một ủy ban. Chứng minh rằng ủy ban này sẽ bao gồm 8 người từ cùng một tỉnh hoặc người từ tất cả 8 tỉnh.

Lời giải. Giả sử ủy bản mỗi tỉnh không có quá 7 người và chỉ đến từ 7 tỉnh trở lại, khi đó số thành viên ủy ban là không qua 49 người, mâu thuẫn.

Vậy trong ủy ban sẽ có một tỉnh có 8 người hoặc thành viên đến từ cả 8 tỉnh.

Ví dụ 4. Viết 10 số từ 0 đến 9 trên một vòng tròn, mỗi số viết đúng một lần.

a) Có tồn tại hay không cách viết sao cho tổng hai số liên tiếp không nhỏ hơn 9?
b) Có tồn tại hay không cách viết sau cho tổng 3 số liên tiếp lớn hơn 12?
Lời giải.

a) Giả sử tồn tại cách viết sao cho tổng hai số liên tiếp không nhỏ hơn 9, xét số 0 và hai số kề với 0 là $a, b$ ta có $0+a \geq 9, 0 + b \geq 9$, suy ra $a=b=9$ mâu thuẫn, vì mỗi số viết đúng 1 lần.

b) Giả sử tồn tại cách viết thỏa đề bài. Tổn các số là 45, bỏ số 9, và xếp 9 số còn lại làm ba nhóm, mỗi nhóm 3 số liên tiếp, khi đó tổng của chúng lớn hơn 36, tuy vậy ta thấy 9 số đó là $0, 1,2, \cdots 8$ tổng là 36, đây là điều mâu thuẫn.

Vậy không cách ghi thỏa đề bài.

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

Bài 1. Chứng minh rằng khi cho $n+1$ con thỏ vào $n$ cái chuồng thì có chuồng chứa ít nhất 2 con thỏ.

Bài 2. 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.

Bài 3. Tích của 22 số nguyên bằng 1. Chứng minh rằng tổng của chúng không thể bằng 0.

Bài 4. Có thể chia tập $X = \{1, 2, …, 2022\}$ thành các tập rời nhau sao cho mỗi tập có ít nhất 3 phần tử và phần tử lớn nhất bằng tổng các phần tử còn lại?

Phương pháp chứng minh phản chứng (Lớp 10)

Leave a reply

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.

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

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)
  • a 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.

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)

Áp dụng mệnh đề vào suy luận toán học

Leave a reply

Một định lý được phát biểu thường có dạng một biểu thức mệnh đề như $P \Rightarrow Q$ (1) hoặc $P \Leftrightarrow Q$ (2)

Ví dụ. Tam giác $ABC$ vuông tại $A$ khi và chỉ khi $AB^2+AC^2=BC^2$ (Pitago).

Ví dụ. Chứng minh rằng mọi số tự nhiên lớn hơn 1 đều có thể biểu diễn thành tích các thừa số nguyên tố.

Thực ra dạng (2) cũng có dạng $P \Rightarrow Q \wedge Q \Rightarrow P$, nên ta xét dạng 1.

Với mệnh đề dạng $P \Rightarrow Q$ thì

  • $P$ được gọi là điều kiện đủ để có $Q$.
  • $Q$ được gọi là điều kiện cần để có $P$.

Phương pháp chứng minh trực tiếp. Để chứng minh mệnh đề $P \Rightarrow Q$ là đúng, ta sử dụng hằng đúng sau: $((P \Rightarrow R) \wedge (R \Rightarrow Q))  \Rightarrow (P \Rightarrow Q)$, tức là ta đi qua các bước trung gian $P \Rightarrow R$ và $R \Rightarrow Q$.

Ví dụ. Chứng minh nếu $A \subset B$ và $B \subset C$ thì $A \subset C$.

Chứng minh. Ta có $X \subset Y \Leftrightarrow \forall x \in X \Rightarrow x \in Y$.

Do đó lấy $x$ bất kì $x\in A$, ta chứng minh $x \in C$.

Thực vậy, do $x \in A$ mà $A \subset B$ nên $x \in B$. Hơn nữa $B \subset $ nên $x \in C$.

Vậy $A \subset C$.

Phương pháp chứng minh gián tiếp. Cụ thể ở đây là phương pháp phản chứng, ta sử dụng tương đương logic $P \Rightarrow Q \Leftrightarrow \overline{Q} \Rightarrow \overline{P}$.  Thay vì chứng minh $P \Rightarrow Q$ là đúng ta chứng minh $\overline{Q} \Rightarrow \overline{P}$ là đúng. Lợi thế của phản chứng minh ta có thể tạo ra một giả thiết mới là $\overline{Q}$ từ đó giúp ta suy luận tiếp.

Ví dụ. Chứng minh rằng tổng của một số hữu tỉ và một số vô tỉ là một số hữu tỉ.

Chứng minh. Lấy $a \in \mathbb{Q}, b \notin \mathbb{Q}$, ta chứng minh $a + b \notin \mathbb{Q}$.

Giả sử ngược lại $a +b = c \in \mathbb{Q}$. Suy ra $b = c – a$, mà $c, a \in \mathbb{Q} \Rightarrow c – a \in \mathbb{Q}$, suy ra $b \in \mathbb{Q}$ (mâu thuẫn).