Kiểm tra từng hộp#
Bạn phải kiểm tra mọi chiếc tất trong một ngăn kéo đều sạch, và có quá nhiều để xem từng chiếc một. Nhưng bạn biết mọi chiếc tất trong đó đều màu đen, trắng hoặc xám. Không có màu nào khác.
Vậy bạn chỉ cần ba lần kiểm tra. Mọi chiếc tất đen đều sạch, mọi chiếc tất trắng đều sạch, mọi chiếc tất xám đều sạch — và xong, vì không còn gì sót lại.
Đó là một chứng minh theo trường hợp (proof by cases). Chia điều bạn đang nói đến thành một danh sách hữu hạn các tình huống, chứng minh khẳng định trong từng tình huống, và kết luận nó luôn đúng.
Danh sách các hộp phải vét cạn (exhaustive) — mọi đối tượng đều phải rơi vào ít nhất một hộp. Bỏ sót một màu tất thì chứng minh không nói gì về nó. Đó là cách duy nhất một chứng minh theo trường hợp thất bại, và nó thất bại một cách âm thầm.
Các hộp đến từ đâu#
Với các số nguyên, bạn không bao giờ phải tự nghĩ ra các hộp. Phép chia cho bạn chúng.
Chọn một số m bất kỳ. Chia một số nguyên n bất kỳ cho m và bạn được một số dư, và số dư đó luôn là một trong 0, 1, 2, …, m − 1. Chia cho 3 thì số dư là 0, 1 hoặc 2 — không bao giờ là gì khác. Vậy mọi số nguyên rơi vào đúng một trong m hộp.
Viết một cách hình thức: n = qm + r với 0 ≤ r < m. Đó là thuật toán chia, và nó là động cơ của toàn bộ chủ đề này.
Cách viết tắt n ≡ r (mod m) đọc là “n chia cho m dư r”. Chọn m, được m hộp, kiểm tra hết. Số trường hợp là m — không phải hai, không phải “vài”, không phải bao nhiêu tùy bạn nghĩ ra.
Chẵn và lẻ chỉ là hai hộp#
Chia thành chẵn và lẻ có cảm giác như mặc định vì đó là cách chia đầu tiên ai cũng học. Nhưng nó chỉ là trường hợp m = 2, và nó cho bạn biết không gì ngoài tính chia hết cho 2.
Nếu một khẳng định nói về việc chia cho 3, chẵn-và-lẻ vô dụng: 3 và 4 nằm ở hai phía của cách chia đó và không sự thật nào liên quan. Hãy khớp cách chia với khẳng định.
| Khẳng định nói về… | Chia theo | Bao nhiêu hộp |
|---|---|---|
| chẵn/lẻ, hoặc chia cho 2 | 2 | 2 |
| chia cho 3 | 3 | 3 |
| bình phương, tổng hai bình phương | 4 | 4 |
| bình phương số lẻ, các dạng như x² + 2y² | 8 | 8 |
| lũy thừa bậc năm | 5 | 5 |
Ví dụ có lời giải — 3 chia hết n³ − n#
Khẳng định. Với mọi số nguyên n, 3 chia hết n³ − n.
Phân tích thành nhân tử trước: n³ − n = (n − 1) · n · (n + 1). Giờ chia theo số dư khi n chia cho 3, cho đúng ba hộp.
- Số dư 0. Khi đó 3 chia hết n, nên nó chia hết tích.
- Số dư 1. Khi đó n − 1 có số dư 0, nên 3 chia hết n − 1, nên nó chia hết tích.
- Số dư 2. Khi đó n + 1 có số dư 0, nên 3 chia hết n + 1, nên nó chia hết tích.
Ba hộp, mọi số nguyên nằm trong một hộp, khẳng định đúng trong từng hộp. Vậy nó đúng với mọi n. ∎
Hãy để ý điều gì làm chứng minh đó ngắn: phân tích nhân tử trước khi chia. Ba số liên tiếp phải chứa một bội của 3, và việc chia trường hợp chỉ là nhận xét đó được viết ra cẩn thận.
Các bảng bình phương đáng nhớ#
Bình phương bị số dư hạn chế rất mạnh, và sự hạn chế đó là nền tảng của hầu hết các chứng minh “điều này không thể xảy ra”. Hãy tính chúng ra một lần rồi giữ lại.
Chia cho 4:
| n có số dư | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| n² có số dư | 0 | 1 | 0 | 1 |
Một số chính phương luôn có số dư 0 hoặc 1 khi chia cho 4. Không bao giờ là 2, không bao giờ là 3.
Chia cho 8 thì bức tranh mịn hơn, và tách hoàn toàn bình phương số lẻ khỏi bình phương số chẵn:
| n | lẻ | chẵn, n/2 lẻ | chẵn, n/2 chẵn |
|---|---|---|---|
| n² mod 8 | 1 | 4 | 0 |
Trường hợp lẻ đáng xem được suy ra, vì nó làm việc thật sự. Viết n = 2m + 1. Khi đó n² = 4m² + 4m + 1 = 4m(m + 1) + 1. Trong hai số liên tiếp bất kỳ, có một số chẵn, nên m(m + 1) chẵn và 4m(m + 1) là bội của 8. Vậy mọi bình phương số lẻ đều dư 1 khi chia cho 8.
Loại bỏ một phương trình bằng số dư#
Để chứng tỏ một phương trình không có nghiệm nguyên, hãy tìm một số dư mà hai vế không bao giờ có thể cùng có.
Lấy x² + y² = 3z² với x, y, z không đồng thời bằng không. Xét mọi thứ chia cho 4. Mỗi bình phương là 0 hoặc 1, nên vế trái là 0, 1 hoặc 2 — không bao giờ là 3. Hãy xem vế phải có thể là gì, và hai vế không thể khớp nhau. Không có nghiệm nào, và bạn chưa bao giờ phải đi tìm nghiệm.
Một phương trình nói hai thứ bằng nhau. Hai số bằng nhau thì có cùng số dư. Nên hãy tìm một m mà hai vế không bao giờ có thể cùng số dư, và phương trình hoàn toàn không có nghiệm. Một m được chọn tốt giải quyết vô số trường hợp cùng lúc.
Khi một số hộp đúng và số khác thì không#
Đôi khi khẳng định đúng trong một số hộp và sai trong các hộp khác. Đó không phải chứng minh thất bại — đó là một kết quả sắc nét hơn, và bạn nên phát biểu nó như vậy.
“n² + 1 chia hết cho 5” là sai với hầu hết n, nhưng xét qua năm hộp cho thấy nó đúng chính xác khi n có số dư 2 hoặc 3. Việc chia trường hợp biến một khẳng định mơ hồ thành một khẳng định chính xác. Hãy nêu hộp nào đúng thay vì gọi cả khẳng định là sai.
Những chỗ dễ sai#
- Các hộp không bao phủ hết mọi thứ. Cách duy nhất thật sự làm phương pháp này thất bại. Hãy nói to vì sao mọi đối tượng đều rơi vào đâu đó.
- Theo thói quen dùng chẵn/lẻ. Nó chỉ cho bạn biết về việc chia cho 2. Hãy khớp cách chia với khẳng định.
- Quá nhiều hộp. Chia theo 6 khi 3 là đủ làm gấp đôi công việc và khả năng sai sót.
- Không phân tích nhân tử trước. Chứng minh n³ − n chỉ có ba dòng sau khi phân tích nhân tử và là một mớ hỗn độn trước đó.
- Chứng minh một trường hợp rồi vẫy tay với phần còn lại. “Tương tự” chỉ chấp nhận được khi các trường hợp thật sự đối xứng, và bạn nên nói vì sao.
- Kết luận “sai” trong khi ý bạn là “đôi khi”. Nếu một số hộp đúng, hãy nói hộp nào.
- Quên rằng số dư không bao giờ âm. Chia cho 3, các hộp là 0, 1, 2 — không phải −1, 0, 1.
Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí
Luyện tập Toán rời rạc miễn phí và dùng được khi không có mạng — các bài luyện chọn theo chủ đề về tính chia hết, tính chẵn lẻ, số dư và phương pháp chứng minh.
Luyện tính chia hết và tính chẵn lẻ →Câu hỏi thường gặp#
Điều gì làm một chứng minh theo trường hợp có hiệu lực?
Các trường hợp phải vét cạn — mọi đối tượng bạn đang nói đến đều phải rơi vào ít nhất một trường hợp. Các trường hợp có thể chồng lên nhau mà không hại gì, nhưng một khoảng trống làm hỏng chứng minh, và nó hỏng một cách âm thầm.
Tôi nên chia theo modulus nào?
Hãy khớp nó với khẳng định. Chia hết cho 3 nghĩa là chia theo 3. Bất cứ điều gì về bình phương thường cần 4, và bình phương số lẻ cần 8. Chẵn-và-lẻ chỉ là cách chia theo 2, và nó không cho bạn biết gì về tính chia hết cho bất cứ số nào khác.
Vì sao mọi số chính phương chia cho 4 đều dư 0 hoặc 1?
Vì một số hoặc chẵn hoặc lẻ. Một số chẵn 2m có bình phương 4m², dư 0. Một số lẻ 2m+1 có bình phương 4m² + 4m + 1, dư 1. Không có khả năng thứ ba, nên không số chính phương nào dư 2 hoặc 3.
Số dư chứng minh một phương trình không có nghiệm như thế nào?
Hai số bằng nhau phải có cùng số dư. Nên nếu bạn tìm được một modulus mà hai vế không bao giờ có thể có cùng số dư, thì không thể có nghiệm — và một modulus được chọn tốt giải quyết vô số trường hợp cùng lúc.
Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.