Mục tiêu bài học
- Hiểu tư duy trường hợp xấu nhất hoặc tối ưu trong chuyên đề “Bài toán tổng hợp nguyên lý chắc chắn”.
- Biết giải thích vì sao số lượng tìm được là đủ và vì sao nhỏ hơn thì chưa chắc chắn.
- Giải được bài phân loại bằng lập luận số học rõ ràng.
Kiến thức cần nhớ
- Bài ‘chắc chắn’ thường xét trường hợp xấu nhất: trì hoãn điều cần đạt lâu nhất rồi lấy thêm 1.
- Khi phân đồ vật vào nhóm, nếu số đồ vật nhiều hơn số nhóm thì phải có nhóm nhận từ 2 đồ vật trở lên.
- Bài tối ưu cần xác định đại lượng giữ nguyên và thử cách phân chia cân đối hoặc lệch nhất tùy mục tiêu.
- Kết quả tối ưu phải được kiểm tra bằng lập luận, không chỉ thử một vài trường hợp.
Ví dụ minh họa
Ví dụ 1: Một túi có bi thuộc 6 màu, mỗi màu có ít nhất 2 viên. Không nhìn, cần lấy ít nhất bao nhiêu viên để chắc chắn có 2 viên cùng màu?
Hướng dẫn giải chi tiết:
Bước 1: Trường hợp xấu nhất, lấy 1 viên ở mỗi màu mà vẫn chưa có 2 viên cùng màu.
Bước 2: Khi đó đã lấy (2−1)×6=6 viên.
Kết luận: Lấy thêm 1 viên chắc chắn tạo đủ 2 viên của một màu; cần 7 viên.
Ví dụ 2: Một túi có bi thuộc 4 màu, mỗi màu có ít nhất 5 viên. Không nhìn, cần lấy ít nhất bao nhiêu viên để chắc chắn có 5 viên cùng màu?
Hướng dẫn giải chi tiết:
Bước 1: Trường hợp xấu nhất, lấy 4 viên ở mỗi màu mà vẫn chưa có 5 viên cùng màu.
Bước 2: Khi đó đã lấy (5−1)×4=16 viên.
Kết luận: Lấy thêm 1 viên chắc chắn tạo đủ 5 viên của một màu; cần 17 viên.
Ví dụ 3: Một túi có bi thuộc 7 màu, mỗi màu có ít nhất 4 viên. Không nhìn, cần lấy ít nhất bao nhiêu viên để chắc chắn có 4 viên cùng màu?
Hướng dẫn giải chi tiết:
Bước 1: Trường hợp xấu nhất, lấy 3 viên ở mỗi màu mà vẫn chưa có 4 viên cùng màu.
Bước 2: Khi đó đã lấy (4−1)×7=21 viên.
Kết luận: Lấy thêm 1 viên chắc chắn tạo đủ 4 viên của một màu; cần 22 viên.
Bài tập áp dụng
Bài 1: Phân 15 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Bài 2: Phân 55 đồ vật vào 11 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Bài 3: Phân 17 đồ vật vào 9 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Bài 4: Chọn 18 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 17.
Bài 5: Chọn 31 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 30.
Xem lời giải
Bài 1: Phân 15 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Lời giải:
Giả sử mỗi hộp nhiều nhất 3 đồ vật thì tổng nhiều nhất 4×3=12.
Nhưng 15>12, mâu thuẫn với số đồ vật đã cho.
Đáp số: Vì vậy có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Bài 2: Phân 55 đồ vật vào 11 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Lời giải:
Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 11×4=44.
Nhưng 55>44, mâu thuẫn với số đồ vật đã cho.
Đáp số: Vì vậy có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Bài 3: Phân 17 đồ vật vào 9 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Lời giải:
Giả sử mỗi hộp nhiều nhất 1 đồ vật thì tổng nhiều nhất 9×1=9.
Nhưng 17>9, mâu thuẫn với số đồ vật đã cho.
Đáp số: Vì vậy có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Bài 4: Chọn 18 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 17.
Lời giải:
Khi chia cho 17, số dư chỉ có thể là 0, 1,…, 16: tổng cộng 17 loại.
Có 18 số được xếp vào 17 nhóm theo số dư.
Đáp số: Vì số được chọn nhiều hơn số nhóm, ít nhất một nhóm có hai số; hai số đó có cùng số dư.
Bài 5: Chọn 31 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 30.
Lời giải:
Khi chia cho 30, số dư chỉ có thể là 0, 1,…, 29: tổng cộng 30 loại.
Có 31 số được xếp vào 30 nhóm theo số dư.
Đáp số: Vì số được chọn nhiều hơn số nhóm, ít nhất một nhóm có hai số; hai số đó có cùng số dư.
Bài tập tự luyện
Bài 1: Chọn 24 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 23.
Bài 2: Hai số tự nhiên có tổng 69. Tìm tích lớn nhất và giải thích vì sao hai số phải gần nhau nhất.
Bài 3: Hai số tự nhiên có tổng 90. Tìm tích lớn nhất và giải thích vì sao hai số phải gần nhau nhất.
Bài 4: Hai số tự nhiên có tổng 45. Tìm tích lớn nhất và giải thích vì sao hai số phải gần nhau nhất.
Bài 5: Hai số tự nhiên dương có tổng 109, mỗi số không nhỏ hơn 33. Tìm tích nhỏ nhất.
Bài 6: Hai số tự nhiên dương có tổng 59, mỗi số không nhỏ hơn 5. Tìm tích nhỏ nhất.
Bài 7: Hai số tự nhiên dương có tổng 72, mỗi số không nhỏ hơn 21. Tìm tích nhỏ nhất.
Bài 8: Chia 62 phần quà vào 3 nhóm sao cho số quà giữa hai nhóm bất kì chênh nhau không quá 1. Mỗi nhóm nhận bao nhiêu và có bao nhiêu nhóm nhận nhiều hơn?
Bài 9: Chia 81 phần quà vào 9 nhóm sao cho số quà giữa hai nhóm bất kì chênh nhau không quá 1. Mỗi nhóm nhận bao nhiêu và có bao nhiêu nhóm nhận nhiều hơn?
Bài 10: Chia 82 phần quà vào 6 nhóm sao cho số quà giữa hai nhóm bất kì chênh nhau không quá 1. Mỗi nhóm nhận bao nhiêu và có bao nhiêu nhóm nhận nhiều hơn?
Bài 11: Cần ít nhất 93 sản phẩm. Ba gói lần lượt chứa 28, 24, 24 sản phẩm, giá 58, 62, 112 nghìn đồng. Nếu chỉ mua một loại gói, chọn loại nào rẻ nhất?
Bài 12: Cần ít nhất 105 sản phẩm. Ba gói lần lượt chứa 26, 16, 20 sản phẩm, giá 126, 110, 120 nghìn đồng. Nếu chỉ mua một loại gói, chọn loại nào rẻ nhất?
Xem lời giải bài tập tự luyện
Bài 1: Chọn 24 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 23.
Lời giải chi tiết:
Bước 1: Khi chia cho 23, số dư chỉ có thể là 0, 1, …, 22: tổng cộng 23 loại.
Bước 2: Có 24 số được xếp vào 23 nhóm theo số dư.
Đáp số: Vì số được chọn nhiều hơn số nhóm, ít nhất một nhóm có hai số; hai số đó có cùng số dư.
Bài 2: Hai số tự nhiên có tổng 69. Tìm tích lớn nhất và giải thích vì sao hai số phải gần nhau nhất.
Lời giải chi tiết:
Bước 1: Xét hai số lệch nhau từ 2 trở lên; chuyển 1 đơn vị từ số lớn sang số bé làm tổng không đổi.
Bước 2: Sau chuyển, tích tăng vì hai số gần nhau hơn; tiếp tục đến khi hai số bằng nhau hoặc hơn kém 1.
Đáp số: Hai số tối ưu là 34 và 35; tích lớn nhất 34×35=1190.
Bài 3: Hai số tự nhiên có tổng 90. Tìm tích lớn nhất và giải thích vì sao hai số phải gần nhau nhất.
Lời giải chi tiết:
Bước 1: Xét hai số lệch nhau từ 2 trở lên; chuyển 1 đơn vị từ số lớn sang số bé làm tổng không đổi.
Bước 2: Sau chuyển, tích tăng vì hai số gần nhau hơn; tiếp tục đến khi hai số bằng nhau hoặc hơn kém 1.
Đáp số: Hai số tối ưu là 45 và 45; tích lớn nhất 45×45=2025.
Bài 4: Hai số tự nhiên có tổng 45. Tìm tích lớn nhất và giải thích vì sao hai số phải gần nhau nhất.
Lời giải chi tiết:
Bước 1: Xét hai số lệch nhau từ 2 trở lên; chuyển 1 đơn vị từ số lớn sang số bé làm tổng không đổi.
Bước 2: Sau chuyển, tích tăng vì hai số gần nhau hơn; tiếp tục đến khi hai số bằng nhau hoặc hơn kém 1.
Đáp số: Hai số tối ưu là 22 và 23; tích lớn nhất 22×23=506.
Bài 5: Hai số tự nhiên dương có tổng 109, mỗi số không nhỏ hơn 33. Tìm tích nhỏ nhất.
Lời giải chi tiết:
Bước 1: Để tích nhỏ nhất với tổng không đổi, hai số phải xa nhau nhất trong phạm vi cho phép.
Bước 2: Số nhỏ nhất có thể là 33, số kia là 109−33=76.
Đáp số: Tích nhỏ nhất là 33×76=2508.
Bài 6: Hai số tự nhiên dương có tổng 59, mỗi số không nhỏ hơn 5. Tìm tích nhỏ nhất.
Lời giải chi tiết:
Bước 1: Để tích nhỏ nhất với tổng không đổi, hai số phải xa nhau nhất trong phạm vi cho phép.
Bước 2: Số nhỏ nhất có thể là 5, số kia là 59−5=54.
Đáp số: Tích nhỏ nhất là 5×54=270.
Bài 7: Hai số tự nhiên dương có tổng 72, mỗi số không nhỏ hơn 21. Tìm tích nhỏ nhất.
Lời giải chi tiết:
Bước 1: Để tích nhỏ nhất với tổng không đổi, hai số phải xa nhau nhất trong phạm vi cho phép.
Bước 2: Số nhỏ nhất có thể là 21, số kia là 72−21=51.
Đáp số: Tích nhỏ nhất là 21×51=1071.
Bài 8: Chia 62 phần quà vào 3 nhóm sao cho số quà giữa hai nhóm bất kì chênh nhau không quá 1. Mỗi nhóm nhận bao nhiêu và có bao nhiêu nhóm nhận nhiều hơn?
Lời giải chi tiết:
Bước 1: Chia đều: 62:3=20 dư 2.
Bước 2: Mỗi nhóm nhận ít nhất 20; phân thêm 1 phần cho 2 nhóm.
Đáp số: Có 2 nhóm nhận 21 phần và 1 nhóm nhận 20 phần.
Bài 9: Chia 81 phần quà vào 9 nhóm sao cho số quà giữa hai nhóm bất kì chênh nhau không quá 1. Mỗi nhóm nhận bao nhiêu và có bao nhiêu nhóm nhận nhiều hơn?
Lời giải chi tiết:
Bước 1: Chia đều: 81:9=9 dư 0.
Bước 2: Mỗi nhóm nhận ít nhất 9; phân thêm 1 phần cho 0 nhóm.
Đáp số: Có 0 nhóm nhận 10 phần và 9 nhóm nhận 9 phần.
Bài 10: Chia 82 phần quà vào 6 nhóm sao cho số quà giữa hai nhóm bất kì chênh nhau không quá 1. Mỗi nhóm nhận bao nhiêu và có bao nhiêu nhóm nhận nhiều hơn?
Lời giải chi tiết:
Bước 1: Chia đều: 82:6=13 dư 4.
Bước 2: Mỗi nhóm nhận ít nhất 13; phân thêm 1 phần cho 4 nhóm.
Đáp số: Có 4 nhóm nhận 14 phần và 2 nhóm nhận 13 phần.
Bài 11: Cần ít nhất 93 sản phẩm. Ba gói lần lượt chứa 28, 24, 24 sản phẩm, giá 58, 62, 112 nghìn đồng. Nếu chỉ mua một loại gói, chọn loại nào rẻ nhất?
Lời giải chi tiết:
Bước 1: Tính số gói cần mua cho từng loại bằng cách chia 93 rồi làm tròn lên: 4, 4, 4 gói.
Bước 2: Tổng tiền tương ứng: 232, 248, 448 nghìn đồng.
Đáp số: Phương án rẻ nhất là loại 1, hết 232 nghìn đồng.
Bài 12: Cần ít nhất 105 sản phẩm. Ba gói lần lượt chứa 26, 16, 20 sản phẩm, giá 126, 110, 120 nghìn đồng. Nếu chỉ mua một loại gói, chọn loại nào rẻ nhất?
Lời giải chi tiết:
Bước 1: Tính số gói cần mua cho từng loại bằng cách chia 105 rồi làm tròn lên: 5, 7, 6 gói.
Bước 2: Tổng tiền tương ứng: 630, 770, 720 nghìn đồng.
Đáp số: Phương án rẻ nhất là loại 1, hết 630 nghìn đồng.
Bài 13: Có 3 nhóm, mỗi nhóm có đủ nhiều vật. Cần lấy ít nhất bao nhiêu vật để chắc chắn có 2 vật thuộc cùng một nhóm?
Lời giải
Trường hợp xấu nhất lấy 1 vật ở mỗi nhóm: 3 × 1 = 3. Lấy thêm 1, cần 4 vật.
Bài 14: Có 4 nhóm, mỗi nhóm có đủ nhiều vật. Cần lấy ít nhất bao nhiêu vật để chắc chắn có 3 vật thuộc cùng một nhóm?
Lời giải
Trường hợp xấu nhất lấy 2 vật ở mỗi nhóm: 4 × 2 = 8. Lấy thêm 1, cần 9 vật.
Bài 15: Có 5 nhóm, mỗi nhóm có đủ nhiều vật. Cần lấy ít nhất bao nhiêu vật để chắc chắn có 4 vật thuộc cùng một nhóm?
Lời giải
Trường hợp xấu nhất lấy 3 vật ở mỗi nhóm: 5 × 3 = 15. Lấy thêm 1, cần 16 vật.
Ghi nhớ
- Bài ‘chắc chắn’ thường xét trường hợp xấu nhất: trì hoãn điều cần đạt lâu nhất rồi lấy thêm 1.
- Khi phân đồ vật vào nhóm, nếu số đồ vật nhiều hơn số nhóm thì phải có nhóm nhận từ 2 đồ vật trở lên.
- Bài tối ưu cần xác định đại lượng giữ nguyên và thử cách phân chia cân đối hoặc lệch nhất tùy mục tiêu.