›
›

Bài giảng Toán rời rạc - Phần 1 - Chương 2: Bài toán tồn tại (Phần 2)

ppt 108 trang haiha333 08/01/2022 4430
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần 1 - Chương 2: Bài toán tồn tại (Phần 2)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_toan_roi_rac_phan_1_chuong_2_bai_toan_ton_tai_phan.ppt

Nội dung text: Bài giảng Toán rời rạc - Phần 1 - Chương 2: Bài toán tồn tại (Phần 2)

  1. Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toán rời rạc 1
  2. Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2
  3. Chương 2. BÀI TOÁN TỒN TẠI 1. Giới thiệu bài toán 2. Các kỹ thuật chứng minh cơ bản 3. Nguyên lý Dirichlet 4. Định lý Ramsey Toán rời rạc 3
  4. 1. Giới thiệu bài toán ⚫ Trong 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ạc 4
  5. Bài toán về 36 sĩ quan ⚫ Bµ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ạc 5
  6. Bài toán về 36 sĩ quan ⚫ Sử 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 Bd ⚫ Mé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 Cb Toán rời rạc 6
  7. Bài toán về 36 sĩ quan ⚫ Do 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Õ nhng «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ạc 7
  8. Bài toán về 36 sĩ quan ⚫ Të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Õ nhng 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), • Toán rời rạc 8
  9. Bµi to¸n 4 mµu ⚫ Cã 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, nhng 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 2006 Toán rời rạc 9
  10. Bài toán 4 màu ⚫ Con 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. A B C D Fall 2006 Toán rời rạc 10
  11. Bài toán 4 màu ⚫ Vấ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 2006 Toán rời rạc 11
  12. Bài toán 4 màu ⚫ Trong 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 2006 Toán rời rạc 12
  13. Hì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 2006 Toán rời rạc 13
  14. Hì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 2006 Toán rời rạc 14
  15. Giả thuyết 3x + 1 ⚫ Giả 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 cho fn ( x )= f ( f ( ( f ( x )) )) f (13)3*13140=+= f (40)40== / 220 nf lÇn gäi hµm f (20)20== / 210 • là bằng 1. f (10)10== / 25 f (5)3*5116=+= f (16)16== / 28 f (8)8== / 24 f (4)4== / 22 f (2)2== /11 Fall 2006 Toán rời rạc 15
  16. Giả thuyết 3x + 1 ⚫ Giả 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 +1 until 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*1013 Fall 2006 Toán rời rạc 16
  17. Một số vấn đề mở Open problems ⚫ Goldbach’s Conjecture • Mỗ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*1014 • Nhiều người cho rằng giả thuyết là đúng ⚫ Cặ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±1 • Số này có 32,220 chữ số! • Cũng được cho rằng là đúng ⚫ Khô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 2006 Toán rời rạc 17
  18. ẢO GIÁC Fall 2006 Toán rời rạc 18
  19. Fractals Fall 2006 Toán rời rạc 19
  20. A bit of humor: Computer terminology Fall 2006 Toán rời rạc 20
  21. Chương 2. BÀI TOÁN TỒN TẠI 1. Giới thiệu bài toán 2. Các kỹ thuật chứng minh cơ bản 3. Nguyên lý Dirichlet 4. Hệ đại diện phân biệt 5. Định lý Ramsey Fall 2006 Toán rời rạc 21
  22. 2. Các kỹ thuật chứng minh 2.0. Mở đầu 2.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 2006 Toán rời rạc 22
  23. 2.0. Mở đầu ⚫ Chứ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ản Fall 2006 Toán rời rạc 23
  24. Cấu trúc của chứng minh ⚫ Cấ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 2006 Toán rời rạc 24
  25. Ví dụ: Chứng minh 2 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 2006 Toán rời rạc 25
  26. Ví dụ: Chứng minh 2 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 2006 Toán rời rạc 26
  27. Ví dụ: Chứng minh 2 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 2006 Toán rời rạc 27
  28. 2.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 2006 Toán rời rạc 28
  29. 2.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 Q ⚫ Phầ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 2006 Toán rời rạc 29
  30. Ví 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 2006 Toán rời rạc 30
  31. 2.2. Chứng minh bằng phản chứng ⚫ Trong 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 2006 Toán rời rạc 31
  32. 2.2. Chứng minh bằng phản chứng ⚫ VÝ 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 < a1 a2 a7 < 100. CÇn chøng minh r»ng trong d·y ®· xÕp lu«n t×m ®îc 3 ®o¹n liªn tiÕp sao cho tæng cña 2 ®o¹n ®Çu lín h¬n ®o¹n cuèi. ⚫ Gi¶ thiÕt ®iÒu nµy kh«ng x¶y ra. Fall 2006 Toán rời rạc 32
  33. 2.2. Chứng minh bằng phản chứng ⚫ Tõ gi¶ thiÕt ph¶n chøng suy ra ®ång thêi x¶y ra c¸c bÊt ®¼ng thøc: a1 + a2 a3, a2 + a3 a4, a3 + a4 a5, a4 + a5 a6, a5 + a6 a7. ⚫ Tõ gi¶ thiÕt a1, a2 cã gi¸ trÞ lín h¬n 10, ta nhËn ®îc a3 > 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 2006 Toán rời rạc 33
  34. 2.2. Chứng minh bằng phản chứng ⚫ VÝ 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 2006 Toán rời rạc 34
  35. 2.2. Chứng minh bằng phản chứng ⚫ Cé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 2006 Toán rời rạc 35
  36. 2.2. Chứng minh bằng phản chứng ⚫ Ví 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 2006 Toán rời rạc 36
  37. 2.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 2006 Toán rời rạc 37
  38. 2.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 2006 Toán rời rạc 38
  39. 2.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 2006 Toán rời rạc 39
  40. 2.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 2006 Toán rời rạc 40
  41. 2.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) “Nguyên lý qui nạp toán học thứ nhất” n 0 (P(n)→P(n+1)) “The First Principle Kết luận: n 0 P(n) of Mathematical Induction” Fall 2006 Toán rời rạc 41
  42. The “Domino Effect” ⚫ Bước #1: Domino #0 đổ. ⚫ Bước #2: Với mọi n N, nếu domino #n đổ, thì domino #n+1 cũng đổ. 6 5 ⚫ Kết luận: Tất cả các quân bài domino đều đổ! 4 3 Chú ý: điều này xảy ra 2 ngay cả khi 1 có vô hạn 0 quân bài domino! Fall 2006 Toán rời rạc 42
  43. Tí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 n ⚫ Từ đó 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 2006 Toán rời rạc 43
  44. Sơ đồ chứng minh bằng qui nạp yếu Giả 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à đúng ⚫ Bướ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 2006 Toán rời rạc 44
  45. Qui nạp mạnh (Second Principle of Induction – Strong Induction) ⚫ Sơ đồ chứng minh: P là đúng trong mọi tình huống trước ⚫ 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<n+1, chứ không phải chỉ riêng với k=n như trong nguyên lý qui nạp thứ nhất. Fall 2006 Toán rời rạc 45
  46. Sơ đồ chứng minh bằng qui nạp mạnh Giả sử ta cần chứng minh P(n) là đúng n 0. ⚫ Cơ sở qui nạp: Chứng minh P(0) là đúng. ⚫ Giả thiết qui nạp: Giả sử P(k) là đúng  0 k n. ⚫ Bướ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 0. Fall 2006 Toán rời rạc 46
  47. Ví dụ 1 Chứng minh rằng luôn có thể phủ kín bàn cờ kích thước 2n 2n (n > 1) bởi các quân bài hình chữ T (T-omino). Fall 2006 Toán rời rạc 47
  48. Cơ sở qui nạp: Bảng 22 x 22 Fall 2006 Toán rời rạc 48
  49. Cơ sở qui nạp: Bảng 22 x 22 Fall 2006 Toán rời rạc 49
  50. Cơ sở qui nạp: Bảng 22 x 22 Fall 2006 Toán rời rạc 50
  51. Cơ sở qui nạp: Bảng 22 x 22 Fall 2006 Toán rời rạc 51
  52. Bướ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 2006 Toán rời rạc 52
  53. VÍ DỤ 2 ⚫ Trê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 2006 Toán rời rạc 53
  54. Ví dụ 2 ⚫ Cơ 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 2006 Toán rời rạc 54
  55. Ví dụ 2 Đ X X X Đ Đ Đ X Đ Fall 2006 Toán rời rạc 55
  56. Ví dụ 2 A Đ B X X Đ Đ X X Đ X X Đ X Đ X Đ Đ X Fall 2006 Toán rời rạc 56
  57. Ví dụ 3 ⚫ Kế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 2006 Toán rời rạc 57
  58. Ví dụ 3 ⚫ Chứ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 2006 Toán rời rạc 58
  59. Ví dụ 3 ⚫ Bâ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 2006 Toán rời rạc 59
  60. Ví 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-1 Fall 2006 Toán rời rạc 60
  61. Paradox Định lý: Tất cả các con ngựa có cùng một màu. Proof: Qui nạp theo n Giả thiết qui nạp: P(n) ::= n con ngựa bất kỳ luôn có cùng một màu Cơ sở qui nạp (n=1): Chỉ có 1 con tất nhiên là chỉ có một màu! 61
  62. Paradox 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. n+1 62
  63. Paradox 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. Tập thứ hai gồm n con ngựa cùng màu Tập thứ nhất gồm n con ngựa cùng màu 63
  64. Paradox 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. Suy ra n+1 con ngựa có cùng một màu! 64
  65. Paradox Lỗi ở đâu? n =1 Chứng minh P(n) → P(n+1) là false nếu n = 1, bởi vì hai nhóm ngựa là không giao nhau. Tập thứ hai gồm n=1 con ngựa Tập thứ nhất gồm n=1 con ngựa 65
  66. A bit of humor Fall 2006 Toán rời rạc 66
  67. Chương 2. BÀI TOÁN TỒN TẠI 1. Giới thiệu bài toán 2. Các kỹ thuật chứng minh cơ bản 3. Nguyên lý Dirichlet 4. Định lý Ramsey Fall 2006 Toán rời rạc 67
  68. 3. Nguyên lý Dirichlet 3.1. Phát biểu nguyên lý 3.2. Các ví dụ ứng dụng Fall 2006 Toán rời rạc 68
  69. 3.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 2006 Toán rời rạc 69
  70. 3.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 2006 Toán rời rạc 70
  71. 3.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 2006 Toán rời rạc 71
  72. 3.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 2006 Toán rời rạc 72
  73. Ví 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 2006 Toán rời rạc 73
  74. Ví 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 2006 Toán rời rạc 74
  75. Nguyên lý Dirichlet tổng quát Generalized Pigeonhole Principle ⚫ Khi 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 2006 Toán rời rạc 75
  76. Nguyên lý Dirichlet tổng quát Generalized Pigeonhole Principle ⚫ Chứ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) < k((n/k+1) - 1)) = n. Mâu thuẫn thu được đã chứng minh nguyên lý. Fall 2006 Toán rời rạc 76
  77. Ví dụ ⚫ VÝ dô 4. Trong 100 ngêi cã Ýt nhÊt 9 ngêi sinh cïng mét th¸ng. ⚫ Gi¶i: XÕp nh÷ng ngêi cïng sinh mét th¸ng vµo mét nhãm. Cã 12 th¸ng tÊt c¶. VËy theo nguyªn lý Dirichlet, tån t¹i Ýt nhÊt mét nhãm cã kh«ng Ýt h¬n 100/12 = 9 ngêi. ⚫ VÝ dô 5. Cã n¨m lo¹i häc bæng kh¸c nhau. Hái r»ng ph¶i cã Ýt nhÊt bao nhiªu sinh viªn ®Ó ch¾c ch¾n r»ng cã Ýt ra lµ s¸u ngêi cïng nhËn häc bæng nh nhau? ⚫ Gi¶i: Sè sinh viªn Ýt nhÊt cÇn cã ®Ó ®¶m b¶o ch¾c ch¾n cã 6 sinh viªn cïng nhËn häc bæng nh nhau lµ sè nguyªn nhá nhÊt n sao cho n/5 = 6. Sè nguyªn nhá nhÊt ®ã lµ n = 5 5+1 = 26. VËy 26 lµ sè lîng sinh viªn nhá nhÊt ®¶m b¶o ch¾c ch¾n lµ cã s¸u sinh viªn cïng hëng mét lo¹i häc bæng. Fall 2006 Toán rời rạc 77
  78. Ví dụ ⚫ VÝ dô 6. Hái Ýt nhÊt ph¶i cã bao nhiªu ngêi cã mÆt trªn tr¸i ®Êt ®Ó lu«n t×m ®îc ba 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. Ta cÇn t×m sè n nhá nhÊt ®Ó n/232 = 3. Tõ ®ã sè ngêi cÇn t×m lµ 2 232 + 1 = 8 589 934 593. Fall 2006 Toán rời rạc 78
  79. 3.2. Các ví dụ ứng dụng ⚫ Trong các ví dụ ứng dụng phức tạp hơn của nguyên lý Dirichlet, cái giỏ và quả táo cần phải được lựa chọn khôn khéo hơn rất nhiều. ⚫ Trong phần này ta sẽ xét một số ví dụ như vậy. Fall 2006 Toán rời rạc 79
  80. Ví dụ 1 ⚫ Ví dụ 1. Trong mét phßng häp bao giê còng t×m ®îc hai ngêi cã sè ngêi quen trong sè nh÷ng ngêi dù häp lµ b»ng nhau. ⚫ Gi¶i: Gäi sè ngêi dù häp lµ n, khi ®ã sè ngêi quen cña mét ngêi nµo ®ã trong phßng häp chØ cã thÓ nhËn c¸c gi¸ trÞ tõ 0 ®Õn n-1. Râ rµng trong phßng kh«ng thÓ ®ång thêi cã ngêi cã sè ngêi quen lµ 0 (tøc lµ kh«ng quen ai c¶) vµ cã ngêi cã sè ngêi quen lµ n-1 (tøc lµ quen tÊt c¶). V× vËy, theo sè lîng ngêi quen ta chØ cã thÓ ph©n n ngêi ra thµnh n-1 nhãm. Theo nguyªn lý Dirichlet suy ra cã Ýt nhÊt mét nhãm ph¶i cã kh«ng Ýt h¬n hai ngêi, tøc lµ lu«n t×m ®îc Ýt ra lµ hai ngêi cã sè ngêi quen lµ b»ng nhau. Fall 2006 Toán rời rạc 80
  81. Ví dụ 2 ⚫ VÝ dô 2. Trong mét th¸ng gåm 30 ngµy mét ®éi bãng chuyÒn thi ®Êu mçi ngµy Ýt nhÊt mét trËn, nhng kh«ng ch¬i qu¸ 45 trËn. H·y chøng minh r»ng ph¶i t×m ®îc mét giai ®o¹n gåm mét sè ngµy liªn tôc nµo ®ã trong th¸ng sao cho trong giai ®o¹n ®ã ®éi ch¬i ®óng 14 trËn. ⚫ Gi¶i: Gi¶ sö aj lµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø j cña ®éi. Khi ®ã a1, a2, , a30 lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ ®ång thêi 1 aj 45. Suy ra d·y a1+14, a2+14, , a30+14 còng lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ 15 aj +14 59. Fall 2006 Toán rời rạc 81
  82. Ví dụ 2 ⚫ TÊt c¶ cã 60 sè nguyªn d¬ng a1, a2, , a30, a1+14, a2+14, , a30+14, trong ®ã tÊt c¶ ®Òu nhá h¬n hoÆc b»ng 59. ⚫ V× vËy theo nguyªn lý Dirichlet, hai trong sè c¸c sè nguyªn nµy ph¶i lµ b»ng nhau. V× c¸c sè a1, , a30 lµ ®«i mét kh¸c nhau vµ c¸c sè a1+14, , a30+14 còng lµ ®«i mét kh¸c nhau, nªn suy ra ph¶i t×m ®îc chØ sè i vµ j sao cho ai = aj+14. §iÒu ®ã cã nghÜa lµ cã ®óng 14 trËn ®Êu trong giai ®o¹n tõ ngµy j+1 ®Õn ngµy i. Fall 2006 Toán rời rạc 82
  83. Ví dụ 3 ⚫ VÝ dô 3. Chøng minh r»ng, trong sè n+1 sè nguyªn d¬ng, mçi sè kh«ng lín h¬n 2n, bao giê còng t×m ®- îc hai sè sao cho sè nµy chia hÕt cho sè kia. ⚫ Gi¶i: Gäi c¸c sè ®· cho lµ a1, a2, . . . , an+1 . ⚫ ViÕt mçi mét sè aj trong n+1 sè trªn díi d¹ng: k(j) aj = 2 qj , j = 1, 2, , n+1 ⚫ trong ®ã k(j) lµ nguyªn kh«ng ©m, qj lµ sè lÎ. Fall 2006 Toán rời rạc 83
  84. Ví dụ 3 ⚫ C¸c sè q1, q2, , qn+1 lµ c¸c sè nguyªn lÎ, mçi sè kh«ng lín h¬n 2n. ⚫ Do trong ®o¹n tõ 1 ®Õn 2n chØ cã n sè lÎ, nªn tõ nguyªn lý Dirichlet suy ra lµ hai trong sè c¸c sè q1, q2, , qn+1 lµ b»ng nhau, tøc lµ t×m ®îc hai chØ sè i vµ j sao cho qi = qj = q. ⚫ Khi ®ã k(i) k(j) ai = 2 q, aj = 2 q. ⚫ Suy ra nÕu k(i) < k(j) th× aj chia hÕt cho ai, cßn nÕu k(i) k(j) th× ai chia hÕt cho aj. Fall 2006 Toán rời rạc 84
  85. Ví dụ 4 ⚫ Ví dụ 4. Trên mặt phẳng cho 5 điểm có toạ độ nguyên Mi(xi, yi), i=1, 2, , 5. Chứng minh rằng luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn đi qua một điểm có toạ độ nguyên khác nữa. ⚫ Giải. Ta sẽ chứng minh: Luôn tìm được 2 điểm sao cho điểm giữa của đoạn thẳng nối chúng có toạ độ nguyên. Theo tính chẵn lẻ của hai toạ độ, 5 điểm đã cho có thể phân vào nhiều nhất là 4 nhóm: (Chẵn, Chẵn), (Chẵn,Lẻ), (Lẻ, Chẵn), (Lẻ, Lẻ). Fall 2006 Toán rời rạc 85
  86. Ví dụ 4 ⚫ Từ đó theo nguyên lý Dirichlet phải tìm được một nhóm chứa ít ra là 2 điểm, chẳng hạn đó là Mi, Mj. Khi đó điểm giữa Gij của đoạn thẳng nối Mi và Mi có toạ độ Gij = ((xi+xj)/2, (yi+yj)/2). ⚫ Do xi và xj cũng như yi và yj có cùng tính chẵn lẻ nên các toạ độ của Gij là các số nguyên. Khẳng định của ví dụ được chứng minh. ⚫ Khẳng định của ví dụ có thể tổng quát cho không gian n- chiều: “Trong không gian n-chiều cho 2n + 1 điểm có toạ độ nguyên. Khi đó luôn tìm được 2 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn đi qua một điểm có toạ độ nguyên khác nữa”. Fall 2006 Toán rời rạc 86
  87. Ví dụ 5 Trước hết ta cần một số khái niệm. ⚫ Cho a1,a2, an là dãy số thực. ⚫ n được gọi là độ dài của dãy số đã cho. ⚫ Ta gọi dãy con của dãy đã cho là dãy có dạng ai1, ai2, , aim, trong đó 1 i1 < i2 < . . . < im n ⚫ Dãy số được gọi là tăng ngặt nếu mỗi số hạng đứng sau luôn lớn hơn số hạng đứng trước. ⚫ Dãy số được gọi là giảm ngặt nếu mỗi số hạng đứng sau luôn nhỏ hơn số hạng đứng trước • Ví dụ: Cho dãy số 1, 5, 6, 2, 3, 9. • 5, 6, 9 là dãy con tăng ngặt của dãy đã cho • 6, 3 là dãy con giảm ngặt của dãy đã cho Fall 2006 Toán rời rạc 87
  88. Ví dụ 5 ⚫ Định lý: Mỗi dãy gồm n2+1 số phân biệt (nghĩa là các phần tử là khác nhau từng đôi) luôn chứa hoặc dãy con tăng ngặt độ dài n+1 hoặc dãy con giảm ngặt độ dài n+1. ⚫ Ví dụ: Dãy 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 gồm 10 = 32+1 số hạng phải chứa hoặc dãy con tăng ngặt độ dài 4 phần tử hoặc dãy con giảm ngặt độ dài 4 phần tử. 1, 4, 6, 12 1, 4, 6, 7 11, 9, 6, 5 Fall 2006 Toán rời rạc 88
  89. Ví dụ 5 2 ⚫ Chứng minh: Giả sử a1, a2, , an2+1 là dãy gồm n +1 số phân biệt. Gán cho mỗi số hạng ak của dãy số cặp có thứ tự (ik,dk), trong đó ik là độ dài của dãy con tăng dài nhất bắt đầu từ ak còn dk là độ dài của dãy con giảm dài nhất bắt đầu từ ak. Ví dụ: 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 a2 = 11 , (2,4) a4 = 1 , (4,1) ⚫ Bây giờ giả sử không tồn tại dãy tăng cũng như dãy giảm có độ dài n+1. Khi đó ik và dk là các số nguyên dương n, với k = 1, 2, , n2+1. Fall 2006 Toán rời rạc 89
  90. Ví dụ 5 2 ⚫ Do 1 ik, dk n, nên theo qui tắc nhân có tất cả n cặp có thứ tự dạng (ik,dk) khác nhau. 2 ⚫ Do ta có tất cả n + 1 cặp (ik,dk), nên theo nguyên lý Dirichlet, hai trong số chúng là trùng nhau. ⚫ Tức là tồn tại hai số hạng as và at trong dãy đã cho với s at. Fall 2006 Toán rời rạc 90
  91. Ví dụ 5 ⚫ Nế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 2006 Toán rời rạc 91
  92. Fall 2006 Toán rời rạc 92
  93. Chương 2. BÀI TOÁN TỒN TẠI 1. Giới thiệu bài toán 2. Các kỹ thuật chứng minh cơ bản 3. Nguyên lý Dirichlet 4. Định lý Ramsey Fall 2006 Toán rời rạc 93
  94. Ví dụ mở đầu ⚫ Trong 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 2006 Toán rời rạc 94
  95. Ví dụ mở đầu A NÕu nh mét trong sè 3 cung AB, AC, P B BC cã mµu xanh thì nã cïng víi hai trong sè ba cung PA, PB, PC t¹o C thµnh mét tam gi¸c xanh. E D Fall 2006 Toán rời rạc 95
  96. Ví dụ mở đầu A Nếu cả 3 cung AB, AC, BC có P B màu đỏ thì chúng tạo thành một tam giác đỏ. C E D Fall 2006 Toán rời rạc 96
  97. Phâ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 đây Fall 2006 Toán rời rạc 97
  98. Phâ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 2006 Toán rời rạc 98
  99. Cá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 2006 Toán rời rạc 99
  100. Các số Ramsey ⚫ Ta 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 2006 Toán rời rạc 100
  101. Các số Ramsey ⚫ Tõ ph©n tÝch ë trªn ta thÊy 6 cã tÝnh chÊt (3,3)-Ramsey, vµ mäi sè n<6 ®Òu kh«ng cã tÝnh chÊt nµy. VËy 6 lµ sè nhá nhÊt cã tÝnh chÊt (3,3)- Ramsey. ⚫ §Þnh nghÜa 3. Sè Ramsey R(i,j) lµ sè nguyªn d¬ng nhá nhÊt cã tÝnh chÊt (i,j)-Ramsey. ⚫ Ch¼ng h¹n, tõ kÕt qu¶ võa tr×nh bµy ë trªn, ta cã R(3,3) = 6. ⚫ VÝ dô. T×m R(2,7) - sè nguyªn d¬ng nhá nhÊt cã tÝnh chÊt (2,7)- Ramsey. ⚫ Gi¶i: Tríc hÕt ta t×m sè nguyªn d¬ng n sao cho víi mäi c¸ch t« c¸c c¹nh cña Kn bëi hai mµu xanh, ®á lu«n t×m ®îc hoÆc K2 ®á hoÆc K7 xanh. R(2,7) lµ sè nhá nhÊt cã tÝnh chÊt nµy. Fall 2006 Toán rời rạc 101
  102. Các số Ramsey ⚫ XÐt mét c¸ch t« mµu (tuú ý) c¸c c¹nh cña K7. Râ rµng hoÆc lµ t×m ®îc Ýt nhÊt mét c¹nh cña K7 ®îc t« mµu ®á, hoÆc lµ tÊt c¶ c¸c c¹nh cña nã ®Òu ®îc t« bëi mµu xanh. NÕu cã c¹nh t« mµu ®á th× râ rµng ta cã K2 ®á. Cßn nÕu tÊt c¶ c¸c c¹nh ®Òu t« bëi mµu xanh th× ta cã K7 xanh. VËy sè 7 cã tÝnh chÊt (2,7)-Ramsey, vµ v× thÕ R(2,7) 7. ⚫ Nhng R(2,7) kh«ng thÓ nhá h¬n 7, bëi v× nÕu t« tÊt c¶ c¸c c¹nh cña K6 bëi mµu xanh ta sÏ kh«ng t×m ®îc K2 ®á vµ còng kh«ng t×m ®îc K7 xanh. ⚫ VËy R(2,7) = 7. Fall 2006 Toán rời rạc 102
  103. Các số Ramsey ⚫ C¸c tÝnh chÊt c¬ b¶n sau ®©y cña sè Ramsey R(i,j) cã thÓ chøng minh b»ng c¸c lËp luËn t¬ng tù nh trong c¸c vÝ dô ®· tr×nh bµy: • R(i,j) = R(j,i); • NÕu m cã tÝnh chÊt (i,j)-Ramsey, th× 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 2006 Toán rời rạc 103
  104. Các số Ramsey ⚫ ViÖ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 2006 Toán rời rạc 104
  105. Các số Ramsey ⚫ Cá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 2006 Toán rời rạc 105
  106. Ask questions! Fall 2006 Toán rời rạc 106
  107. Fall 2006 Toán rời rạc 107
  108. Fall 2006 Toán rời rạc 108