TAILIEUCHUNG - Toán rời rạc và một số vấn đề liên quan (P4)

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

• Toán học
• bài tập toán rời rạc
• toán đại học
• toán cao cấp
• thi học sinh giỏi toán
• chuyên đề bất đẳng thức
• Toán rời rạc cơ bản
• Toán rời rạc
• Ôn thi toán rời rạc
• Ôn tập toán rời rạc
• 10 bài tập toán rời rạc
• Tài liệu toán rời rạc
• Học toán rời rạc
• Bài tập về toán rời rạc
• Đề thi toán rời rạc
• Bài giảng toán rời rạc
• Giáo trình toán rời rạc
• Lý thuyết về toán rời rạc
• Câu hỏi thi Toán rời rạc
• Tài liệu thi Toán rời rạc
• Bài thi Toán rời rạc
• Nội dung thi Toán rời rạc
• Bài tập thảo luận Toán học rời rạc
• Toán học rời rạc
• Bài tập Toán học rời rạc
• Ôn tập Toán học rời rạc
• Thảo luận về Toán học rời rạc
• Đề cương toán rời rạc
• Toán ánh xạ
• dạng toán rời rạc
• lý thuyết toán rời rạc
• Câu hỏi Toán rời rạc
• Hệ thức truy hồi
• Quan hệ chia để trị Toán rời rạc
• toán rời rạc trên đồ thị