Con chim bay đi!

30

KVANT 2017/№1

Con chim bay đi!

HÃY XEM XÉT MỘT SỐ BÀI TẬP được đặt ra ở câu lạc bộ Cơ học nhỏ và Toán lớp 6. Trong mỗi bài toán, để biện minh cho đáp số, bạn cần đưa ra một ví dụ thỏa mãn điều kiện và chứng minh rằng ví dụ này không thể cải thiện được. Bài toán 1. 50 con chim bay vào studio ảnh - 18 con sáo, 17 con chìa vôi và 15 con chim gõ kiến. Mỗi khi nhiếp ảnh gia bấm nút chụp máy ảnh, một trong những con chim sẽ bay đi (rõ ràng là vậy). Số lượng khung hình tối đa mà một nhiếp ảnh gia có thể chụp để chắc chắn rằng anh ta sẽ có được cả ba loài chim trong studio của mình là bao nhiêu? bài toán này rất đơn giản: nếu nhiếp ảnh gia chụp 15 khung hình, có thể xảy ra trường hợp tất cả chim gõ kiến ​​bay đi và chỉ còn lại chim sáo đá và chim chìa vôi. Nếu chỉ có 14 khung hình thì không quá 14 con chim thuộc bất kỳ loài nào có thể bay đi - nghĩa là ít nhất một con trong mỗi loài sẽ còn lại. Đáp số: 14. Ở đây chúng ta đã giải quyết được vấn đề kép bài toán: số lượng khung hình nhỏ nhất đủ để những chú chim “đánh bại” nhiếp ảnh gia là bao nhiêu (để đảm bảo rằng điều kiện của anh ta không được đáp ứng). Nếu có ít nhất 15 khung hình thì chim quỷ quyệt có “chiến lược” (chim gõ kiến ​​bay đi), nếu có 14 khung hình trở xuống thì không có chiến lược. Chúng ta hãy xem xét bài toán phức tạp hơn từ quan điểm này. Bài toán 2. 50 con chim bay vào studio ảnh - 18 con sáo, 17 con chìa vôi và 15 con chim gõ kiến. Mỗi khi nhiếp ảnh gia bấm nút chụp máy ảnh, một trong những con chim sẽ bay đi (rõ ràng là vậy). Số lượng khung hình lớn nhất mà một nhiếp ảnh gia có thể chụp để chắc chắn là bao nhiêu:

giải đấu sẽ có ít nhất 10 con chim của một loài nào còn lại? Các loài chim ở đây cần giảm số lượng mỗi loài xuống dưới 10. Để làm được điều này, phải bay đi ít nhất 9 con sáo, ít nhất 8 con chìa vôi và ít nhất 6 con chim gõ kiến ​​- tổng cộng ít nhất 23 con. Điều này có nghĩa là nếu có 22 khung hình thì không có chiến lược nào và nhiếp ảnh gia có thể chắc chắn rằng tình trạng của mình sẽ không bị vi phạm. Nếu có ít nhất 23 khung hình thì không còn độ tin cậy nữa. Đáp số: 22. Và cuối cùng, thêm một biến thể nữa. Bài toán 3. Trong cùng điều kiện, hãy xác định số lượng khung hình lớn nhất mà nhiếp ảnh gia có thể chụp để đảm bảo: ít nhất 11 con chim thuộc một loài và ít nhất 10 con chim thuộc loài khác sẽ vẫn ở trong studio. Ở đây nhiếp ảnh gia đang “một mũi tên đuổi hai con chim” (anh ta muốn đáp ứng hai điều kiện cùng một lúc), và để lũ chim đánh bại anh ta, chỉ cần “giết” ít nhất một trong số chúng là đủ. Dịch từ ngôn ngữ thỏ sang ngôn ngữ chim, hãy đảm bảo rằng không có quá 10 con chim của mỗi loài hoặc cho phép bao nhiêu con chim của một loài nhất định tùy thích, nhưng sau đó không được nhiều hơn 9 con của mỗi loài khác loài. Hãy xem chiến lược nào tiết kiệm hơn về số lượng chim bay đi. Trong trường hợp đầu tiên, 8 con sáo, 7 con chim chìa vôi và 5 con chim gõ kiến ​​“thêm” phải bay đi - tổng cộng là 20 con chim. Trong trường hợp thứ hai, chúng ta cần chọn một loài mà chúng ta không áp đặt các hạn chế về số lượng. Rõ ràng đây phải là chim sáo - còn nhiều hơn nữa. Sau đó, ít nhất 8 con chim chìa vôi và 6 con chim gõ kiến ​​sẽ bay đi - tổng cộng