Nội dung

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õ coù 2 phaàn töû trong 1 chuoàng. Ta ñöôïc ñieàu caàn chöùng minh. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 5 / 13 Nguyeân lyù chuoàng boà caâu Ví duï Chöùng minh raèng toàn taïi moät soá trong daõy caùc soá 7, 77, 777, 7777, · · · chia heát cho 2003. HD: Giaû söû khoâng toàn taïi soá naøo trong daõy treân chia heát cho 2003. Ta choïn ra 2003 soá haïn ñaàu tieân cuûa daõy treân vaø laàn löôït chia chuùng cho 2003. Do khoâng coù soá naøo chia heát cho 2003, neân caùc soá dö cuûa chuùng ít nhaát laø 1 vaø nhieàu nhaát laø 2002. Ta coù 2003 soá dö, vaø chæ coù 2002 giaù trò maø caùc soá dö coù theå nhaän ñöôïc. Theo nguyeân lyù chuoàng boà caâu thì seõ coù ít nhaát hai soá coù cuøng soá dö khi chia cho 2003. Giaû söû ta goïi hai soá ñoù naèm ôû vò trí thöù i vaø thöù j trong daõy treân, vôùi i < j ta goïi chuùng laø ai vaø aj . Khi ñoù ai = 2003ki + r, vaø aj = 2003kj + r. Suy ra aj − ai = 2003(kj − ki ) chia heát cho 2003. Deã daøng thaáy raèng aj − ai = 77 . . . 7 × 10i . Maø 10i vaø 2003 laø hai soá nguyeân toá cuøng nhau, neân suy ra 77 . . . 7 chia heát cho 2003. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 6 / 13 Nguyeân lyù chuoàng boà caâu Ví duï Chöùng minh raèng neáu coù 10 ñieåm naèm trong moät hình vuoâ √ ng ñôn vò thì coù ít nhaát hai ñieåm trong chuùng coù khoaûng caùch gaàn hôn 32 , vaø coù ít nhaát ba ñieåm trong chuùng naèm trong moät voøng troøn baùn kính 12 . HD: -Ta chia hình vuoâng ra thaønh 9 oâ vuoâng bôûi caùc ñöôøng thaúng nhö hình veõ Bôûi vì coù 10 ñieåm ñöôïc ñaët trong 9 hình vuoâng neân coù ít nhaát moät hình vuoâng chöùa 2 ñieåm. Khoaûng caùch 2 ñieåm trong√hình vuoâng nhoû thì nhoû hôn hoaëc baèng ñoä daøi ñöôøng cheùo, töùc laø baèng 32 . Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 7 / 13 Nguyeân lyù chuoàng boà caâu HD:-Ta chia hình vuoâng ra thaønh 4 phaàn nhö hình veõ Theo nguyeân lyù chuoàng boà caâu coù ít nhaát 3 ñieåm naèm trong moät tam giaùc nhoû. Ta thaáy moãi tam giaùc nhoû thì noäi tieáp trong moät ñöôøng troøn coù baùn kính laø 21 . Do ñoù ta ñöôïc ñieàu caàn chöùng minh. Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 8 / 13 Phöông phaùp quy naïp toaùn hoïc Quy naïp yeáu Phöông phaùp: Khi chöùng minh moät khaúng ñònh naøo ñoù ñuùng vôùi moïi soá nguyeân döông m baèng phöông phaùp quy naïp yeáu, ta seõ chöùng minh theo caùc böôùc sau: Chöùng minh khaúng ñònh ñuùng cho tröôøng hôïp m nhaän caùc giaù trò nhoû nhaát, (thöôøng laø 0, 1, 2 . . . ). Giaû söû khaúng ñònh ñuùng vôùi m = n. Ta chöùng minh khaúng ñònh ñuùng vôùi m = n + 1. Ví duï Vôùi moïi soá nguyeân döông m, chöùng minh raèng 12 + 22 + · · · + m2 = m(m + 1)(2m + 1) . 6 Ví duï   1 1 0 Cho A =  0 1 1 . Tính An , vôùi n laø moät soá nguyeân döông naøo ñoù. 0 0 1 Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 9 / 13 Phöông phaùp quy naïp toaùn hoïc Quy naïp yeáu Ví duï Cho a0 = 0, vaø an+1 = 3an + 1 vôùi moïi soá nguyeân döông n. Tìm moät coâng thöùc cho am . HD: Ta thöû tính nhöõng giaù trò ñaàu tieân cuûa daõy soá treân: 1, 4, 13, 40, 121, . . . . Coù theå ñoaùn ñöôïc daïng cuûa daõy soá treân laø am = (3m − 1)/2. Ta seõ chöùng minh khaúng ñònh naøy baèng quy naïp. Deã daøng thaáy raèng keát luaän ñuùng vôùi tröôøng hôïp m = 0, 1. Giaû söû khaúng ñònh ñuùng vôùi m = n. Ta chöùng minh khaúng ñònh ñuùng vôùi m = n + 1. Theo giaû thieát quy naïp ta coù an+1 = 3an + 1 = Nguyeãn Anh Thi ( ÑH KHTN, Tp HCM) 3n+1 − 1 3.(3n − 1) +1= . 2 2 Baøi giaûng Nhaäp moân Lyù Thuyeát Toå Hôïp 2017 10 / 13