Tag Archives: PhanChung

Suy luận phản chứng (phần 2)

Leave a reply

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. Sau đây ta xét một vài ví dụ áp dụng suy luận này, dành cho các bạn hs lớp 8, 9.

1/ Ví dụ:

Ví dụ 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ỉ.

Ví dụ 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ỉ.

Ví dụ 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ố phân biệt 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}$. Ta chỉ cần chứng minh $a_1 > 0$.

Thật vậy, giả sử $a_1 \leq 0$, khi đó $$a_1 + a_2 + \cdots + a_8 \leq a_2 + a_3 + \cdots a_8 < a_9 + \cdots a_{15}$$ (mâu thuẫn).

Vậy điều giả sử là sai, hay  $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.

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)