Bài giảng Nhập môn lý thuyết tổng hợp Chương 1 Mở đầu trình bày nội dung của bài học về: Nguyên lý chuồng bồ câu; Phương pháp quy nạp toán học (Quy nạp yếu và quy nạp mạnh),. . | Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp Nguyeãn Anh Thi ÑH KHTN, Tp HCM 2017 Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 1 / 13 Chöông 1 MÔÛ ÑAÀU Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 2 / 13 Noäi dung Noäi dung 1 Nguyeân lyù chuoàng boà caâu 2 Phöông phaùp quy naïp toaùn hoïc Quy naïp yeáu Quy naïp maïnh Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 3 / 13 Nguyeân lyù chuoàng boà caâu Nguyeân lyù chuoàng boà caâu (Derichlet) Goïi dxe laø soá nguyeân nhoû nhaát lôùn hôn hay baèng x. Giaû söû coù n chim boà caâu trong k chuoàng. Khi ñoù toàn taïi ít nhaát moät chuoàng chöùa töø dn/ke boà caâu trôû leân. Ví duï Trong nhoùm coù 367 ngöôøi thì ít nhaát coù 2 ngöôøi sinh cuøng ngaøy. Ví duï Chöùng minh raèng trong 10 soá töï nhieân baát kyø coù theå choïn 2 soá coù hieäu chia heát cho 9. HD: Khi chia 10 soá baát kyø cho 9 ta seõ coù moãi soá coù moät soá dö trong 9 soá dö: 0, 1, 2, . . . , 8. Do ñoù theo nguyeân lyù chuoàng boà caâu phaûi toàn taïi ít nhaát hai soá coù cuøng soá dö. Hieäu cuûa hai soá ñoù seõ chia heát cho 9. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 4 / 13 Nguyeân lyù chuoàng boà caâu Ví duï Trong moät lôùp hoïc phaûi coù ít nhaát bao nhieâu hoïc sinh ñeå cho coù ít nhaát 6 hoïc sinh chôi cuøng moät nhaïc cuï, bieát raèng coù 5 loaïi nhaïc cuï caùc hoïc sinh ñöôïc choïn hoïc laø A, B, C, D vaø E. HD: Goïi soá hoïc sinh cuûa lôùp laø N. Theo nguyeân lyù chuoàng boà caâu ta coù d N5 e = 6. Khi ñoù 25 < N ≤ 30 Do ñoù ta coù theå choïn N = 26. Vaäy lôùp phaûi coù ít nhaát 26 hoïc sinh. Ví duï Cho taäp X = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Laáy A laø taäp hôïp con cuûa X goàm 6 phaàn töû. Khi ñoù trong A seõ coù hai phaàn töû coù toång laø 10. HD: Ta laäp caùc chuoàng nhö sau: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Do A coù 6 phaàn töû neân trong 6 phaàn töû ñoù seõ
