Chương 17: Chứng minh phản chứng

Câu hỏi mở đầu

Có những điều mà đi thẳng không tới được, nhất là khi phải chứng minh một điều là không thể, hay không tồn tại: không có phân số nào bình phương bằng 2, không có số nguyên tố lớn nhất. Không thể thử mọi phân số hay kiểm mọi số nguyên tố. Vậy làm sao chứng minh "không có"?

Chứng minh rằng không có

Muốn chứng minh "có", chỉ cần chỉ ra một ví dụ. Muốn chứng minh "không có", không có gì để chỉ ra. Không thể thử mọi phân số để thấy không phân số nào có bình phương bằng 2, cũng không thể đi dọc các số nguyên tố để thấy chúng không bao giờ hết.

Trong đời thường, ta vẫn lập luận về những điều "không thể" theo một cách quen thuộc. Một người bị nghi đã ở hiện trường lúc 8 giờ tối. Người khác lập luận: "Giả sử anh ta ở đó lúc 8 giờ. Nhưng 8 giờ 10 phút anh ta có mặt ở một nơi cách đó hai giờ đi đường, có nhiều người chứng kiến. Không ai đi hai giờ đường trong mười phút. Vậy giả sử kia sai: anh ta không ở hiện trường." Ta không kiểm tra hiện trường; ta cho điều cần bác bỏ là đúng, lần theo hệ quả của nó, và gặp một điều không thể xảy ra.

Chương 11 đã chứng minh \(\sqrt2\) vô tỉ đúng như thế: giả sử \(\sqrt2 = \frac pq\) tối giản, lần theo hệ quả, thấy \(p\) và \(q\) đều chẵn, trái với "tối giản". Chương này gọi tên và mổ xẻ lối lập luận ấy.

Vì sao phản chứng hợp lệ

Nền của phản chứng là định nghĩa mệnh đề ở Chương 14: một mệnh đề có đúng một trong hai giá trị, đúng hoặc sai. Muốn chứng minh \(P\), ta giả sử \(\lnot P\), và từ đó suy ra, qua những bước hợp lệ, một mâu thuẫn: một mệnh đề \(Q\) cùng với phủ định \(\lnot Q\) của nó. Vì \(Q\) và \(\lnot Q\) không thể cùng đúng, và những bước hợp lệ không dẫn từ điều đúng tới điều sai, nên \(\lnot P\) không thể đúng. Mệnh đề nào cũng có một giá trị, nên \(\lnot P\) sai, tức \(P\) đúng.

Bằng bảng chân trị: câu "\(\lnot P\) kéo theo một điều luôn sai" có cùng giá trị với \(P\) ở mọi dòng (Định lý 1 dưới đây). Phản chứng không phải một mẹo; nó là một phép tương đương logic.

Phản chứng khác chứng minh phản đảo ở Chương 16. Muốn chứng minh \(P \Rightarrow Q\) bằng phản đảo, ta giả sử \(\lnot Q\) và phải đi tới đúng một đích: \(\lnot P\). Bằng phản chứng, ta giả sử cả \(P\) lẫn \(\lnot Q\), rồi đi tới bất kỳ mâu thuẫn nào. Phản chứng linh hoạt hơn: ta có thêm một giả thiết để dùng, và mâu thuẫn có thể đến từ bất cứ đâu. Cái giá của sự linh hoạt ấy sẽ bàn ở mục Ranh giới.

Ký hiệu

Một chứng minh phản chứng thường viết theo khuôn:

1. "Giả sử ngược lại, \(\lnot P\)." (Với câu \(P \Rightarrow Q\): "Giả sử \(P\) đúng nhưng \(Q\) sai.")
2. Suy luận từng bước, dùng cả giả thiết mới ấy.
3. "Điều này mâu thuẫn với ...", chỉ rõ mệnh đề nào vừa đúng vừa sai.
4. "Vậy giả sử là sai, và \(P\) đúng." \(\square\)

flowchart LR
    A["Muốn chứng minh P"] --> B["Giả sử không P"]
    B --> C["Suy luận từng bước"]
    C --> D["Gặp Q và không Q"]
    D --> E["Giả sử sai"]
    E --> F["Vậy P đúng"]

