tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG II BÀI TOÁN ĐẾM_2

Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là bằng k. Điều này trái giả thiết là có ít nhất k + 1 vật | CHƯƠNG II BÀI TOÁN ĐẾM Chứng minh Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó tổng số vật được chứa trong các hộp nhiều nhất là bằng k. Điều này trái giả thiết là có ít nhất k 1 vật. Nguyên lý này thường được gọi là nguyên lý Dirichlet mang tên nhà toán học người Đức ở thế kỷ 19. Ông thường xuyên sử dụng nguyên lý này trong công việc của mình. Thí dụ 4 1 Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau. 2 Trong kỳ thi học sinh giỏi điểm bài thi được đánh giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng ít nhất có bao nhiêu học sinh dự thi để cho chắc chắn tìm được hai học sinh có kết quả thi như nhau Theo nguyên lý Dirichlet số học sinh cần tìm là 102 vì ta có 101 kết quả điểm thi khác nhau. 3 Trong số những người có mặt trên trái đất phải tìm được hai người có hàm răng giống nhau. Nếu xem mỗi hàm răng gồm 32 cái như là một xâu nhị phân có chiều dài 32 trong đó răng còn ứng với bit 1 và răng mất ứng với bit 0 thì có tất cả 232 hàm răng khác nhau. Trong khi đó số người trên hành tinh này là vượt quá 5 tỉ nên theo nguyên lý Dirichlet ta có điều cần tìm. . Nguyên lý Dirichlet tổng quát Mệnh đề Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất N k đồ vật. Ở đây x là giá trị của hàm trần tại số thực x đó là số nguyên nhỏ nhất có giá trị lớn hơn hoặc bằng x. Khái niệm này đối ngẫu với x - giá trị của hàm sàn hay hàm phần nguyên tại x - là số nguyên lớn nhất có giá trị nhỏ hơn hoặc bằng x. Chứng minh Giả sử mọi hộp đều chứa ít hơn N k vật. Khi đó tổng số đồ vật là k N - 1 k N N. Điều này mâu thuẩn với giả thiết là có N đồ vật cần xếp. Thí dụ 5 1 Trong 100 người có ít nhất 9 người sinh cùng một tháng. Xếp những người sinh cùng tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo nguyên lý Dirichlet tồn tại một nhóm có ít nhất 100 12 9 người. 2 Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao