Bài giảng Lý thuyết tổ hợp - Chương 2: Bài toán tồn tại (Tiếp theo)

Toán rời rạcPhần thứ nhấtLÝ THUYẾT TỔ HỢPCombinatorial Theory Fall 2009Toán rời rạcNội dungChương 0. Mở đầuChương 1. Bài toán đếmChương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợpChương 4. Bài toán tối ưu tổ hợpToán rời rạcChương 2. BÀI TOÁN TỒN TẠIGiới thiệu bài toánCác kỹ thuật chứng minh cơ bảnNguyên lý DirichletĐịnh lý RamseyToán rời rạc1. Giới thiệu bài toánTrong ch­¬ng tr­íc, ta ®· tËp trung chó ý vµo viÖc ®Õm sè c¸c cÊu h×nh tæ hîp. Trong nh÷ng bµi to¸n ®ã sù tån t¹i cña c¸c cÊu h×nh lµ hiÓn nhiªn vµ c«ng viÖc chÝnh lµ ®Õm sè phÇn tö tho¶ m·n tÝnh chÊt ®Æt ra. Tuy nhiªn, trong rÊt nhiÒu bµi to¸n tæ hîp, viÖc chØ ra sù tån t¹i cña mét cÊu h×nh tho¶ m·n c¸c tÝnh chÊt cho tr­íc lµ hÕt søc khã kh¨n. Ch¼ng h¹n, khi mét kú thñ cÇn ph¶i tÝnh to¸n c¸c n­íc ®i cña m×nh ®Ó gi¶i ®¸p xem liÖu cã kh¶ n¨ng th¾ng hay kh«ng, Mét ng­êi gi¶i mËt m· cÇn t×m kiÕm ch×a kho¸ gi¶i cho mét bøc mËt m· mµ anh ta kh«ng biÕt liÖu ®©y cã ®óng lµ bøc ®iÖn thËt ®­îc m· ho¸ cña ®èi ph­¬ng hay kh«ng, hay chØ lµ bøc mËt m· gi¶ cña ®èi ph­¬ng tung ra nh»m ®¶m b¶o an toµn cho bøc ®iÖn thËt ...Trong tæ hîp xuÊt hiÖn mét vÊn ®Ò thø hai rÊt quan träng lµ: xÐt sù tån t¹i cña c¸c cÊu h×nh tæ hîp víi c¸c tÝnh chÊt cho tr­íc - bµi to¸n tån t¹i tæ hîp.NhiÒu bµi to¸n tån t¹i tæ hîp ®· tõng th¸ch thøc trÝ tuÖ nh©n lo¹i vµ ®· lµ ®éng lùc thóc ®Èy sù ph¸t triÓn cña tæ hîp nãi riªng vµ to¸n häc nãi chung.Toán rời rạcBài toán về 36 sĩ quanBµi to¸n nµy ®­îc Euler ®Ò nghÞ, néi dung cña nã nh­ sau: “Cã mét lÇn ng­êi ta triÖu tËp tõ 6 trung ®oµn mçi trung ®oµn 6 sÜ quan thuéc 6 cÊp bËc kh¸c nhau: thiÕu óy, trung uý, th­îng uý, ®¹i uý, thiÕu t¸, trung t¸ vÒ tham gia duyÖt binh ë s­ ®oµn bé. Hái r»ng cã thÓ xÕp 36 sÜ quan nµy thµnh mét ®éi ngò h×nh vu«ng sao cho trong mçi mét hµng ngang còng nh­ mçi mét hµng däc ®Òu cã ®¹i diÖn cña c¶ 6 trung ®oµn vµ cña c¶ 6 cÊp bËc sÜ quan.”Toán rời rạcBài toán về 36 sĩ quanSử dụng: A, B, C, D, E, F ®Ó chØ c¸c phiªn hiÖu trung ®oµn, a, b, c, d, e, f ®Ó chØ c¸c cÊp bËc sÜ quan. Bµi to¸n nµy cã thÓ tæng qu¸t ho¸ nÕu thay con sè 6 bëi n. Trong tr­êng hîp n = 4, mét lêi gi¶i cña bµi to¸n 16 sü quan lµ Ab Dd Ba Cc Bc Ca Ad Db Cd Bb Dc Aa Da Ac Cb BdMét lêi gi¶i trong tr­êng hîp n = 5 lµ Aa Bb Cc Dd Ee Cd De Ea Ab Bc Eb Ac Bd Ce Da Be Ca Db Ec Ad Dc Ed Ae Ba CbToán rời rạcBài toán về 36 sĩ quanDo lêi gi¶i cña bµi to¸n cã thÓ biÓu diÔn bëi 2 h×nh vu«ng víi c¸c ch÷ c¸i la tinh hoa vµ th­êng chång c¹nh nhau nªn bµi to¸n tæng qu¸t ®Æt ra cßn ®­îc biÕt d­íi tªn gäi bµi to¸n vÒ h×nh vu«ng la tinh trùc giao. Euler ®· mÊt rÊt nhiÒu c«ng søc ®Ó t×m lêi gi¶i cho bµi to¸n 36 sÜ quan thÕ nh­ng «ng ®· kh«ng thµnh c«ng. Tõ ®ã «ng ®· ®Ò ra mét gi¶ thuyÕt tæng qu¸t lµ: Kh«ng tån t¹i h×nh vu«ng la tinh trùc giao cÊp n = 4k + 2. Tarri, n¨m 1901 chøng minh gi¶ thuyÕt ®óng víi n = 6, b»ng c¸ch duyÖt tÊt c¶ mäi kh¶ n¨ng xÕp.N¨m 1960 ba nhµ to¸n häc Mü lµ Boce, Parker, Srikanda chØ ra ®­îc mét lêi gi¶i víi n = 10 vµ sau ®ã chØ ra ph­¬ng ph¸p x©y dùng h×nh vu«ng la tinh trùc giao cho mäi n = 4k+2, víi k > 1.Toán rời rạcBài toán về 36 sĩ quanT­ëng chõng bµi to¸n ®Æt ra chØ cã ý nghÜa thuÇn tuý cña mét bµi to¸n ®è hãc bóa thö trÝ tuÖ con ng­êi. ThÕ nh­ng gÇn ®©y ng­êi ta ®· ph¸t hiÖn nh÷ng øng dông quan träng cña vÊn ®Ò trªn vµo:Quy ho¹ch thùc nghiÖm (Experimental Design), S¾p xÕp c¸c lÞch thi ®Êu trong c¸c gi¶i cê quèc tÕ, H×nh häc x¹ ¶nh (Projective Geometry), ...Fall 2006Toán rời rạcBµi to¸n 4 mµuCã nh÷ng bµi to¸n mµ néi dung cña nã cã thÓ gi¶i thÝch cho bÊt kú ai, tuy nhiªn lêi gi¶i cña nã th× ai còng cã thÓ thö t×m, nh­ng mµ khã cã thÓ t×m ®­îc. Ngoµi ®Þnh lý Fermat th× bµi to¸n 4 mµu lµ mét bµi to¸n nh­ vËy. Bµi to¸n cã thÓ ph¸t biÓu trùc quan nh­ sau: Chøng minh r»ng mäi b¶n ®å trªn mÆt ph¼ng ®Òu cã thÓ t« b»ng 4 mµu sao cho kh«ng cã hai n­íc l¸ng giÒng nµo l¹i bÞ t« bëi cïng mét mµu. Chó ý r»ng, ta xem nh­ mçi n­íc lµ mét vïng liªn th«ng vµ hai n­íc ®­îc gäi lµ l¸ng giÒng nÕu chóng cã chung biªn giíi lµ mét ®­êng liªn tôc.Fall 2006Toán rời rạcBài toán 4 màuCon sè 4 kh«ng ph¶i lµ ngÉu nhiªn. Ng­êi ta ®· chøng minh ®­îc r»ng mäi b¶n ®å ®Òu ®­îc t« víi sè mÇu lín h¬n 4, cßn víi sè mÇu Ýt h¬n 4 th× kh«ng t« ®­îc. Ch¼ng h¹n b¶n ®å gåm 4 n­íc ë h×nh d­íi kh«ng thÓ t« ®­îc víi sè mÇu Ýt h¬n 4.BCDAFall 2006Toán rời rạcBài toán 4 màuVấn đề này được đề cập trong bức thư của Augustus De Morgan gửi W. R. Hamilton năm 1852 (De Morgan biết sự kiện này từ Frederick Guthrie, còn Guthrie từ người anh trai của mình...)Trong 110 năm rất nhiều chứng minh được công bố nhưng đều có lỗi.Năm 1976, Appel và Haken đã đưa ra chứng minh bằng máy tính điện tử! K. Appel and W. Hankin, "Every planar map is 4-colorable," Bulletin of the AMS, Volume 82 (1976), 711-712. Fall 2006Toán rời rạcBài toán 4 màuTrong ngôn ngữ toán học, bài toán 4 màu được phát biểu dưới dạng bài toán tô màu đồ thị phẳng.Việc giải quyết Bài toán 4 màu đóng góp phần quan trọng vào việc phát triển lý thuyết đồ thị.Bài toán tô màu đồ thị có nhiều ứng dụng thực tế quan trọng.Fall 2006Toán rời rạcHình lục giác thần bíN¨m 1910 Clifford Adams ®Ò ra bµi to¸n h×nh lôc gi¸c thÇn bÝ sau: trªn 19 « lôc gi¸c (xem h×nh vÏ ë d­íi) h·y ®iÒn vµo c¸c sè tõ 1 ®Õn 19 sao cho tæng theo 6 h­íng cña lôc gi¸c lµ b»ng nhau (vµ ®Òu b»ng 38).Fall 2006Toán rời rạcHình lục giác thần bíSau 47 n¨m trêi kiªn nhÉn cuèi cïng «ng ta ®· t×m ®­îc lêi gi¶i. Sau ®ã v× s¬ ý ®¸nh mÊt b¶n th¶o «ng ta ®· tèn thªm 5 n¨m ®Ó kh«i phôc l¹i. N¨m 1962 Adams ®· c«ng bè lêi gi¶i ®ã.ThËt kh«ng thÓ ngê lµ ®ã lµ lêi gi¶i duy nhÊt (nÕu kh«ng tÝnh ®Õn c¸c lêi gi¶i sai kh¸c nhau bëi phÐp biÕn h×nh ®¬n gi¶n).Fall 2006Toán rời rạcGiả thuyết 3x + 1Giả thuyết 3x+1 (conjecture)Giả sử hàm f(x) trả lại x/2 nếu x là số chẵn và 3x+1 nếu x là số lẻ. Với mọi số nguyên dương x, luôn tồn tại n sao cholà bằng 1.Fall 2006Toán rời rạcGiả thuyết 3x + 1Giả thuyết 3x+1: Đoạn chương trình sau đây luôn kết thúc với mọi số nguyên dương x:repeat if x mod 2 = 0 then x:= x div 2 else x:= 3*x +1until x=1; Paul Erdös commented concerning the intractability of the 3x+1 problem: ``Mathematics is not yet ready for such problems.'' Đã chứng minh với mọi x  5.6*1013Fall 2006Toán rời rạcMột số vấn đề mở Open problemsGoldbach’s ConjectureMỗi số nguyên n >2 đều là tổng của 2 số nguyên tốĐã chỉ ra là đúng với mọi n đến tận 4*1014Nhiều người cho rằng giả thuyết là đúngCặp số nguyên tố sinh đôi (Twin prime conjecture)Có vô số cặp số nguyên tố sinh đôi (nghĩa là chỉ chênh lệch nhau 2)Cặp sinh đôi lớn nhất: 318,032,361*2107,001±1Số này có 32,220 chữ số!Cũng được cho rằng là đúngKhông tồn tại số hoàn hảo lẻ (Odd perfect number)Nếu bạn giải quyết được một trong những vấn đề này ....Fall 2006Toán rời rạcẢO GIÁCFall 2006Toán rời rạcFractalsFall 2006Toán rời rạcA bit of humor: Computer terminologyFall 2006Toán rời rạcChương 2. BÀI TOÁN TỒN TẠIGiới thiệu bài toánCác kỹ thuật chứng minh cơ bảnNguyên lý DirichletHệ đại diện phân biệtĐịnh lý RamseyFall 2006Toán rời rạc2. Các kỹ thuật chứng minh2.0. Mở đầu2.1. Chứng minh trực tiếp (Direct Proof) 2.2. Chứng minh bằng phản chứng (Proof by Contradiction) 2.3. Chứng minh bằng phản đề (Proof by Contrapositive) 2.4. Chứng minh bằng qui nạp toán học (Proof by Mathematical Induction) Fall 2006Toán rời rạc2.0. Mở đầuChứng minh là trái tim của toán học. Trong suốt quá trình học từ thuở nhỏ đến trưởng thành bạn đã và sẽ còn phải làm việc với chứng minh – phải đọc, hiểu và thực hiện chứng minh. Có bí quyết gì không? Có phép màu gì giúp được không? Câu trả lời là: Không có bí quyết, không có phép màu. Vấn đề quan trọng là cần biết tư duy, hiểu biết một số sự kiện và nắm vững một số kỹ thuật cơ bảnFall 2006Toán rời rạcCấu trúc của chứng minhCấu trúc cơ bản của chứng minh rất đơn giản: Nó là dãy các mệnh đề, mỗi một trong số chúng sẽ hoặc là giả thiết, hoặc là kết luận được suy trực tiếp từ giả thiết hoặc suy ra từ các kết quả đã chứng minh trước đó. Ngoài ra có thể có những giải thích – cần cho người đọc và không có ảnh hưởng đến cấu trúc của chứng minh. Một chứng minh cần được trình bày sao cho dễ theo dõi: Mỗi bước trong chứng minh đều rõ ràng hoặc ít ra là được giải thích rõ ràng, Người đọc được dẫn dắt đến kết luận mà không gặp những vướng mắc do những tình tiết không rõ ràng gây ra.Fall 2006Toán rời rạcVí dụ: Chứng minh là số vô tỷ Trước hết ta nhắc lại khái niệm số vô tỷ và một kết quả của số học:Một số thực được gọi là số hữu tỷ nếu nó có thể biểu diễn dưới dạng p/q, với p và q là các số nguyên. Một số thực không là số hữu tỷ được gọi là số vô tỷ.Định lý cơ bản của số học: Mọi số nguyên dương đều có thể biểu diễn một cách duy nhất dưới dạng tích của các số nguyên tố mà ta sẽ gọi là phân tích ra thừa số nguyên tố (sẽ viết tắt là PTNT) của số đó.Fall 2006Toán rời rạcVí dụ: Chứng minh là số vô tỷ Ký hiệu s = 21/2. Theo định nghĩa, s thoả mãn phương trình s2 = 2.Nếu s là số hữu tỷ, thì ta có thể viết s = p/q trong đó p và q là hai số nguyên. Bằng cách chia cho ước chung nếu cần, ta có thể giả thiết là p và q không có ước chung nào ngoài 1. Thay biểu diễn này vào phương trình đầu tiên, sau khi biến đổi một chút, ta thu được phương trình p2 = 2 q2 .Fall 2006Toán rời rạcVí dụ: Chứng minh là số vô tỷ Thế nhưng, theo định lý cơ bản của số học, 2 là thừa số trong PTNT của p2 . Do 2 là số nguyên tố, nên nó cũng là thừa số trong PTNT của p. Từ đó suy ra, 22 cũng xuất hiện trong PTNT của p2, và vì thế trong cả PTNT của 2q2. Bằng cách chia hai vế cho 2, ta suy ra 2 là thừa số trong PTNT của q2. Tương tự như trên (như đối với p2) ta có thể kết luận 2 là thừa số nguyên tố của q. Như vậy, ta thấy p và q có chung thừa số 2. Điều đó là mâu thuẫn với giả thiết p và q không có ước chung nào ngoài 1. Khẳng định được chứng minh. Fall 2006Toán rời rạc2.1. Chứng minh trực tiếp(Direct proofs)Chúng ta bắt đầu bằng ví dụ chứng minh tính bắc cầu của tính chất chia hết.Định lý. Nếu a chia hết b và b chia hết c thì a chia hết c. Proof. Theo giả thiết, và định nghĩa tính chia hết, ta suy ra tồn tại các số nguyên k1 và k2 sao cho b = a k1 và c = b k2.Suy ra c = b k2 = a k1 k2.Đặt k = k1 k2. Ta có k là số nguyên và c = a k, do đó theo định nghĩa về tính chia hết, a chia hết c. Fall 2006Toán rời rạc2.1. Chứng minh trực tiếp(Direct proofs)Nếu P, thì Q (If P, Then Q)Phần lớn các định lý (các bài tập hay bài kiểm tra) mà bạn cần chứng minh hoặc ẩn hoặc hiện có dạng “Nếu P, Thì Q". Trong ví dụ vừa nêu, "P" là “Nếu a chia hết b và b chia hết c " còn "Q" là "a chia hết c". Đây là dạng phát biểu chuẩn của rất nhiều định lý. Chứng minh trực tiếp có thể hình dung như là một dãy các suy diễn bắt đầu từ “P” và kết thúc bởi "Q". P  ...  QPhần lớn các chứng minh là chứng minh trực tiếp. Khi phải chứng minh, bạn nên thử bắt đầu từ chứng minh trực tiếp, ngoại trừ tình huống bạn có lý do xác đáng để không làm như vậy. Fall 2006Toán rời rạcVí dụVí dụ 1. Mỗi số nguyên lẻ đều là hiệu của hai số chính phương. CM. Giả sử 2a+1 là số nguyên lẻ, khi đó 2a+1 = (a+1)2 - a2.Ví dụ 2. Số 100...01 (với 3n-1 số không, trong đó n là số nguyên dương) là hợp số. CM. Ta có thể viết 100...01 = 103n + 1, trong đó n là số nguyên dương. Sử dụng hằng đẳng thức a3 + b3 = (a+b)(a2 - a b + b2) với a = 10n và b = 1, ta thu được (10n)3 + 1 = (10n + 1)(102n - 10n + 1).Do (10n + 1) > 1 và (102n - 10n + 1) > 1 khi n là nguyên dương nên ta có đpcm. Fall 2006Toán rời rạc2.2. Chứng minh bằng phản chứngTrong chứng minh bằng phản chứng ta sử dụng các giả thiết và mệnh đề phủ định kết quả cần chứng minh và từ đó cố gắng suy ra các điều phi lý hoặc các mâu thuẫn với giả thiết ban đầu. Nghĩa là nếu phải chứng minh “Nếu P, Thì Q", ta giả thiết rằng P và Not Q là đúng. Mâu thuẫn thu được có thể là một kết luận trái với một trong những giả thiết đã cho hoặc điều phi lý, chẳng hạn như 1 = 0.Chứng minh căn bậc hai của 2 là số vô tỷ trong ví dụ mở đầu là một ví dụ chứng minh như vậy.Fall 2006Toán rời rạc2.2. Chứng minh bằng phản chứngVÝ dô 1. Cho 7 ®o¹n th¼ng cã ®é dµi lín h¬n 10 vµ nhá h¬n 100. Chøng minh r»ng lu«n t×m ®­îc 3 ®o¹n ®Ó cã thÓ ghÐp thµnh mét tam gi¸c.Gi¶i: Chó ý r»ng, cÇn vµ ®ñ ®Ó 3 ®o¹n cã thÓ ghÐp thµnh mét tam gi¸c lµ tæng ®é dµi cña 2 ®o¹n nhá ph¶i lín h¬n ®é dµi cña ®o¹n lín. S¾p c¸c ®o¹n ®· cho theo thø tù t¨ng dÇn cña ®é dµi, ta cã: 10 20. Tõ a2 > 10 vµ a3 > 20, ta nhËn ®­îc a4 > 30, ..., cø nh­ vËy ta nhËn ®­îc a5 > 50, a6 > 80 vµ a7 > 130. BÊt ®¼ng thøc cuèi cïng m©u thuÉn víi gi¶ thiÕt c¸c ®é dµi nhá h¬n 100 vµ ®iÒu ®ã chøng minh kÕt luËn cña VÝ dô 1.Fall 2006Toán rời rạc2.2. Chứng minh bằng phản chứngVÝ dô 2. C¸c ®Ønh cña mét thËp gi¸c ®Òu ®­îc ®¸nh sè bëi c¸c sè nguyªn 0, 1, ... , 9 mét c¸ch tuú ý. Chøng minh r»ng lu«n t×m ®­îc ba ®Ønh liªn tiÕp cã tæng c¸c sè lµ lín h¬n 13.Gi¶i: Gäi x1, x2, . . ., x10 lµ c¸c sè g¸n cho c¸c ®Ønh cña 1, 2,..., 10 cña thËp gi¸c. Gi¶ sö ng­îc l¹i lµ kh«ng t×m ®­îc ba ®Ønh nµo tho¶ m·n kh¼ng ®Þnh cña vÝ dô. Khi ®ã ta cã x1 + x2 + x3  13, x2 + x3 + x4  13, . . . . . x9 + x10 + x1  13, x10 + x1 + x2  13, Fall 2006Toán rời rạc2.2. Chứng minh bằng phản chứngCéng vÕ víi vÕ tÊt c¶ c¸c bÊt ®¼ng thøc trªn ta suy ra 3(x1 + x2 + . . . + x10)  130.MÆt kh¸c do 3(x1 + x2 + . . . + x10) = 3 (0 + 1 + 2 + . . . + 9) = 135, suy ra 135 = 3(x1 + x2 + . . . + x10)  130.M©u thuÉn thu ®­îc ®· chøng tá kh¼ng ®Þnh trong vÝ dô lµ ®óng.Fall 2006Toán rời rạc2.2. Chứng minh bằng phản chứngVí dụ 3. Chứng minh rằng không thể nối 31 máy vi tính thành một mạng sao cho mỗi máy được nối với đúng 5 máy khác.Giải: Giả sử ngược lại là tìm được cách nối 31 máy sao cho mỗi máy được nối với đúng 5 máy khác. Khi đó số lượng kênh nối là 531/2 = 75,5 ?! Điều phi lý thu được đã chứng minh khẳng định trong ví dụ là đúng.Fall 2006Toán rời rạc2.3. Chứng minh bằng phản đề (Proof by Contrapositive) Chứng minh bằng phản đề sử dụng sự tương đương của hai mệnh đề "P kéo theo Q" và “Phủ định Q kéo theo phủ định P". (P  Q) (¬Q  ¬P).Ví dụ, khẳng định “Nếu đó là xe của tôi thì nó có màu mận" là tương đương với “Nếu xe đó không có màu mận thì nó không phải của tôi". Do đó, để chứng minh “Nếu P, Thì Q" bằng phương pháp phản đề, ta chứng minh “Nếu phủ định Q thì có phủ định P” ("If Not Q, Then Not P“). Fall 2006Toán rời rạc2.3. Chứng minh bằng phản đề Ví dụ 1. Nếu x và y là hai số nguyên sao cho x+y là số chẵn, thì x và y có cùng tính chẵn lẻ. CM. Mệnh đề phản đề của khẳng định đã cho là “Nếu x và y là hai số nguyên không cùng chẵn lẻ, thì tổng của chúng là số lẻ." Vì thế ta giả sử rằng x và y không cùng chẵn lẻ. Không giảm tổng quát, giả sử rằng x là chẵn còn y là lẻ. Khi đó ta tìm được các số nguyên k và m sao cho x = 2k và y = 2m+1. Bây giờ ta tính tổng x+y = 2k + 2m + 1 = 2(k+m) + 1, mà rõ ràng là số lẻ. Từ đó suy ra khẳng định cuả ví dụ là đúng. Fall 2006Toán rời rạc2.3. Chứng minh bằng phản đề Ví dụ 2. Nếu n là số nguyên dương sao cho n mod 4 là bằng 2 hoặc 3, thế thì n không là số chính phương. CM. Ta sẽ chứng minh mệnh đề phản đề: “Nếu n là số chính phương thì n mod 4 phải bằng 0 hoặc 1." Giả sử n = k2. Có 4 tình huống có thể xảy ra. Nếu k mod 4 = 0, thì k = 4q, với q nguyên nào đó. Khi đó, n = k2 = 16 q2 = 4(4 q2) , suy ra n mod 4 = 0. Nếu k mod 4 = 1, thì k = 4q + 1, với q nguyên nào đó. Khi đó, n = k2 = 16 q2 + 8 q + 1= 4(4 q2 + 2 q) + 1, suy ra n mod 4 = 1. Nếu k mod 4 = 2, thì k = 4q + 2, với q nguyên nào đó. Khi đó, n = k2 = 16 q2 + 16 q + 4 = 4(4 q2 + 4 q + 1), suy ra n mod 4 = 0. Nếu k mod 4 = 3, thì k = 4q + 3, với q nguyên nào đó. Khi đó, n = k2 = 16 q2 + 24 q + 9 = 4(4 q2 + 6 q + 2) + 1, suy ra n mod 4 = 1. Fall 2006Toán rời rạc2.3. Chứng minh bằng phản đề Chứng minh bằng phản đề khác chứng minh phản chứng ở chỗ nào? Ta xét việc áp dụng chúng vào việc chứng minh "If P, Then Q". Chứng minh bằng phản chứng: Giả sử có P và Not Q ta cố gắng chỉ ra điều mâu thuẫn. Chứng minh bằng phản đề: Giả sử có Not Q và ta phải chứng minh not P. Phương pháp chứng minh bằng phản đề có ưu điểm là bạn có mục đích rõ ràng là: Chứng minh Not P. Trong phương pháp phản chứng, bạn phải cố gắng chỉ ra điều mâu thuẫn mà ngay từ đầu bạn chưa thể xác định được đó là điều gì. Fall 2006Toán rời rạc2.4. Chứng minh bằng qui nạp toán họcĐây là kỹ thuật chứng minh rất hữu ích khi ta phải chứng minh mệnh đề P(n) là đúng với mọi số tự nhiên n.Tương tự như nguyên lý “hiệu ứng domino”.Sơ đồ chứng minh: P(0)n0 (P(n)P(n+1))Kết luận: n0 P(n)“Nguyên lý qui nạp toán học thứ nhất”“The First Principleof Mathematical Induction”Fall 2006Toán rời rạcThe “Domino Effect” 0123456Bước #1: Domino #0 đổ.Bước #2: Với mọi nN,nếu domino #n đổ, thì domino #n+1 cũng đổ.Kết luận: Tất cả các quân bài domino đều đổ!Chú ý: điều này xảy rangay cả khi có vô hạnquân bài domino!Fall 2006Toán rời rạcTính đúng đắn của qui nạp(The Well-Ordering Property)Tính đúng đắn của chứng minh qui nạp là hệ quả của “well-ordering property”:Mỗi tập con khác rỗng các số nguyên không âm đều có phần tử nhỏ nhất”.   S  N : m  S : n  S : m  nTừ đó suy ra tập {n|P(n)} (nếu khác rỗng) có phần tử nhỏ nhất m, thế nhưng điều đó là trái với điều đã chứng minh: Ta có P(m−1) là đúng, suy ra P((m−1)+1) là đúng?!Fall 2006Toán rời rạcSơ đồ chứng minh bằng qui nạp yếuGiả sử ta cần chứng minh P(n) là đúng n  m .Cơ sở qui nạp: Chứng minh P(m) là đúng.Giả thiết qui nạp: Giả sử P(n) là đúngBước chuyển qui nạp: Chứng minh P(n+1) là đúng.Kết luận: Theo nguyên lý qui nạp ta có P(n) là đúng n  m.Fall 2006Toán rời rạcQui nạp mạnh(Second Principle of Induction – Strong Induction)Sơ đồ chứng minh:P(0)n0: ( 0  k  n P(k))  P(n+1)Kết luận n0: P(n)Sự khác biệt với sơ đồ qui nạp “yếu” ở chỗ:Bước chuyển qui nạp sử dụng giả thiết mạnh hơn: P(k) là đúng cho mọi số nhỏ hơn k 1) bởi các quân bài hình chữ T (T-omino).Fall 2006Toán rời rạcCơ sở qui nạp: Bảng 22 x 22 Fall 2006Toán rời rạcCơ sở qui nạp: Bảng 22 x 22Fall 2006Toán rời rạcCơ sở qui nạp: Bảng 22 x 22Fall 2006Toán rời rạcCơ sở qui nạp: Bảng 22 x 22Fall 2006Toán rời rạcBước chuyển qui nạp Giả sử ta có thể phủ kín bàn cờ kích thước 2n  2n. Ta phải chứng minh có thể phủ kín bàn cờ kích thước 2n+1  2n+1. Thực vậy, chia bàn cờ 2n+1  2n+1 ra thành 4 phần, mỗi phần kích thước 2n  2n. Theo giả thiết qui nạp mỗi phần này đều có thể phủ kín bởi các quân bài chữ T. Đặt chúng vào bàn cờ 2n+1  2n+1 ta thu được cách phủ cần tìm.Fall 2006Toán rời rạcVÍ DỤ 2Trên mặt phẳng vẽ n đường thẳng ở vị trí tổng quát. Hỏi ít nhất phải sử dụng bao nhiêu màu để tô các phần bị chia bởi các đường thẳng này sao cho không có hai phần có chung cạnh nào bị tô bởi cùng một màu?P(n): Luôn có thể tô các phần được chia bởi n đường thẳng vẽ ở vị trí tổng quát bởi 2 màu xanh và đỏ sao cho không có hai phần có chung cạnh nào bị tô bởi cùng một màu.Fall 2006Toán rời rạcVí dụ 2Cơ sở qui nạp: Khi n = 1, mặt phẳng được chia làm hai phần, một phần sẽ tô màu xanh, phần còn lại tô màu đỏ.Giả sử khẳng định đúng với n-1, ta chứng minh khẳng định đúng với n.Thực vậy, trước hết ta vẽ n-1 đường thẳng. Theo giả thiết qui nạp có thể tô màu các phần sinh ra bởi hai màu thoả mãn điều kiện đặt ra. Bây giờ ta vẽ đường thẳng thứ n. Đường thẳng này chia mặt phẳng ra làm hai phần, gọi là phần A và B. Các phần của mặt phẳng được chia bởi n đường thẳng ở bên nửa mặt phẳng B sẽ giữ nguyên màu đã tô trước đó. Trái lại, các phần trong nửa mặt phẳng A mỗi phần sẽ được tô màu đảo ngược xanh thành đỏ và đỏ thành xanh. Rõ ràng:Hai phần có chung cạnh ở cùng một nửa mặt phẳng A hoặc B là không có chung màu.Hai phần có chung cạnh trên đường thẳng thứ n rõ ràng cũng không bị tô cùng màu (do màu bên nửa A bị đảo ngược).Vậy P(n) đúng. Theo qui nạp khẳng định đúng với mọi n.Fall 2006Toán rời rạcVí dụ 2XĐĐĐĐĐXXXFall 2006Toán rời rạcVí dụ 2XĐĐĐĐĐXXXABĐXĐXXĐXXFall 2006Toán rời rạcVí dụ 3Kết thúc một giải vô địch bóng chuyền gồm n đội tham gia, trong đó các đội thi đấu vòng tròn một lượt người ta mời các đội trưởng của các đội ra đứng thành một hàng ngang để chụp ảnh. P(n): Luôn có thể xếp n đội trưởng ra thành một hàng ngang sao cho ngoại trừ hai người đứng ở hai mép, mỗi người trong hàng luôn đứng cạnh một đội trưởng của đội thắng đội mình và một đội trưởng của đội thua đội mình trong giải.Fall 2006Toán rời rạcVí dụ 3Chứng minh. Ta chứng minh bằng qui nạp toán học.Cơ sở qui nạp: Rõ ràng P(1) là đúng.Giả sử P(n-1) là đúng, ta chứng minh P(n) là đúng.Trước hết, ta xếp n-1 đội trưởng của các đội 1, 2,..., n-1. Theo giả thiết qui nạp, luôn có thể xếp họ ra thành hàng ngang thoả mãn điều kiện đầu bài. Không giảm tổng quát ta có thể giả thiết hàng đó là: 1 2  ...  n-1.Fall 2006Toán rời rạcVí dụ 3Bây giờ ta sẽ tìm chỗ cho đội trưởng của đội n. Có 3 tình huống:Nếu đội n thắng đội 1, thì hàng cần tìm là: n  1 2  ...  n-1.Nếu đội n thua đội n-1, thì hàng cần tìm là: 1 2  ...  n-1  n .Nếu đội n thua đội 1 và thắng đội n-1. Gọi k là chỉ số nhỏ nhất sao cho đội n thắng đội k. Rõ ràng tồn tại k như vậy.Hàng cần thu được từ hàng gồm n-1 đội đã xếp bằng cách chèn đội trưởng đội n vào vị trí giữa đội trưởng của đội k-1 và đội k.Fall 2006Toán rời rạcVí dụ 3 1 2  ... k-1 k  k+1 ... n-1 n Hàng cần tìm: 1 ... k-1 n k  k+1 ... n-1ParadoxĐịnh lý: Tất cả các con ngựa có cùng một màu. Proof: Qui nạp theo nGiả thiết qui nạp:P(n) ::= n con ngựa bất kỳ luôn có cùng một màuCơ sở qui nạp (n=1): Chỉ có 1 con tất nhiên là chỉ có một màu!Bước chuyển qui nạp Giả sử n con ngựa bất kỳ luôn có cùng màu.Ta cần chứng minh n+1 con ngựa bất kỳ luôn có cùng màu.Paradoxn+1Tập thứ nhất gồm n con ngựa cùng màuTập thứ hai gồm n con ngựa cùng màuBước chuyển qui nạp Giả sử n con ngựa bất kỳ luôn có cùng màu.Ta cần chứng minh n+1 con ngựa bất kỳ luôn có cùng màu.ParadoxSuy ra n+1 con ngựa có cùng một màu!Bước chuyển qui nạp Giả sử n con ngựa bất kỳ luôn có cùng màu.Ta cần chứng minh n+1 con ngựa bất kỳ luôn có cùng màu.ParadoxLỗi ở đâu?Chứng minh P(n) → P(n+1) là false nếu n = 1, bởi vì hai nhóm ngựalà không giao nhau.Tập thứ nhất gồm n=1 con ngựan =1Tập thứ hai gồm n=1 con ngựaParadoxFall 2006Toán rời rạcA bit of humorFall 2006Toán rời rạcChương 2. BÀI TOÁN TỒN TẠIGiới thiệu bài toánCác kỹ thuật chứng minh cơ bảnNguyên lý DirichletĐịnh lý RamseyFall 2006Toán rời rạc3. Nguyên lý Dirichlet3.1. Phát biểu nguyên lý3.2. Các ví dụ ứng dụngFall 2006Toán rời rạc3.1. Phát biểu nguyên lý (Pigeonhole Principle)Nếu xếp nhiều hơn n đối tượng vào n cái hộp thì bao giờ cũng tìm được ít nhất một cái hộp chứa ít ra là hai đối tượng.Fall 2006Toán rời rạc3.1. Phát biểu nguyên lý (Pigeonhole Principle)Chứng minh. Việc chứng minh nguyên lý trên chỉ là một lập luận phản chứng đơn giản. Giả sử ngược lại là không tìm được cái hộp nào chứa không ít hơn 2 đối tượng. Điều đó có nghĩa là mỗi cái hộp chứa không quá một đối tượng. Từ đó suy ra tổng số đối tượng xếp trong n cái hộp là không vượt quá n, trái với giả thiết là có nhiều hơn n đối tượng được xếp trong chúng.Fall 2006Toán rời rạc3.1. Phát biểu nguyên lý (Pigeonhole Principle)Lập luận trên đã được nhà toán học người Đức là Dirichlet vận dụng thành công vào việc giải quyết rất nhiều bài toán tồn tại tổ hợp. Trong lập luận của Dirichlet, các đối tượng được xét là các quả táo còn các cái hộp được thay bởi các cái giỏ: “Nếu đem bỏ nhiều hơn n quả táo vào n cái giỏ thì bao giờ cũng tìm được ít nhất một cái giỏ chứa ít ra là 2 quả táo”. Fall 2006Toán rời rạc3.1. Phát biểu nguyên lý (Pigeonhole Principle)Trong tài liệu tiếng Anh lập luận đó lại được trình bày trong ngôn ngữ của các con chim bồ câu: “Nếu đem nhốt nhiều hơn n con chim bồ câu vào n cái lồng thì bao giờ cũng tìm được ít nhất 1 cái lồng chứa ít ra là 2 con chim bồ câu”. Vì thế nguyên lý còn có tên gọi là “Nguyên lý về các lồng chim bồ câu”.Trong ngôn ngữ của lý thuyết tập hợp, nguyên lý có thể phát biểu như sau: “Nếu tập X gồm nhiều hơn n phần tử được phân hoạch thành n tập con, thì bao giờ cũng tìm được một tập con trong phân hoạch đó có lực lượng ít ra là 2”Fall 2006Toán rời rạcVí dụVÝ dô 1. Trong sè 367 ng­êi bao giê còng t×m ®­îc hai ng­êi cã ngµy sinh nhËt gièng nhau bëi v× chØ cã tÊt c¶ 366 ngµy sinh nhËt kh¸c nhau.VÝ dô 2. Trong kú thi häc sinh giái ®iÓm bµi thi ®­îc ®¸nh gi¸ bëi mét sè nguyªn trong kho¶ng tõ 0 ®Õn 100. Hái r»ng Ýt nhÊt ph¶i cã bao nhiªu häc sinh dù thi ®Ó cho ch¾c ch¾n t×m ®­îc hai häc sinh cã kÕt qu¶ thi nh­ nhau? Gi¶i. Theo nguyªn lý Dirichlet, sè häc sinh cÇn t×m lµ 102, v× ta cã 101 kÕt qu¶ ®iÓm thi kh¸c nhau.Fall 2006Toán rời rạcVí dụVÝ dô 3. Trong sè nh÷ng ng­êi cã mÆt trªn tr¸i ®Êt lu«n t×m ®­îc hai ng­êi cã hµm r¨ng gièng nhau.Giải: Tất cả chỉ có 232 = 4 294 967 296 hµm r¨ng kh¸c nhau mµ sè ng­êi trªn hµnh tinh chóng ta hiÖn nay ®· v­ît qu¸ 5 tû.Fall 2006Toán rời rạcNguyên lý Dirichlet tổng quátGeneralized Pigeonhole PrincipleKhi số lượng quả táo bỏ vào k cái giỏ vượt quá số lượng cái giỏ nhiều lần thì rõ ràng khẳng định trong nguyên lý về sự tồn tại cái giỏ chứa ít ra là 2 quả táo là quá ít. Trong trường hợp như vậy ta sử dụng nguyên lý Dirichlet tổng quát sau đây:“Nếu đem bỏ n quả táo vào k cái giỏ thì bao giờ cũng tìm được ít nhất một cái giỏ chứa ít ra là n/k quả táo”.Ở đây ký hiệu  gọi là phần nguyên già của số thực  - theo định nghĩa là số nguyên nhỏ nhất còn lớn hơn hoặc bằng .Fall 2006Toán rời rạcNguyên lý Dirichlet tổng quátGeneralized Pigeonhole PrincipleChứng minh nguyên lý tổng quát: Giả sử khẳng định của nguyên lý là không đúng. Khi đó mỗi cái giỏ chứa không quá n/k - 1 quả táo. Từ đó suy ra tổng số quả táo bỏ trong k cái giỏ không vượt quá k(n/k - 1) at. Fall 2006Toán rời rạcVí dụ 5Nếu as it. Mâu thuẫn với giả thiết is= it.Tương tự như vậy, nếu as > at, ta có thể chỉ ra ds phải lớn hơn dt, và cũng đi đến mâu thuẫn.Định lý được chứng minh.Fall 2006Toán rời rạcFall 2006Toán rời rạcChương 2. BÀI TOÁN TỒN TẠIGiới thiệu bài toánCác kỹ thuật chứng minh cơ bảnNguyên lý DirichletĐịnh lý RamseyFall 2006Toán rời rạcVí dụ mở đầuTrong mÆt ph¼ng cho 6 ®iÓm ®­îc nèi víi nhau tõng ®«i mét bëi c¸c cung mµu xanh hoÆc mµu ®á. Chøng minh r»ng lu«n t×m ®­îc 3 ®iÓm sao cho c¸c cung nèi chóng cã cïng mét mµu (ta sÏ nãi lµ chóng t¹o thµnh tam gi¸c xanh hoÆc ®á).Gi¶i: Chän ®iÓm P nµo ®ã. Tõ nã cã 5 cung nèi víi 5 ®iÓm cßn l¹i. Theo nguyªn lý Dirichlet, cã 3 trong sè 5 cung ®ã ph¶i cã cïng mét mµu, ch¼ng h¹n lµ mµu xanh. Gi¶ sö ®ã lµ c¸c cung PA, PB, PC. NÕu nh­ mét trong sè 3 cung AB, AC, BC cã mµu xanh th× nã cïng víi hai trong sè ba cung PA, PB, PC t¹o thµnh mét tam gi¸c xanh. NÕu ng­îc l¹i th× tam gi¸c ABC lµ mét tam gi¸c ®á.Fall 2006Toán rời rạcVí dụ mở đầuPABCEDNÕu nh­ mét trong sè 3 cung AB, AC, BC cã mµu xanh thì nã cïng víi hai trong sè ba cung PA, PB, PC t¹o thµnh mét tam gi¸c xanh.Fall 2006Toán rời rạcVí dụ mở đầuPABCEDNếu cả 3 cung AB, AC, BC có màu đỏ thì chúng tạo thành một tam giác đỏ.Fall 2006Toán rời rạcPhân tích ví dụMét c¸ch ph¸t biÓu kh¸c cña kÕt qu¶ võa chøng minh lµ: Trong sè 6 ng­êi t¹i mét bµn tiÖc lu«n t×m ®­îc hoÆc ba ng­êi ®«i mét quen nhau hoÆc ba ng­êi ®«i mét kh«ng quen nhau. Có thể thấy rằng nếu thay con số 6 bởi n > 6 thì khẳng định trong ví dụ vẫn đúng. Nhưng nếu thay con số 6 bởi 5 thì khẳng định trong ví dụ không còn đúng nữa như chỉ ra trong hình vẽ sau đâyFall 2006Toán rời rạcPhân tích ví dụNhư vậy có thể thấy 6 là giá trị n nhỏ nhất để khẳng định trong ví dụ là đúng. Chóng ta cã thÓ ®Æt ra c¸c c©u hái t­¬ng tù nh­: Hái Ýt nhÊt ph¶i cã bao nhiªu ng­êi ®Ó ch¾c ch¾n t×m ®­îc hoÆc 4 ng­êi ®«i mét quen nhau hoÆc 4 ng­êi ®«i mét kh«ng quen nhau? Hái Ýt nhÊt ph¶i cã bao nhiªu ng­êi ®Ó ch¾c ch¾n t×m ®­îc hoÆc 5 ng­êi ®«i mét quen nhau hoÆc 5 ng­êi ®«i mét kh«ng quen nhau? Con sè nhá nhÊt nh¾c ®Õn trong c¸c c©u hái trªn ®­îc gäi lµ c¸c sè Ramsey, mang tªn nhµ to¸n häc ng­êi Anh ®· chøng minh ®­îc ®Þnh lý næi tiÕng trong lý thuyÕt tËp hîp lµ sù tæng qu¸t ho¸ nguyªn lý Dirichlet. Fall 2006Toán rời rạcCác số Ramsey§Ó cã thÓ ph¸t biÓu nh÷ng kÕt qu¶ tæng qu¸t h¬n chóng ta cÇn ®Õn mét sè kh¸i niÖm.§Þnh nghÜa 1. Gäi Kn lµ bé gåm hai tËp V, E, trong ®ã V lµ tËp gåm n ®iÓm cßn E lµ tËp c¸c ®o¹n nèi gi÷a tÊt c¶ c¸c cÆp ®iÓm trong V. Ta sÏ ký hiÖu Kn = (V, E). C¸c phÇn tö cña V ®­îc gäi lµ c¸c ®Ønh, vµ V lµ tËp ®Ønh cña Kn. Mçi ®o¹n nèi hai ®Ønh u, v  V sÏ ®­îc gäi lµ mét c¹nh cña Kn vµ ký hiÖu lµ (u, v), vµ tËp E ®­îc gäi lµ tËp c¹nh cña Kn.Fall 2006Toán rời rạcCác số RamseyTa cã thÓ ph¸t biÓu l¹i kÕt qu¶ trong vÝ dô më ®Çu nh­ sau: “Gi¶ sö mçi c¹nh cña K6 ®­îc t« bëi mét trong hai mµu xanh hoÆc ®á. Khi ®ã K6 lu«n chøa hoÆc K3 víi tÊt c¶ c¸c c¹nh ®­îc t« mµu xanh (gäi t¾t lµ K3 xanh) hoÆc K3 víi tÊt c¶ c¸c c¹nh ®­îc t« mµu ®á (gäi t¾t lµ K3 ®á). Chóng ta sÏ nãi r»ng sè 6 cã tÝnh chÊt (3,3)-Ramsey. §Þnh nghÜa 2. Gi¶ sö i vµ j lµ hai sè nguyªn sao cho i  2, j  2. Sè nguyªn d­¬ng m cã tÝnh chÊt (i,j)-Ramsey nÕu Km víi mçi c¹nh ®­îc t« bëi mét trong hai mµu xanh, ®á lu«n chøa hoÆc lµ Ki ®á hoÆc lµ Kj xanh.Fall 2006Toán rời rạcCác số RamseyTõ ph©n tÝch ë trªn ta thÊy 6 cã tÝnh chÊt (3,3)-Ramsey, vµ mäi sè n m còng cã tÝnh chÊt nµy;NÕu m kh«ng cã tÝnh chÊt (i,j)-Ramsey, th× mäi sè n < m còng kh«ng cã tÝnh chÊt nµy;NÕu i1  i2 th× R(i1,j)  R(i2,j).Fall 2006Toán rời rạcCác số RamseyViÖc x¸c ®Þnh sè Ramsey R(i,j) ®ßi hái chóng ta ph¶i t×m sè nguyªn d­¬ng nhá nhÊt cã tÝnh chÊt (i,j)-Ramsey. LiÖu sè nµy cã tån t¹i víi mäi i  2, j  2 hay kh«ng? §Þnh lý Ramsey cho ta kh¼ng ®Þnh vÒ sù tån t¹i cña c¸c sè nµy.§Þnh lý Ramsey. NÕu i  2, j  2 lµ c¸c sè nguyªn d­¬ng th× lu«n t×m ®­îc sè nguyªn d­¬ng víi tÝnh chÊt (i,j)-Ramsey (tõ ®ã suy ra sè R(i,j) lµ tån t¹i).Fall 2006Toán rời rạcCác số RamseyCác số R(i,j) vừa trình bày ở trên chỉ là một trong số nhiều dòng số Ramsey đã được nghiên cứu.Việc xác định R(i,j) với những giá trị i, j cụ thể luôn là các bài toán tổ hợp không tầm thường. Hiện nay người ta mới biết giá trị của R(i, j) với rất ít giá trị của (i,j).Fall 2006Toán rời rạcAsk questions!Fall 2006Toán rời rạcFall 2006Toán rời rạc