Bài giảng Nhập môn lý thuyết tổng hợp: Chương 1 - Nguyễn Anh Thi

Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp<br /> Nguyeãn Anh Thi<br /> ÑH KHTN, Tp HCM<br /> <br /> 2017<br /> <br /> Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)<br /> <br /> Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp<br /> <br /> 2017<br /> <br /> 1 / 13<br /> <br /> Chöông 1<br /> <br /> MÔÛ ÑAÀU<br /> <br /> Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)<br /> <br /> Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp<br /> <br /> 2017<br /> <br /> 2 / 13<br /> <br /> Noäi dung<br /> <br /> Noäi dung<br /> <br /> 1<br /> <br /> Nguyeân lyù chuoàng boà caâu<br /> <br /> 2<br /> <br /> Phöông phaùp quy naïp toaùn hoïc<br /> Quy naïp yeáu<br /> Quy naïp maïnh<br /> <br /> Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)<br /> <br /> Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp<br /> <br /> 2017<br /> <br /> 3 / 13<br /> <br /> Nguyeân lyù chuoàng boà caâu<br /> <br /> Nguyeân lyù chuoàng boà caâu (Derichlet) Goïi dxe laø soá nguyeân nhoû nhaát lôùn<br /> 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<br /> nhaát moät chuoàng chöùa töø dn/ke boà caâu trôû leân.<br /> Ví duï<br /> Trong nhoùm coù 367 ngöôøi thì ít nhaát coù 2 ngöôøi sinh cuøng ngaøy.<br /> Ví duï<br /> Chöùng minh raèng trong 10 soá töï nhieân baát kyø coù theå choïn 2 soá coù hieäu<br /> chia heát cho 9.<br /> HD: Khi chia 10 soá baát kyø cho 9 ta seõ coù moãi soá coù moät soá dö trong 9 soá<br /> 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<br /> hai soá coù cuøng soá dö. Hieäu cuûa hai soá ñoù seõ chia heát cho 9.<br /> <br /> Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)<br /> <br /> Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp<br /> <br /> 2017<br /> <br /> 4 / 13<br /> <br /> Nguyeân lyù chuoàng boà caâu<br /> <br /> Ví duï<br /> 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<br /> 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<br /> ñöôïc choïn hoïc laø A, B, C, D vaø E.<br /> HD: Goïi soá hoïc sinh cuûa lôùp laø N. Theo nguyeân lyù chuoàng boà caâu ta coù<br /> d N5 e = 6. Khi ñoù<br /> 25 < N ≤ 30<br /> Do ñoù ta coù theå choïn N = 26. Vaäy lôùp phaûi coù ít nhaát 26 hoïc sinh.<br /> Ví duï<br /> 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<br /> phaàn töû. Khi ñoù trong A seõ coù hai phaàn töû coù toång laø 10.<br /> HD: Ta laäp caùc chuoàng nhö sau: {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Do A coù<br /> 6 phaàn töû neân trong 6 phaàn töû ñoù seõ coù 2 phaàn töû trong 1 chuoàng. Ta<br /> ñöôïc ñieàu caàn chöùng minh.<br /> Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM)<br /> <br /> Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp<br /> <br /> 2017<br /> <br /> 5 / 13<br /> <br />