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 đề “Chọn số để chắc chắn có hai số thỏa mã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: Chọn 28 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 27.
Hướng dẫn giải chi tiết:
Bước 1: Khi chia cho 27, số dư chỉ có thể là 0, 1,…, 26: tổng cộng 27 loại.
Bước 2: Có 28 số được xếp vào 27 nhóm theo số dư.
Kết luận: 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ư.
Ví dụ 2: Chọn 23 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 22.
Hướng dẫn giải chi tiết:
Bước 1: Khi chia cho 22, số dư chỉ có thể là 0, 1,…, 21: tổng cộng 22 loại.
Bước 2: Có 23 số được xếp vào 22 nhóm theo số dư.
Kết luận: 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ư.
Ví dụ 3: Chọn 15 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 14.
Hướng dẫn giải chi tiết:
Bước 1: Khi chia cho 14, số dư chỉ có thể là 0, 1,…, 13: tổng cộng 14 loại.
Bước 2: Có 15 số được xếp vào 14 nhóm theo số dư.
Kết luận: 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 áp dụng
Bài 1: Chọn 14 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 13.
Bài 2: Chọn 17 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 16.
Bài 3: Chọn 29 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 28.
Bài 4: Chọn 16 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 15.
Bài 5: Chọn 30 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 29.
Xem lời giải
Bài 1: Chọn 14 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 13.
Lời giải:
Khi chia cho 13, số dư chỉ có thể là 0, 1,…, 12: tổng cộng 13 loại.
Có 14 số được xếp vào 13 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: Chọn 17 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 16.
Lời giải:
Khi chia cho 16, số dư chỉ có thể là 0, 1,…, 15: tổng cộng 16 loại.
Có 17 số được xếp vào 16 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 3: Chọn 29 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 28.
Lời giải:
Khi chia cho 28, số dư chỉ có thể là 0, 1,…, 27: tổng cộng 28 loại.
Có 29 số được xếp vào 28 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 4: Chọn 16 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 15.
Lời giải:
Khi chia cho 15, số dư chỉ có thể là 0, 1,…, 14: tổng cộng 15 loại.
Có 16 số được xếp vào 15 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 30 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 29.
Lời giải:
Khi chia cho 29, số dư chỉ có thể là 0, 1,…, 28: tổng cộng 29 loại.
Có 30 số được xếp vào 29 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 20 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 19.
Bài 2: Chọn 13 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 12.
Bài 3: Chọn 25 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 24.
Bài 4: Chọn 26 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 25.
Bài 5: Chọn 27 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 26.
Bài 6: Chọn 19 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 18.
Bài 7: Chọn 12 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 11.
Bài 8: Chọn 22 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 21.
Bài 9: 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.
Bài 10: Chọn 21 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 20.
Bài 11: 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 12: 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.
Xem lời giải bài tập tự luyện
Bài 1: Chọn 20 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 19.
Lời giải chi tiết:
Bước 1: Khi chia cho 19, số dư chỉ có thể là 0, 1, …, 18: tổng cộng 19 loại.
Bước 2: Có 20 số được xếp vào 19 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: Chọn 13 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 12.
Lời giải chi tiết:
Bước 1: Khi chia cho 12, số dư chỉ có thể là 0, 1, …, 11: tổng cộng 12 loại.
Bước 2: Có 13 số được xếp vào 12 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 3: Chọn 25 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 24.
Lời giải chi tiết:
Bước 1: Khi chia cho 24, số dư chỉ có thể là 0, 1, …, 23: tổng cộng 24 loại.
Bước 2: Có 25 số được xếp vào 24 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 4: Chọn 26 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 25.
Lời giải chi tiết:
Bước 1: Khi chia cho 25, số dư chỉ có thể là 0, 1, …, 24: tổng cộng 25 loại.
Bước 2: Có 26 số được xếp vào 25 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 27 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 26.
Lời giải chi tiết:
Bước 1: Khi chia cho 26, số dư chỉ có thể là 0, 1, …, 25: tổng cộng 26 loại.
Bước 2: Có 27 số được xếp vào 26 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 6: Chọn 19 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 18.
Lời giải chi tiết:
Bước 1: Khi chia cho 18, số dư chỉ có thể là 0, 1, …, 17: tổng cộng 18 loại.
Bước 2: Có 19 số được xếp vào 18 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 7: Chọn 12 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 11.
Lời giải chi tiết:
Bước 1: Khi chia cho 11, số dư chỉ có thể là 0, 1, …, 10: tổng cộng 11 loại.
Bước 2: Có 12 số được xếp vào 11 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 8: Chọn 22 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 21.
Lời giải chi tiết:
Bước 1: Khi chia cho 21, số dư chỉ có thể là 0, 1, …, 20: tổng cộng 21 loại.
Bước 2: Có 22 số được xếp vào 21 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 9: 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 chi tiết:
Bước 1: Khi chia cho 30, số dư chỉ có thể là 0, 1, …, 29: tổng cộng 30 loại.
Bước 2: 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 10: Chọn 21 số tự nhiên bất kì. Chứng minh luôn có hai số cho cùng số dư khi chia cho 20.
Lời giải chi tiết:
Bước 1: Khi chia cho 20, số dư chỉ có thể là 0, 1, …, 19: tổng cộng 20 loại.
Bước 2: Có 21 số được xếp vào 20 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 11: 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 chi tiết:
Bước 1: Khi chia cho 17, số dư chỉ có thể là 0, 1, …, 16: tổng cộng 17 loại.
Bước 2: 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 12: 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 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.