tailieunhanh - Toán rời rạc: Bài tập phần nguyên lý chuồng bồ câu

Toán rời rạc: Bài tập phần nguyên lý chuồng bồ câu gồm các bài tập tự luận phần nguyên lý chuồng bồ câu nhằm giúp người học củng cố kiến thực được học đồng thời thử sức mình qua các bài tập tham khảo dưới đây. | Toán rời rạc Bài tập phần nguyên lý chuồng bồ câu 1. Một cờ thủ có 11 tuần để chuẩn bị đấu giải. Anh ta quyết tâm chơi mỗi ngày một trận, nhưng để giữ sức anh ta quyết không chơi quá 12 trận một tuần. Chứng minh rằng có một giai đoạn (gồm những ngày liên tiếp) anh ta chơi đúng 21 trận. 2. Với giả thiết như trong bài tập 1, hãy chứng minh rằng có một giai đoạn (gồm những ngày liên tiếp) anh ta chơi đúng k trận, với k = 1, 2, . . . , 21. Liệu có thể kết luận rằng có giai đoạn anh này chơi 22 trận liên tiếp được không? 3. * Chứng minh rằng nếu chọn 100 số nguyên từ tập 1, 2, . . . , 200, và một trong các số được chọn nhỏ hơn 16, vậy có hai trong các số được chọn mà số này chia hết cho số kia. 4. Tổng quát hoá ví dụ trước để cho phép chọn (bao nhiêu?) số từ tập {1, 2, . . . , 2n}. 5. Chứng minh rằng nếu chọn n + 1 số nguyên từ tập {1, 2, . . . , 2n}, vậy ít nhất có hai số chỉ hơn kém nhau một. 6. Chứng minh rằng nếu chọn n + 1 số nguyên từ tập {1, 2, . . . , 3n}, vậy ít nhất có hai số chỉ hơn kém nhau hai. 7. Tổng quát hoá bài tập 5 và 6. 8. * Chứng minh rằng cho trước 52 số nguyên luôn tồn tại hai số trong đó tổng, hoặc hiệu của chúng chia hết cho 100. 9. Dùng nguyên lý chuồng bồ câu để chứng minh rằng khai triển thập phân của một số hữu tử m/n phải lặp lại. Ví dụ 34, 478 = · · · . 99, 900 10. Trong phòng có 10 người, không ai trong số họ lớn hơn 60 hoặc ít hơn một tuổi. Chứng minh rằng chúng ta luôn tìm thấy hai nhóm phân biệt có tổng số tuổi bằng nhau. Liệu 10 có phải số nhỏ nhất không? 11. Một đứa bé xem TV ít nhất một giờ mỗi ngày trong bảy tuần nhưng không xem quá 11 giờ mỗi tuần (vì cha mẹ cấm). Chứng minh rằng có một giai đoạn gồm những ngày liên tiếp mà đứa bé này xem TV đúng 20 giờ. (Giả sử số giờ xem TV luôn là số nguyên.) 12. Một sinh viên có 37 ngày để chuẩn bị kiểm tra. Kinh nghiệm cho thấy rằng cô không cần học nhiều hơn 60 giờ. Cô ấy cũng muốn học mỗi ngày ít nhất một giờ. Chứng minh rằng dù cô ấy xếp lịch học thế nào thì luôn có