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?