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 đề “Nguyên lý chiếc hộp ở mức tiểu học”.
- 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: Phân 48 đồ vật vào 12 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Hướng dẫn giải chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 3 đồ vật thì tổng nhiều nhất 12×3=36.
Bước 2: Nhưng 48>36, mâu thuẫn với số đồ vật đã cho.
Kết luận: Vì vậy có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Ví dụ 2: Phân 18 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Hướng dẫn giải chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 4×4=16.
Bước 2: Nhưng 18>16, mâu thuẫn với số đồ vật đã cho.
Kết luận: Vì vậy có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Ví dụ 3: Phân 19 đồ vật vào 12 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Hướng dẫn giải chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 1 đồ vật thì tổng nhiều nhất 12×1=12.
Bước 2: Nhưng 19>12, mâu thuẫn với số đồ vật đã cho.
Kết luận: Vì vậy có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Bài tập áp dụng
Bài 1: 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 2: Phân 22 đồ vật vào 11 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Bài 3: Phân 27 đồ vật vào 8 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Bài 4: Phân 36 đồ vật vào 12 hộp. Chứng minh có ít nhất một hộp chứa từ 3 đồ vật trở lên.
Bài 5: Phân 11 đồ vật vào 6 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Xem lời giải
Bài 1: 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 2: Phân 22 đồ vật vào 11 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 11×1=11.
Nhưng 22>11, 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 3: Phân 27 đồ vật vào 8 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 8×3=24.
Nhưng 27>24, 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 4: Phân 36 đồ vật vào 12 hộp. Chứng minh có ít nhất một hộp chứa từ 3 đồ vật trở lên.
Lời giải:
Giả sử mỗi hộp nhiều nhất 2 đồ vật thì tổng nhiều nhất 12×2=24.
Nhưng 36>24, 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ừ 3 đồ vật trở lên.
Bài 5: Phân 11 đồ vật vào 6 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 6×1=6.
Nhưng 11>6, 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 tập tự luyện
Bài 1: 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 2: Phân 10 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 3 đồ vật trở lên.
Bài 3: Phân 45 đồ vật vào 12 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Bài 4: Phân 21 đồ vật vào 5 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Bài 5: Phân 34 đồ vật vào 7 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Bài 6: Phân 11 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 3 đồ vật trở lên.
Bài 7: Phân 19 đồ vật vào 11 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Bài 8: Phân 35 đồ vật vào 9 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Bài 9: Phân 27 đồ vật vào 6 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Bài 10: Phân 26 đồ vật vào 7 hộp. Chứng minh có ít nhất một hộp chứa từ 4 đồ vật trở lên.
Bài 11: Phân 7 đồ vật vào 5 hộp. Chứng minh có ít nhất một hộp chứa từ 2 đồ vật trở lên.
Bài 12: Phân 20 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 5 đồ vật trở lên.
Xem lời giải bài tập tự luyện
Bài 1: 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 11×4=44.
Bước 2: 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 2: Phân 10 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 3 đồ vật trở lên.
Lời giải chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 2 đồ vật thì tổng nhiều nhất 4×2=8.
Bước 2: Nhưng 10>8, 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ừ 3 đồ vật trở lên.
Bài 3: Phân 45 đồ vật vào 12 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 3 đồ vật thì tổng nhiều nhất 12×3=36.
Bước 2: Nhưng 45>36, 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 4: Phân 21 đồ vật vào 5 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 5×4=20.
Bước 2: Nhưng 21>20, 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 5: Phân 34 đồ vật vào 7 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 7×4=28.
Bước 2: Nhưng 34>28, 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 6: Phân 11 đồ vật vào 4 hộp. Chứng minh có ít nhất một hộp chứa từ 3 đồ vật trở lên.
Lời giải chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 2 đồ vật thì tổng nhiều nhất 4×2=8.
Bước 2: Nhưng 11>8, 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ừ 3 đồ vật trở lên.
Bài 7: Phân 19 đồ vật vào 11 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 1 đồ vật thì tổng nhiều nhất 11×1=11.
Bước 2: Nhưng 19>11, 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 8: Phân 35 đồ vật vào 9 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 3 đồ vật thì tổng nhiều nhất 9×3=27.
Bước 2: Nhưng 35>27, 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 9: Phân 27 đồ vật vào 6 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 6×4=24.
Bước 2: Nhưng 27>24, 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 10: Phân 26 đồ vật vào 7 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 3 đồ vật thì tổng nhiều nhất 7×3=21.
Bước 2: Nhưng 26>21, 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 11: Phân 7 đồ vật vào 5 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 1 đồ vật thì tổng nhiều nhất 5×1=5.
Bước 2: Nhưng 7>5, 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 12: Phân 20 đồ vật vào 4 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 chi tiết:
Bước 1: Giả sử mỗi hộp nhiều nhất 4 đồ vật thì tổng nhiều nhất 4×4=16.
Bước 2: Nhưng 20>16, 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 13: 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ó 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: 5 × 1 = 5. Lấy thêm 1, cần 6 vật.
Bài 14: Có 6 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: 6 × 2 = 12. Lấy thêm 1, cần 13 vật.
Bài 15: Có 7 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: 7 × 3 = 21. Lấy thêm 1, cần 22 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.