Hai khái niệm đi kèm. Nguyên lý chuồng bồ câu (pigeonhole principle): nếu xếp nhiều vật hơn số hộp, thì có hộp chứa ít nhất hai vật; tên gọi đến từ hình ảnh những con chim bồ câu bay vào các ngăn chuồng. Chứng minh có xây dựng (constructive proof) của một câu "tồn tại" là chứng minh chỉ ra được đối tượng tồn tại; một chứng minh chỉ cho thấy đối tượng phải tồn tại, mà không chỉ ra nó, gọi là chứng minh không xây dựng (non-constructive proof).

Làm bằng tay

Ví dụ 1 (có vô số số nguyên tố). Giả sử ngược lại: chỉ có hữu hạn số nguyên tố, liệt kê hết là \(p_1, p_2, \dots, p_n\). Xét số

\[ N = p_1 \cdot p_2 \cdots p_n + 1 . \]

Vì \(N \geq 2 + 1 > 1\), nó có ít nhất một ước nguyên tố \(q\) (Bổ đề 2). Theo giả sử, \(q\) phải là một trong các \(p_i\). Khi đó \(q\) chia hết \(p_1 p_2 \cdots p_n\), và \(q\) chia hết \(N\), nên \(q\) chia hết hiệu của chúng, là 1 (bài B10 Chương 16). Nhưng không số nguyên tố nào chia hết 1. Mâu thuẫn. Vậy có vô số số nguyên tố. \(\square\)

Lập luận này là một chứng minh cổ điển, thường gắn với tên Euclid. Một hiểu lầm hay gặp: nó không nói rằng \(N\) là số nguyên tố. Với sáu số nguyên tố đầu tiên, \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\), một hợp số. Nó chỉ nói rằng các ước nguyên tố của \(N\) nằm ngoài danh sách, nên danh sách không thể đầy đủ.

Tích \(n\) số nguyên tố đầu tiên cộng 1. Năm số đầu là số nguyên tố, nhưng từ \(n = 6\) thì không: \(30031 = 59 \cdot 509\). Chứng minh không cần \(N\) nguyên tố; nó chỉ cần các ước nguyên tố của \(N\) nằm ngoài danh sách.

Ví dụ 2 (\(\sqrt2\) theo khuôn phản chứng). Giả sử ngược lại, \(\sqrt2 = \frac pq\) với \(p\), \(q\) nguyên dương không cùng chẵn (luôn có thể rút gọn tới mức ấy, Chương 10). Bình phương: \(p^2 = 2q^2\), nên \(p^2\) chẵn, nên \(p\) chẵn (Chương 16, Mệnh đề 5): \(p = 2k\). Thay vào: \(q^2 = 2k^2\), nên \(q\) chẵn. Vậy \(p\) và \(q\) cùng chẵn, mâu thuẫn với giả sử. \(\square\)

Nhìn theo khuôn, có thể thấy rõ "mệnh đề vừa đúng vừa sai" ở đây là "\(p\) và \(q\) cùng chẵn". Toàn bộ nghệ thuật nằm ở việc chọn trước một giả sử đủ mạnh để có chỗ va vào: nếu không đòi \(\frac pq\) tối giản, lập luận chỉ cho "\(p\), \(q\) cùng chẵn", chẳng mâu thuẫn với gì (bài C3 cho một cách khác để cứu nó).

Ví dụ 3 (cùng tháng sinh). Trong 13 người bất kỳ có hai người sinh cùng tháng. Giả sử ngược lại: 13 người sinh ở 13 tháng khác nhau. Nhưng một năm chỉ có 12 tháng. Mâu thuẫn. Đây là nguyên lý chuồng bồ câu: 13 vật (người) vào 12 hộp (tháng).

Mạnh hơn: trong 25 người bất kỳ có ba người sinh cùng tháng. Giả sử ngược lại: mỗi tháng có nhiều nhất 2 người. Khi đó tổng số người không quá \(2 \cdot 12 = 24 < 25\). Mâu thuẫn. Con số 25 là tốt nhất có thể: 24 người, mỗi tháng đúng 2 người, không có ba người nào cùng tháng.

