›
›

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

pdf 108 trang huongle 6811
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lí thuyết tổ hợp - Chương 2: Bài toán tồn tại", để 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:

  • pdfbai_giang_li_thuyet_to_hop_chuong_2_bai_toan_ton_tai.pdf

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

  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ế 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ạ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ế 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), • 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, 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 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* 13 1 40  f (40) 40/ 2 20 n lÇn gäi hµm f f (20) 20/ 2 10 • là bằng 1. f (10) 10/ 2 5 f (5) 3* 5 1 16 f (16) 16/ 2 8 f (8) 8/ 2 4 f (4) 4/ 2 2 f (2) 2/1 1 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, nhưng 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 P B AB, AC, BC có màu xanh thỡ nó cùng với hai trong số ba cung PA, C PB, PC tạo thành một tam giác E D xanh. 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.  Nhưng 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