Toán học rời rạc (tiếng Anh: discrete mathematics) là tên chung của nhiều ngành toán học có đối tượng nghiên cứu là các tập hợp rời rạc, các ngành này được tập hợp lại từ khi xuất hiện khoa học máy tính làm thành cơ sở toán học của khoa học máy tính. Nó còn được gọi là toán học dành cho máy tính. Người ta thường kể đến trong toán học rời rạc lý thuyết tổ hợp, lý thuyết đồ thị, lý thuyết độ phức tạp, đại số Boole | làm của mỗi học sinh có thể được đặt tương ứng với một bộ X xi X2 X3 x4 x5 G I5 trong đó Xi là số thứ tự của phương án mà học sinh đã chọn để trả lời cho câu hỏi thứ i ị z 1 i 5 . Ngoài ra nếu X G I5 ta cũng sẽ chấp nhận cách viết X 24 x với x z2 X3 x4 x5 G 4. Bằng cách như vậy dễ thấy I5 được phân hoạch thành 44 256 tập con rời nhau mỗi tập con gồm bộ chỉ khác nhau ở thành phần thứ nhất tức là tập con có dạng Ax 1 x y 2 x y 3 x y 4 O c 5 1 với x z4. Vì 2000 7 X 256 nên theo nguyên lý Dirichlet có tám học sinh khác nhau Al A2 . -As mà bài làm của họ thì ứng với các bộ thuộc cùng một tập con A nào đó trong số 256 tập con nói trên . Nhưng 2000 8 1992 7 X 256 nên lại theo nguyên lý Dirichlet - tồn tại tám học sinh khác nhau trong số 1992 học sinh còn lại là B1 B2 . Bs có bài làm ứng với các bộ thuộc cùng một tập con B nào đó trong số 256 tập con nói trên . Cuối cùng vẫn có 1992 8 1984 7 X 256 nên dùng nguyên lý Dirichlet một lần nữa từ 1984 học sinh còn lại ta tiếp tục tìm ra tám học sinh khác nhau là Cl C2 . Ơ8 mà bài làm của họ ứng với các bộ trong cùng một tập con c nào đó. Từ bốn học sinh bất kỳ trong số 24 học sinh A1 A2 . A 8 Bỵ B2 . Bs Cl C2 c8 ta luôn chọn ra được hai học sinh có bài làm ứng với các bộ thuộc cùng một tập con một trong ba tập con A B hoặc C giả sử chẳng hạn đó là các học sinh Ai và Aj i j G Z 1 ỉ j 8 mà bài làm ứng với hai bộ trong A. Theo cách xây dựng các tập con 1 bài làm của hai học sinh này chỉ có thể khác nhau ở tối đa là một câu hỏi chính là câu hỏi thứ nhất nếu hai bài làm không hoàn toàn giống nhau yêu cầu của bài toán đã không được thoả mãn 2 Bây giờ ta chỉ ra một tình huống mà n 25 thoả yêu cầu của bài toán. Muốn vậy xét 5 s E 75 0 mod 4 2 i i Rõ ràng s gồm đúng 4x4x4x4xl 256 bộ hơn nữa 2 cho thấy khi X y E s thì x y j e N i j 5 Xi í yít Xj yj. 3 Lấy p là một tập con 250 phần tử của s và xét tình huống mà với mỗi X tồn tại đúng 8 học sinh có bài làm cùng ứng với bộ X tình huống này hoàn toàn có thể xảy ra vì 2000 8 X 250. Khi