Bốn vật có thể nằm ở bốn hộp khác nhau; vật thứ năm buộc phải vào một hộp đã có vật. Nguyên lý không nói hộp nào.

Ví dụ 4 (năm điểm trong một hình vuông). Trong một hình vuông cạnh 2, đặt 5 điểm bất kỳ. Khi đó có hai điểm cách nhau không quá \(\sqrt2\).

Chia hình vuông thành bốn ô vuông cạnh 1 (một điểm nằm trên cạnh chung thì xếp nó vào một ô bất kỳ trong các ô chứa nó). Năm điểm, bốn ô: theo nguyên lý chuồng bồ câu, có một ô chứa hai điểm. Hai điểm trong một ô vuông cạnh 1 cách nhau không quá đường chéo của ô, tức \(\sqrt2\) (Chương 11). \(\square\)

Năm điểm, bốn ô: có một ô chứa hai điểm, và hai điểm ấy cách nhau không quá đường chéo \(\sqrt2\) của ô.

Để ý cách lời giải được tìm ra: cái khó không nằm ở lập luận, mà ở việc chọn "hộp" cho khéo. Chọn ô cạnh 1 vì đường chéo của nó đúng bằng \(\sqrt2\), con số cần có.

Ví dụ 5 (khi phản chứng thừa). "Không có số hữu tỉ dương nhỏ nhất." Phản chứng: giả sử \(q\) là số hữu tỉ dương nhỏ nhất; khi đó \(\frac q2\) là số hữu tỉ dương nhỏ hơn \(q\), mâu thuẫn. Nhưng ở Chương 15, bài C3 đã chứng minh trực tiếp điều mạnh hơn: mỗi số hữu tỉ dương \(q\) đều có số hữu tỉ dương nhỏ hơn, là \(\frac q2\). Hai chứng minh dùng cùng một ý; lớp vỏ phản chứng ở đây không thêm gì. Khi một chứng minh phản chứng chỉ va vào chính giả sử "\(q\) nhỏ nhất" bằng một ví dụ xây dựng được, nó thường là một chứng minh trực tiếp đội lốt.

Ví dụ 6 (tồn tại mà không chỉ ra được). Có tồn tại hai số vô tỉ \(a\), \(b\) sao cho \(a^b\) là số hữu tỉ không? Xét số \(\sqrt2^{\sqrt2}\) (hiểu theo cách mở rộng số mũ ở Chương 12). Nó hoặc hữu tỉ, hoặc vô tỉ.

• Nếu nó hữu tỉ: chọn \(a = b = \sqrt2\), xong.
• Nếu nó vô tỉ: chọn \(a = \sqrt2^{\sqrt2}\) và \(b = \sqrt2\). Khi đó \(a^b = \sqrt2^{\sqrt2 \cdot \sqrt2} = \sqrt2^2 = 2\), hữu tỉ.

Trường hợp nào cũng có một cặp như thế. Vậy câu trả lời là có, dù lập luận không cho biết cặp nào đúng. Đó là một chứng minh không xây dựng. (Bằng một định lý khó hơn nhiều, người ta biết \(\sqrt2^{\sqrt2}\) vô tỉ, nên cặp thứ hai mới là cặp đúng.)

Ranh giới

Mâu thuẫn giả. Trong chứng minh trực tiếp, một lỗi tính toán thường dẫn tới một kết luận lạ, và người viết dừng lại kiểm tra. Trong phản chứng, người viết đang chờ một điều vô lý; một lỗi tính toán tạo ra đúng thứ họ chờ, và họ dễ dàng tin. Vì thế mỗi bước của một chứng minh phản chứng cần được kiểm kỹ hơn, không phải lơi hơn (bài B9).

Lạm dụng phản chứng. Nhiều chứng minh phản chứng là chứng minh trực tiếp hay phản đảo đội lốt, như Ví dụ 5. Chúng không sai, nhưng che mất cấu trúc: một chứng minh trực tiếp cho biết vì sao điều ấy đúng, và thường cho thêm một cách xây dựng. Hãy thử viết lại một chứng minh phản chứng thành chứng minh trực tiếp; nếu làm được, thường nên làm.

