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

Fall 2006Toỏn rời rạcPhần thứ nhấtLí THUYẾT TỔ HỢPCombinatorial Theory Fall 2008Fall 2006Toỏ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ợpFall 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ạ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.Fall 2006Toỏ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.”Fall 2006Toỏ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 CbFall 2006Toỏ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.Fall 2006Toỏ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 trỡnh bày tốt sẽ rất 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-1Fall 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