Mở đầu: Giả sử có một đàn chim bổ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩ nhiên là có thể áp dụng cho các đối t- ợng không phải là chim bồ câu và 13 chuồng chim. Mệnh đề (Nguyên lý): Nếu có k +1 (hoặc nhiều hơn) đồ vạt được đặt vào trong k hộp thì tồn tại một hộp có ít nhất hai đồ vật.
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. Ví dụ: 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 = 4.296 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 N N chứa không ít hơn đổ vât.(hay tổn tại hộp có ít nhất [ ] đổ vât) (Ớ đây, [x] đó k k 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.) N Chứng minh: Giả sử mọi hộp đều chứa ít hơn ] ]vật. Khi đó tổng số đổ vật k 14 N tối đa là k.] [ đồ vật k Điều này mâu thuẩn với giả thiết là có N đổ vât cần xếp. Vây ta có điều phải chứng minh Ví dụ: 1. Chứng minh rằng 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. Có năm loại học bổng khác nhau.
Hỏi rằng phải có ít nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là 6 người cùng nhạn học bổng như nhau. Gọi N là số sinh viên, khi đó ] N/5 [ = 6 khi và chỉ khi 5 < N/5 < =6 hay 25 < N < =30. Vậy số N cần tìm là 26. Số mã vùng cần thiết nhỏ nhất phải là bao nhiêu để đảm bảo 25 triệu máy điện thoại trong n- ớc có số điện thoại khác nhau, mỗi số có 9 chữ số (giả sử số điện thoại có dạng 0XX - 8XXXXX với X nhạn các giá trị từ 0 đến 9).000 số điện thoại khác nhau có dạng 0XX - 8XXXXX.
Vì vạy theo nguyên lý Dirichlet tổng quát, trong số 25 triệu máy điện thoại ít nhất có ] 25.000 [ = 3 có cùng một số. Để đảm bảo mỗi máy có một số cần có ít nhất 3 mã vùng. Một số ứng dụng của nguyên lý Dirichlet. Lưu ý: Trong nhiều ứng dụng của nguyên lý Dirichlet, khái niệm đổ vật và hộp cần phải được lựa chọn một cách khôn khéo.
Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số người quen trong số những người dự họp là như nhau. Số người quen của mỗi ng-ời trong phòng họp nhạn các giá trị từ 0 đến n- 1. Rõ ràng trong phòng không thể đổng thời có người có số người quen là 0 (tức là không quen ai) và có người có số người quen là n - 1 (tức là quen tất cả). Vì vạy theo số lượng người quen, ta chỉ có thể phân n người ra thành n -1 nhóm.
Vậy theo nguyên lý Dirichlet tổn tai một nhóm có ít nhất 2 người, tức là luôn tìm được 15 ít nhất 2 người có số người quen là như nhau. Trong một tháng gổm 30 ngày, một đội bóng chuyền thi đấu mỗi ngày ít nhất 1 trân nh- ng chơi không quá 45 trân. Chứng minh rằng tìm được một giai đoạn gổm một số ngày liên tục nào đó trong tháng sao cho trong giai đoạn đó đội chơi đúng 14 trận. Gọi aj là số trạn mà đội đã chơi từ ngày đầu tháng đến hết ngày j., a30+14 nằm giữa 1 và 59.
Do đó theo nguyên lý Dirichlet có ít nhất 2 trong 60 số này bằng nhau. Vì vạy tổn tại i và j sao cho ai = aj + 14 (j < i). Điều này có nghĩa là từ ngày j + 1 đêh hết ngày i đội đã chơi đúng 14 trân. Chứng tỏ rằng trong n + 1 số nguyên dương không vượt quá 2n, tổn tại ít nhất một số chia hết cho số khác.
Ta viết mỗi số nguyên a1, a2,., an+1 d-ới dạng aj = 2kj qj trong đó kj là số nguyên không âm còn qj là số dương lẻ nhỏ hơn 2n. Vì chỉ có n số nguyên dương lẻ nhỏ hơn 2n nên theo nguyên lý Dirichlet tổn tại i và j sao cho qi = qj = q. Khi đó ai= 2ki q và aj = 2k q. Vì vây, nếu ki < kj thì aj chia hết cho ai còn trong trường hợp ngược lại ta có ai chia hết cho aj.
Ví dụ cuối cùng trình bày cách áp dụng nguyên lý Dirichlet vào lý thuyết tổ hợp mà vẫn quen gọi là lý thuyết Ramsey, tên của nhà toán học ng- ời Anh. Nói chung, lý thuyết Ramsey giải quyết những bài toán phân chia các tâp con của một tâp các phần tử. Giả sử trong một nhóm 6 người mỗi cặp hai hoặc là bạn hoặc là thù. Chứng tỏ rằng trong nhóm có ba người là bạn lẫn nhau hoặc có ba người là kẻ thù lẫn nhau.
Gọi A là một trong 6 người. Trong số 5 người của nhóm hoặc là có ít nhất ba người là bạn của A hoặc có ít nhất ba người là kẻ thù của A, điều này suy ra từ nguyên lý Dirichlet tổng quát, vì ] 5/2 [ = 3. Trong trường hợp đầu ta gọi B, C, D là bạn của A. nếu trong ba người này có hai người là bạn thì họ cùng với A lâp thành một bộ ba người bạn lẫn nhau, ngược lại, tức là nếu trong ba người B, C, D không có ai là bạn ai cả thì chứng tỏ họ là bộ ba người thù lẫn nhau.
Tương tự có thể chứng minh trong trường hợp có ít nhất ba ng- ời là kẻ thù của A. 16 Bài tập thực hành: Bài 1: Trong tổng số 2504 sinh viên của một khoa công nghệ thông tin, có 1876 theo học môn ngôn ngữ lâp trình Pascal, 999 học môn ngôn ngữ Fortran và 345 học ngôn ngữ C. Ngoài ra còn biết 876 sinh viên học cả Pascal và Fortran, 232 học cả Fortran và C, 290 học cả Pascal và C. Nếu 189 sinh viên học cả 3 môn Pascal, Fortran và C thì trong trường hợp đó có bao nhiêu sinh viên không học môn nào trong 3 môn ngôn ngữ lâp trình kể trên.
Bài 2: Một cuộc họp gổm 12 người tham dự để bàn về 3 vấn đề. Có 8 người phát biểu về vấn đề I, 5 người phát biểu về vấn đề II và 7 người phát biểu về vấn đề III. Ngoài ra, có đúng 1 người không phát biểu vấn đề nào. Hỏi nhiều lắm là có bao nhiêu người phát biểu cả 3 vấn đề.
Bài 3: Trong tạp số nguyên {1, 2, , 100} có bao nhiêu số không chia hết cho bất kỳ số nào trong các số 3, 4, 7 Bài 4: Có bao nhiêu a. Xâu có đô dài 4 và không chứa chữ x Bài 5: Có bao nhiêu xâu gồm 3 chữ số thập phân? a. Không chứa cùng môt chữ số 3 lần b. Bắt đầu bằng chữ số lẻ c.
Có đúng hai chữ số 4 Bài 6: Có bao nhiêu xâu nhị phân đô dài 10 hoặc bắt đầu bằng 000 hoặc kết thúc bằng 111 Bài 7: Có bao nhiêu số nguyên không lớn hơn 1000 chia hết cho 7 hoặc 11 Bài 8: Trong số các số nguyên d- ơng có 3 chữ số, có bao nhiêu số: a. Chia hết cho 7 e. Không chia hết cho 4 b. Chia hết cho 3 hoặc 4 c.
Có 3 chữ số đôimôt khác nhau g. Không chia hết cho 3hoặc cho 4 d. Chia hết cho 3và cho 4 h. Chia hết cho 3 nh-ngkhông chia hết cho 4 Bài 9: Có bao nhiêu xâu nhị phân đô dài 7 chứa môt số chẵn các bit 0 17 Bài 10: Tìm hệ số của x5y8 trong khai triển (x + y)13 Bài 11: Có bao nhiêu xâu khác nhau có thể lập được từ các chữ cái trong từ ACCESS, yêu cầu phải dùng tất cả các chữ? Bài 12: Môt giáo sư cất bô sưu tập gồm 40 số báo toán học vào 4 chiếc ngăn tủ, mỗi ngăn đựng 10 số.
Có bao nhiêu cách có thể cất các tờ báo vào các ngăn nếu: 1) Mỗi ngăn được đánh số sao cho có thể phân biệt được; 2) Các ngăn là giống hệt nhau? Bài 13: Chỉ ra rằng có ít nhất 4 người trong số 25 triệu người có cùng tên họ viết tắt bằng 3 chữ cái sinh cùng ngày trong năm (không nhất thiết trong cùng một năm). Bài 14: Một tay đô vạt tham gia thi đấu giành chức vô địch trong 75 giờ. Mỗi giờ anh ta có ít nhất một trân đấu, nh- ng toàn bộ anh ta có không quá 125 trân. Chứng tỏ rằng có những giờ liên tiếp anh ta đã đấu đúng 24 trân.
Bài 15: Cho n là số nguyên dương bất kỳ. Chứng minh rằng luôn lấy ra được từ n số đã cho một số số hạng thích hợp sao cho tổng của chúng chia hết cho n.