Nguyên lý chuồng bồ câu không chỉ ra hộp nào. Trong 13 người có hai người cùng tháng sinh, nhưng nguyên lý không nói đó là ai, hay tháng nào. Đó là một kết luận về tổng thể: ta biết điều gì đó phải xảy ra ở một chỗ, mà không biết chỗ nào.

Chứng minh không xây dựng và những người không chấp nhận nó. Ví dụ 6 dựa vào bước "số ấy hoặc hữu tỉ hoặc vô tỉ", dù không biết là trường hợp nào. Một số nhà toán học, theo trường phái gọi là toán học kiến thiết (constructive mathematics), chỉ chấp nhận một câu "tồn tại" khi có cách xây dựng đối tượng ấy. Với họ, phản chứng vẫn dùng được để chứng minh một điều là không thể, nhưng không đủ để chứng minh một điều có. Cuộc tranh luận này nối thẳng với câu hỏi ở Chương 1: nếu toán học là khám phá một thế giới có sẵn, thì "tồn tại" có nghĩa ngay cả khi ta chưa chỉ ra được; nếu toán học là việc con người xây dựng, thì "tồn tại" nên có nghĩa là "xây dựng được". Phần lớn toán học ngày nay chấp nhận cả hai kiểu chứng minh, nhưng vẫn quý chứng minh có xây dựng hơn, vì nó cho nhiều thông tin hơn.

Phát biểu chặt chẽ

Định lý 1 (cơ sở của phản chứng). Với mọi mệnh đề \(P\) và \(Q\), mệnh đề \(\lnot P \Rightarrow (Q \land \lnot Q)\) tương đương logic với \(P\).

Chứng minh. \(Q \land \lnot Q\) sai ở mọi dòng. Phép kéo theo có kết luận luôn sai thì đúng khi và chỉ khi giả thiết sai, tức khi \(\lnot P\) sai, tức khi \(P\) đúng. Bảng chân trị:

\(P\)	\(Q\)	\(\lnot P\)	\(Q \land \lnot Q\)	\(\lnot P \Rightarrow (Q \land \lnot Q)\)
Đ	Đ	S	S	Đ
Đ	S	S	S	Đ
S	Đ	Đ	S	S
S	S	Đ	S	S

Cột cuối trùng với cột \(P\). \(\square\)

Bổ đề 2. Mỗi số nguyên \(n \geq 2\) có ít nhất một ước nguyên tố.

Chứng minh. Trong các ước lớn hơn 1 của \(n\) (có ít nhất một, chính là \(n\)), gọi \(d\) là ước nhỏ nhất. Giả sử \(d\) không phải số nguyên tố. Khi đó \(d = a b\) với \(1 < a < d\). Nhưng \(a \mid d\) và \(d \mid n\) nên \(a \mid n\) (Mệnh đề 7 của Chương 16), tức \(a\) là một ước của \(n\) lớn hơn 1 và nhỏ hơn \(d\), trái với cách chọn \(d\). Vậy \(d\) là số nguyên tố. \(\square\)

Chứng minh này dùng một điều mà ta coi là hiển nhiên: mỗi nhóm khác rỗng các số tự nhiên có một số nhỏ nhất. Chương 18 sẽ cho thấy điều ấy gắn chặt với một lối chứng minh mới.

Định lý 3. Có vô số số nguyên tố.

Chứng minh. Như Ví dụ 1. \(\square\)

Định lý 4 (nguyên lý chuồng bồ câu). Nếu xếp \(n + 1\) vật vào \(n\) hộp thì có ít nhất một hộp chứa ít nhất 2 vật.

Chứng minh. Giả sử ngược lại: mỗi hộp chứa nhiều nhất 1 vật. Khi đó tổng số vật không quá \(n \cdot 1 = n\), trái với việc có \(n + 1\) vật. \(\square\)

Định lý 5 (nguyên lý chuồng bồ câu tổng quát). Nếu xếp \(kn + 1\) vật vào \(n\) hộp thì có ít nhất một hộp chứa ít nhất \(k + 1\) vật.

Chứng minh. Bài C1. \(\square\)

Sợi chỉ

• S4. Cục bộ và toàn cục. Nguyên lý chuồng bồ câu đi từ một phép đếm tổng thể (nhiều vật hơn chỗ chứa) tới một kết luận về một hộp cụ thể, mà không chỉ ra hộp nào. Ví dụ 4 dùng nó để suy ra một điều về hai điểm từ một điều về cả năm điểm.
• S2. Thông tin và khả nghịch. Phản chứng lần theo hệ quả của một giả sử cho tới khi gặp điều không thể. Một chứng minh không xây dựng cho biết "có", nhưng làm mất thông tin về "cái gì"; đó là lý do nhiều người quý chứng minh có xây dựng hơn.
• S1. Bất biến qua biến đổi. Trong Ví dụ 2 và bài B2, mâu thuẫn đến từ tính chẵn lẻ, bất biến đã phục vụ ta từ bàn cờ cắt góc ở Chương 1.

Tóm tắt

• Chứng minh phản chứng: giả sử điều ngược lại, suy ra một mâu thuẫn \(Q \land \lnot Q\), rồi kết luận điều cần chứng minh; nó hợp lệ vì mỗi mệnh đề có đúng một giá trị chân lý.
• Phản đảo đi tới một đích định trước (\(\lnot P\)); phản chứng đi tới bất kỳ mâu thuẫn nào, nên linh hoạt hơn nhưng cũng dễ che giấu cấu trúc và lỗi.
• Có vô số số nguyên tố: nếu chỉ có \(p_1, \dots, p_n\), thì mọi ước nguyên tố của \(p_1 \cdots p_n + 1\) nằm ngoài danh sách; bản thân số ấy không nhất thiết là số nguyên tố (\(30031 = 59 \cdot 509\)).
• Nguyên lý chuồng bồ câu: \(n + 1\) vật vào \(n\) hộp thì có hộp chứa ít nhất 2 vật; \(kn + 1\) vật thì có hộp chứa ít nhất \(k + 1\) vật. Nghệ thuật nằm ở việc chọn hộp.
• Một chứng minh không xây dựng cho biết đối tượng tồn tại mà không chỉ ra nó; toán học kiến thiết chỉ chấp nhận chứng minh có xây dựng.
• Trong phản chứng, một lỗi tính toán tạo ra mâu thuẫn giả; vì đang chờ mâu thuẫn, người viết càng phải kiểm kỹ.

Bài tập

A. Tư duy

A1. Giải thích vì sao phản chứng hợp lệ, dựa vào định nghĩa mệnh đề ở Chương 14. Nếu một câu có thể "không đúng cũng không sai", như "Câu này sai", thì phản chứng còn dùng được cho câu ấy không?

Lời giải

Một mệnh đề có đúng một trong hai giá trị. Nếu từ \(\lnot P\) suy ra được một mâu thuẫn, thì \(\lnot P\) không thể đúng, vì những bước hợp lệ không dẫn từ điều đúng tới \(Q \land \lnot Q\), một điều luôn sai. Vậy \(\lnot P\) sai; vì \(P\) phải có một giá trị, \(P\) đúng.

Lập luận dùng cả hai nửa của định nghĩa: "không thể vừa đúng vừa sai" (để \(Q \land \lnot Q\) là điều không thể) và "phải đúng hoặc sai" (để từ "\(\lnot P\) không đúng" suy ra "\(P\) đúng"). Với một câu như "Câu này sai", vốn không có giá trị nào, nửa sau không còn, và phản chứng không áp dụng được. Đó là một lý do để logic loại những câu như thế ra khỏi nhóm mệnh đề.

A2. Trong chứng minh có vô số số nguyên tố, một người lập luận: "Vậy \(p_1 p_2 \cdots p_n + 1\) là một số nguyên tố mới." Chỉ ra chỗ sai. Chứng minh thật sự dùng điều gì về số ấy?

Lời giải

Số ấy không nhất thiết là số nguyên tố: \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509\). Chứng minh chỉ dùng hai điều: số ấy lớn hơn 1, nên có một ước nguyên tố (Bổ đề 2); và ước nguyên tố ấy không thể nằm trong danh sách, vì nếu nằm trong danh sách thì nó chia hết 1. Số nguyên tố "mới" là một ước của \(N\), có thể là \(N\) hoặc không.

A3. Giả sử mỗi người có ít hơn 1 triệu sợi tóc trên đầu, và một thành phố có hơn 1 triệu người. Chứng minh rằng có hai người trong thành phố có cùng số sợi tóc. Chứng minh ấy có chỉ ra hai người đó không? Bạn có chấp nhận nó là một chứng minh không?

Lời giải

Số sợi tóc của mỗi người là một số tự nhiên từ 0 tới 999.999: có đúng 1.000.000 giá trị, tức 1.000.000 "hộp". Số người nhiều hơn số hộp, nên theo nguyên lý chuồng bồ câu có hai người rơi vào cùng một hộp, tức có cùng số sợi tóc. \(\square\)

Chứng minh không chỉ ra hai người ấy, cũng không cho cách nào tìm họ ngoài việc đếm tóc của mọi người. Theo chuẩn thông thường của toán học, đó là một chứng minh hoàn chỉnh cho câu "tồn tại". Người theo toán học kiến thiết sẽ nói: nó cho một cách xây dựng về nguyên tắc (đếm tóc tất cả mọi người rồi so), chỉ là không làm được trong thực tế; ở đây sự bất đồng nhỏ hơn ở Ví dụ 6, nơi không có cách nào để biết trường hợp nào đúng nếu thiếu một định lý khác.

B. Tính toán

B1. Tính \(p_1 p_2 \cdots p_n + 1\) với \(n = 1, 2, \dots, 6\) (các số nguyên tố đầu tiên). Số nào là số nguyên tố? Với số không phải số nguyên tố, phân tích nó ra thừa số nguyên tố.

Lời giải

\(2 + 1 = 3\); \(2 \cdot 3 + 1 = 7\); \(2 \cdot 3 \cdot 5 + 1 = 31\); \(2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211\); \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2311\): năm số này đều là số nguyên tố. Số thứ sáu, \(30031 = 59 \cdot 509\), là hợp số; cả 59 và 509 đều không nằm trong danh sách \(2, 3, 5, 7, 11, 13\), đúng như chứng minh đòi hỏi.

B2. Chứng minh bằng phản chứng: (a) không có số chẵn lớn nhất; (b) không có hai số nguyên \(a\), \(b\) nào thỏa \(4a + 6b = 1\).

Lời giải

(a) Giả sử \(M\) là số chẵn lớn nhất. Khi đó \(M + 2\) cũng chẵn và lớn hơn \(M\), mâu thuẫn. \(\square\)

(b) Giả sử có \(a\), \(b\) nguyên với \(4a + 6b = 1\). Vế trái bằng \(2(2a + 3b)\), là số chẵn; vế phải 1 là số lẻ. Một số không thể vừa chẵn vừa lẻ (Bổ đề 2 của Chương 16), mâu thuẫn. \(\square\)

B3. Dùng nguyên lý chuồng bồ câu, chứng minh: (a) trong 367 người bất kỳ có hai người cùng ngày sinh (tính cả ngày 29 tháng 2); (b) trong 11 số nguyên bất kỳ có hai số có cùng chữ số hàng đơn vị; (c) trong 5 số nguyên bất kỳ có hai số có hiệu chia hết cho 4.

Lời giải

(a) Có 366 ngày sinh có thể: 367 người, 366 hộp.

(b) Chữ số hàng đơn vị là một trong 10 chữ số 0 đến 9: 11 số, 10 hộp.

(c) Số dư khi chia cho 4 là một trong 0, 1, 2, 3: 5 số, 4 hộp. Hai số có cùng số dư thì hiệu của chúng chia hết cho 4 (Chương 8).

B4. (a) Cần ít nhất bao nhiêu người để chắc chắn có 5 người sinh cùng tháng? (b) Một ngăn kéo có tất đủ ba màu, lấy ra mà không nhìn. Phải lấy ít nhất bao nhiêu chiếc để chắc có 2 chiếc cùng màu? Để chắc có 3 chiếc cùng màu?

Lời giải

(a) Theo Định lý 5 với \(k = 4\), \(n = 12\): \(4 \cdot 12 + 1 = 49\) người. Với 48 người vẫn có thể mỗi tháng đúng 4 người.

