Trường hợp xấu nhất, cân và tìm kiếm
Câu hỏi có chữ “chắc chắn” chiếm khoảng 3,9% đề Tin học trẻ Bảng M1, M2 năm 2025-2026: lấy bao nhiêu viên bi để chắc chắn có đủ màu, cân mấy lần để chắc chắn tìm được đồng xu giả. Cách nghĩ chung: tưởng tượng mọi chuyện diễn ra theo cách xấu nhất có thể, rồi tính cho trường hợp đó.
Dạng 1. Lấy đồ trong trường hợp xấu nhất
Phần tiêu đề “Dạng 1. Lấy đồ trong trường hợp xấu nhất”Hộp có 5 bi đỏ, 3 bi xanh. Lấy ít nhất bao nhiêu viên để chắc chắn có bi xanh?
Trường hợp xấu nhất: lấy được hết bi đỏ trước (5 viên). Viên thứ 6 chắc chắn là xanh. Đáp số 6.
Công thức chung: (số đồ lấy được trong trường hợp xấu nhất mà chưa đạt yêu cầu) + 1.
| Muốn chắc chắn có | Trường hợp xấu nhất |
|---|---|
| 2 cái cùng màu | mỗi màu 1 cái |
| k cái cùng màu | mỗi màu k − 1 cái (màu nào ít hơn thì lấy hết) |
| đủ mọi màu | lấy hết các màu nhiều nhất, thiếu đúng một màu |
| 1 cái màu X | lấy hết các màu khác X |
Lưu ý: câu “lấy k cái bất kỳ luôn có màu X” đọc ngược lại là: số cái không phải màu X nhiều nhất là k − 1.
Dạng 2. Nguyên lý Dirichlet
Phần tiêu đề “Dạng 2. Nguyên lý Dirichlet”Nhốt nhiều thỏ hơn số chuồng thì có chuồng chứa ít nhất 2 thỏ. Tổng quát hơn: nhốt n thỏ vào k chuồng thì có chuồng chứa ít nhất n : k (làm tròn lên) thỏ.
Bí quyết là chọn đúng chuồng:
| Bài toán | Chuồng |
|---|---|
| Sinh cùng tháng | 12 tháng |
| Hai số có hiệu chia hết cho 7 | 7 số dư khi chia cho 7 |
| Hai số có tổng bằng 21 trong 1..20 | 10 cặp (1, 20), (2, 19), …, (10, 11) |
| Hai điểm gần nhau trong hình vuông | các ô vuông nhỏ chia từ hình vuông |
Chi tiết hơn ở bài Nguyên lý Dirichlet bên Toán tin.
Dạng 3. Cân hai đĩa
Phần tiêu đề “Dạng 3. Cân hai đĩa”Mỗi lần cân có 3 kết quả: lệch trái, lệch phải, thăng bằng. Tìm 1 đồng xu nhẹ hơn trong n đồng: chia làm 3 nhóm, đặt hai nhóm bằng nhau lên hai đĩa, nhóm thứ ba để ngoài.
| Số lần cân | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Tìm được trong nhiều nhất | 3 đồng | 9 đồng | 27 đồng | 81 đồng |
Cân điện tử (hiện số gam): lấy số đồng khác nhau từ mỗi túi (1, 2, 3, …) rồi cân một lần; độ hụt so với khi toàn tiền thật cho biết túi giả.
Lưu ý: biết đồng giả nặng hơn hay nhẹ hơn thì dễ hơn nhiều so với không biết.
Dạng 4. Đếm số khả năng
Phần tiêu đề “Dạng 4. Đếm số khả năng”Muốn biết ít nhất cần bao nhiêu lần hỏi, cân, so sánh: đếm số khả năng cần phân biệt, rồi xem mỗi lần cho bao nhiêu kết quả.
- Câu hỏi có/không: k câu phân biệt được 2 × 2 × … × 2 (k lần) khả năng. Đoán số từ 1 đến 30 cần 5 câu (32 ≥ 30).
- So sánh hai vật: cũng 2 kết quả. Sắp xếp 3 vật có 6 thứ tự; 2 lần so chỉ phân biệt được 4 thứ tự, chưa đủ 6, nên cần ít nhất 3 lần so.
- Cân hai đĩa: 3 kết quả mỗi lần.
Con số tính được là chặn dưới. Sau đó còn phải chỉ ra một cách làm đạt đúng số lần đó.
Dạng 5. “Chắc chắn” là phần chung của mọi trường hợp
Phần tiêu đề “Dạng 5. “Chắc chắn” là phần chung của mọi trường hợp”Khi đề hỏi “ô nào chắc chắn”, “bạn nào chắc chắn”, hãy liệt kê mọi trường hợp có thể rồi lấy phần chung. Thường chỉ cần xét hai trường hợp ở hai đầu (sớm nhất và muộn nhất, nhỏ nhất và lớn nhất).
Lưu ý: “biết chắc” không đòi hỏi phải kiểm tra hết: khi phần còn lại chỉ có một khả năng thì đã biết rồi, không cần thử thêm (chìa khóa cuối cùng, bạn cuối cùng).
Luyện tập
Phần tiêu đề “Luyện tập”Gồm 20 bài, chia thành 5 nhóm từ dễ đến khó. Nhãn M1 là mức đề tiểu học, M2 là mức đề THCS. Mỗi bài có đáp số để các bạn tự kiểm tra sau khi làm.
Nhóm 1. Lấy bi trong trường hợp xấu nhất
Phần tiêu đề “Nhóm 1. Lấy bi trong trường hợp xấu nhất”Bài 1. Chắc chắn có hai bi cùng màu (M1)
Phần tiêu đề “Bài 1. Chắc chắn có hai bi cùng màu (M1)”Hộp có 15 viên bi: 6 đỏ, 5 xanh, 4 vàng. Nhắm mắt lấy bi, không nhìn. Phải lấy ít nhất bao nhiêu viên để chắc chắn có 2 viên cùng màu?
Bài 2. Chắc chắn có đủ ba màu (M1)
Phần tiêu đề “Bài 2. Chắc chắn có đủ ba màu (M1)”Vẫn hộp bi 6 đỏ, 5 xanh, 4 vàng. Phải lấy ít nhất bao nhiêu viên để chắc chắn có đủ cả 3 màu?
Bài 3. Chắc chắn có 4 bi cùng màu (M1)
Phần tiêu đề “Bài 3. Chắc chắn có 4 bi cùng màu (M1)”Vẫn hộp bi 6 đỏ, 5 xanh, 4 vàng. Phải lấy ít nhất bao nhiêu viên để chắc chắn có 4 viên cùng màu?
Bài 4. Chắc chắn có hai bi khác màu (M1)
Phần tiêu đề “Bài 4. Chắc chắn có hai bi khác màu (M1)”Hộp có 8 viên bi đỏ, 6 viên bi xanh, 8 viên bi vàng. Phải lấy ít nhất bao nhiêu viên để chắc chắn có 2 viên khác màu?
Bài 5. Tủ que kem (M2)
Phần tiêu đề “Bài 5. Tủ que kem (M2)”Tủ có các que kem vị đậu xanh, vị cốm và vị sữa dừa. Biết rằng: lấy 8 que bất kỳ luôn có ít nhất 1 que đậu xanh; lấy 10 que bất kỳ luôn có ít nhất 1 que cốm; lấy 12 que bất kỳ luôn có ít nhất 1 que sữa dừa. Tủ có nhiều nhất bao nhiêu que kem?
Nhóm 2. Nguyên lý Dirichlet
Phần tiêu đề “Nhóm 2. Nguyên lý Dirichlet”Bài 6. Sinh cùng tháng (M1)
Phần tiêu đề “Bài 6. Sinh cùng tháng (M1)”Lớp có 40 bạn. Chắc chắn có ít nhất bao nhiêu bạn sinh cùng một tháng?
Bài 7. Hai số có tổng 50 (M1)
Phần tiêu đề “Bài 7. Hai số có tổng 50 (M1)”Gấu có 49 quả bóng ghi số 1, 2, …, 49. Phải lấy ra ít nhất bao nhiêu quả (không nhìn số) để chắc chắn có 2 quả có tổng hai số bằng 50?
Bài 8. Hiệu chia hết cho 7 (M1)
Phần tiêu đề “Bài 8. Hiệu chia hết cho 7 (M1)”Phải chọn ít nhất bao nhiêu số tự nhiên bất kỳ để chắc chắn có 2 số mà hiệu của chúng chia hết cho 7?
Bài 9. Điểm trong hình vuông (M2)
Phần tiêu đề “Bài 9. Điểm trong hình vuông (M2)”Hình vuông cạnh 3 cm. Phải đặt ít nhất bao nhiêu điểm trong hình vuông (kể cả trên cạnh) để chắc chắn có 2 điểm nằm trong cùng một ô vuông cạnh 1 cm, khi chia hình vuông thành lưới 3 × 3 ô?
Nhóm 3. Cân và so sánh
Phần tiêu đề “Nhóm 3. Cân và so sánh”Bài 10. Túi tiền giả (M1)
Phần tiêu đề “Bài 10. Túi tiền giả (M1)”Có 9 túi tiền trông giống hệt nhau, trong đó 8 túi thật nặng bằng nhau và 1 túi giả nhẹ hơn. Dùng một cái cân hai đĩa (không có quả cân), cần ít nhất bao nhiêu lần cân để chắc chắn tìm ra túi giả?
Bài 11. Một trăm quả bóng (M2)
Phần tiêu đề “Bài 11. Một trăm quả bóng (M2)”Có 100 quả bóng giống hệt nhau, trong đó 99 quả nặng bằng nhau và 1 quả nhẹ hơn. Dùng cân hai đĩa, cần ít nhất bao nhiêu lần cân để chắc chắn tìm ra quả nhẹ?
Bài 12. Cân điện tử một lần (M1)
Phần tiêu đề “Bài 12. Cân điện tử một lần (M1)”Có 9 túi tiền đánh số 1 đến 9. Đồng tiền thật nặng 10 g, nhưng có đúng một túi chứa toàn đồng giả nặng 9 g. Dùng cân điện tử (hiện số gam), Bin lấy từ túi số 1 một đồng, túi số 2 hai đồng, …, túi số 9 chín đồng, cân tất cả một lần được 442 g. Túi nào chứa tiền giả?
Bài 13. Xếp bốn hộp theo khối lượng (M2)
Phần tiêu đề “Bài 13. Xếp bốn hộp theo khối lượng (M2)”Có 4 hộp khối lượng khác nhau. Mỗi lần dùng cân hai đĩa so sánh hai hộp để biết hộp nào nặng hơn. Cần ít nhất bao nhiêu lần so để chắc chắn xếp được 4 hộp từ nhẹ đến nặng?
Bài 14. Tìm hộp nặng nhất và nhẹ nhất (M2)
Phần tiêu đề “Bài 14. Tìm hộp nặng nhất và nhẹ nhất (M2)”Có 4 hộp khối lượng khác nhau. Mỗi lần so sánh hai hộp bằng cân hai đĩa. Cần ít nhất bao nhiêu lần so để chắc chắn biết hộp nặng nhất và hộp nhẹ nhất (không cần xếp thứ tự các hộp ở giữa)?
Nhóm 4. Đoán và dò tìm
Phần tiêu đề “Nhóm 4. Đoán và dò tìm”Bài 15. Đoán số từ 1 đến 100 (M1)
Phần tiêu đề “Bài 15. Đoán số từ 1 đến 100 (M1)”An nghĩ một số từ 1 đến 100. Bình được hỏi các câu hỏi mà An chỉ trả lời “có” hoặc “không” (ví dụ “Số đó lớn hơn 50 phải không?”). Bình cần ít nhất bao nhiêu câu hỏi để chắc chắn biết số đó?
Bài 16. Thả trứng từ tòa tháp (M2)
Phần tiêu đề “Bài 16. Thả trứng từ tòa tháp (M2)”Tòa tháp có 100 tầng. Có một tầng T: thả trứng từ tầng T trở xuống thì không vỡ, từ cao hơn T thì vỡ (T có thể từ 0 đến 100). Bạn có 2 quả trứng, trứng chưa vỡ thì dùng lại được. Cần ít nhất bao nhiêu lần thả để chắc chắn tìm ra T?
Bài 17. Bắn tàu (M2)
Phần tiêu đề “Bài 17. Bắn tàu (M2)”Alice giấu một con tàu chiếm 3 ô liền nhau (theo hàng ngang hoặc cột dọc) trên bảng 4 × 4. Bob chọn một số ô để bắn cùng lúc. Bob cần bắn ít nhất bao nhiêu ô để chắc chắn trúng tàu, dù tàu giấu ở đâu?
Nhóm 5. Chắc chắn biết
Phần tiêu đề “Nhóm 5. Chắc chắn biết”Bài 18. Kiểm tra vở bài tập (M1)
Phần tiêu đề “Bài 18. Kiểm tra vở bài tập (M1)”Lớp có 10 bạn, trong đó có đúng 2 bạn quên vở bài tập. Cô giáo kiểm tra lần lượt từng bạn. Trong trường hợp xấu nhất, cô phải kiểm tra bao nhiêu bạn để biết chắc 2 bạn quên vở là ai?
Bài 19. Ô chắc chắn được tô (M1)
Phần tiêu đề “Bài 19. Ô chắc chắn được tô (M1)”Có 12 ô vuông xếp thành một hàng, đánh số 1 đến 12. Tâm đặt 9 quân cờ đen vào 9 ô liên tiếp nào đó (không biết là 9 ô nào). Có bao nhiêu ô chắc chắn có quân cờ?
Bài 20. Thử chìa khóa (M1)
Phần tiêu đề “Bài 20. Thử chìa khóa (M1)”Có 6 ổ khóa và 6 chiếc chìa, mỗi chìa mở đúng một ổ nhưng chưa biết chìa nào mở ổ nào. Mỗi lần thử là cắm một chìa vào một ổ. Trong trường hợp xấu nhất, cần thử bao nhiêu lần để biết hết chìa nào mở ổ nào?
© 2026 Bumbii Academy. Toàn bộ nội dung thuộc bản quyền của Bumbii Academy, nghiêm cấm sao chép dưới mọi hình thức khi chưa được cho phép.