(b) Ba màu là ba hộp. Để có 2 chiếc cùng màu: \(1 \cdot 3 + 1 = 4\) chiếc (3 chiếc có thể khác màu hết). Để có 3 chiếc cùng màu: \(2 \cdot 3 + 1 = 7\) chiếc (6 chiếc có thể là mỗi màu hai chiếc).

B5. Chứng tỏ các con số ở Ví dụ 3 là tốt nhất có thể: (a) có 12 người mà không hai người nào cùng tháng sinh; (b) có 24 người mà không ba người nào cùng tháng sinh.

Lời giải

(a) Mỗi tháng một người. (b) Mỗi tháng đúng hai người. Hai ví dụ này cho thấy không thể thay 13 bằng 12, hay 25 bằng 24.

B6. Trong một tam giác đều cạnh 2 đặt 5 điểm bất kỳ. Chứng minh có hai điểm cách nhau không quá 1.

Lời giải

Nối trung điểm ba cạnh, tam giác được chia thành bốn tam giác đều cạnh 1. Năm điểm, bốn tam giác: có một tam giác nhỏ chứa hai điểm (điểm nằm trên cạnh chung thì xếp vào một tam giác bất kỳ chứa nó). Hai điểm trong một tam giác đều cạnh 1 cách nhau không quá độ dài cạnh, tức 1. \(\square\)

B7. Chọn 6 số khác nhau bất kỳ từ các số \(1, 2, \dots, 10\). Chứng minh có hai số trong đó có tổng bằng 11.

Lời giải

Chia mười số thành năm cặp có tổng 11: \(\{1; 10\}\), \(\{2; 9\}\), \(\{3; 8\}\), \(\{4; 7\}\), \(\{5; 6\}\). Sáu số, năm cặp: có hai số rơi vào cùng một cặp, và tổng của chúng là 11. \(\square\) Với 5 số thì không đủ: \(1, 2, 3, 4, 5\) không có cặp nào tổng 11.

B8. Dùng máy tính, tính xấp xỉ \(\sqrt2^{\sqrt2}\) và \(\left(\sqrt2^{\sqrt2}\right)^{\sqrt2}\). Kết quả thứ hai có khớp với Ví dụ 6 không?

Lời giải

\(\sqrt2^{\sqrt2} \approx 1{,}6325\). Nâng lên lũy thừa \(\sqrt2\): \(\left(\sqrt2^{\sqrt2}\right)^{\sqrt2} = \sqrt2^{2} = 2\), và máy tính cho \(2{,}0000\). Con số \(1{,}6325\) trông không giống một phân số quen thuộc, nhưng một vài chữ số thập phân không bao giờ đủ để quyết định một số là hữu tỉ hay vô tỉ (Chương 11).

B9. Tìm lỗi trong "chứng minh" sau: "91 là số nguyên tố. Giả sử ngược lại, 91 là hợp số. Khi đó nó có một ước nguyên tố \(p\) với \(p^2 \leq 91\), tức \(p\) là 2, 3, 5 hoặc 7. Nhưng 91 chia 2 dư 1, chia 3 dư 1, chia 5 dư 1, chia 7 dư 3. Mâu thuẫn. Vậy 91 là số nguyên tố."

Lời giải

\(91 = 7 \cdot 13\), nên 91 chia 7 dư 0, không phải dư 3. Một lỗi tính toán đã tạo ra một "mâu thuẫn" giả, và phản chứng biến lỗi ấy thành một kết luận sai. Khuôn lập luận thì đúng (một hợp số \(n\) có ước nguyên tố \(p\) với \(p^2 \leq n\)); chỉ một phép chia sai là đủ làm hỏng tất cả.

B10. Chứng minh bằng phản chứng: với số nguyên \(n\), nếu \(n^2\) lẻ thì \(n\) lẻ. So sánh với chứng minh phản đảo ở bài B4 Chương 16.

Lời giải

Giả sử \(n^2\) lẻ nhưng \(n\) không lẻ, tức \(n\) chẵn: \(n = 2k\). Khi đó \(n^2 = 4k^2 = 2(2k^2)\) chẵn, trong khi giả thiết nói \(n^2\) lẻ. Một số không thể vừa chẵn vừa lẻ, mâu thuẫn. \(\square\)

Phần giữa của chứng minh, "\(n\) chẵn thì \(n^2\) chẵn", chính là toàn bộ chứng minh phản đảo. Lớp vỏ phản chứng chỉ thêm câu mở đầu và câu kết. Đây là một ví dụ của phản chứng đội lốt phản đảo.

C. Phản ví dụ và chứng minh

C1. Chứng minh Định lý 5: xếp \(kn + 1\) vật vào \(n\) hộp thì có hộp chứa ít nhất \(k + 1\) vật.

Lời giải

Giả sử ngược lại: mỗi hộp chứa nhiều nhất \(k\) vật. Khi đó tổng số vật không quá \(k \cdot n = kn\), trong khi có \(kn + 1\) vật. Mâu thuẫn. \(\square\)

C2. Chứng minh có vô số số nguyên tố chia 4 dư 3. (Gợi ý: nếu chỉ có \(p_1, \dots, p_n\), xét \(N = 4 p_1 p_2 \cdots p_n - 1\). Tích của các số chia 4 dư 1 thì chia 4 dư mấy?)

Lời giải

Tích hai số chia 4 dư 1 lại chia 4 dư 1: \((4a + 1)(4b + 1) = 4(4ab + a + b) + 1\); lặp lại, tích của bao nhiêu số chia 4 dư 1 cũng chia 4 dư 1.

Giả sử chỉ có hữu hạn số nguyên tố chia 4 dư 3, là \(p_1, \dots, p_n\) (danh sách này không rỗng, vì có số 3). Đặt \(N = 4 p_1 \cdots p_n - 1\). Khi đó \(N > 1\), \(N\) lẻ, và \(N = 4(p_1 \cdots p_n - 1) + 3\) chia 4 dư 3. Các ước nguyên tố của \(N\) đều lẻ, nên mỗi ước chia 4 dư 1 hoặc dư 3. Nếu mọi ước nguyên tố của \(N\) đều chia 4 dư 1, thì \(N\), là tích của chúng, cũng chia 4 dư 1, sai. Vậy \(N\) có một ước nguyên tố \(q\) chia 4 dư 3. Theo giả sử, \(q\) là một \(p_i\), nên \(q\) chia hết \(4 p_1 \cdots p_n\). Mà \(q\) chia hết \(N\), nên \(q\) chia hết hiệu \(4 p_1 \cdots p_n - N = 1\). Mâu thuẫn. \(\square\)

C3. Chứng minh \(\sqrt2\) vô tỉ mà không dùng phân số tối giản. (Gợi ý: nếu \(p^2 = 2q^2\) với \(p\), \(q\) nguyên dương, hãy tìm một cặp nhỏ hơn cũng thỏa đẳng thức ấy.)

Lời giải

Giả sử có các số nguyên dương \(p\), \(q\) với \(p^2 = 2q^2\). Như Ví dụ 2, \(p\) chẵn, \(p = 2k\), và \(q^2 = 2k^2\). Vậy cặp \((q; k)\) cũng thỏa đẳng thức, và \(q < p\) (vì \(p^2 = 2q^2 > q^2\)). Lặp lại, ta được một dãy số nguyên dương \(p > q > k > \dots\) giảm mãi. Nhưng một dãy số nguyên dương giảm dần không thể kéo dài mãi: bắt đầu từ \(p\), nó dừng sau nhiều nhất \(p\) bước. Mâu thuẫn. \(\square\)

Lối lập luận này gọi là lùi vô hạn (infinite descent). Nó dựa vào đúng điều mà Bổ đề 2 đã dùng: mỗi nhóm khác rỗng các số tự nhiên có một số nhỏ nhất, nên không có dãy giảm mãi.

Câu hỏi để ngỏ

Có một loại "với mọi" đặc biệt: với mọi số tự nhiên \(n\). Bổ đề 2 và bài C3 đều ngầm dùng một tính chất riêng của các số tự nhiên: không thể giảm mãi. Liệu tính chất ấy có cho phép chứng minh một điều cho vô số trường hợp \(n = 0, 1, 2, \dots\) chỉ bằng hai bước hữu hạn?