Bài giảng Toán rời rạc - Chương 2, Phần 2: Bài toán tồn tại - Nguyễn Đức Nghĩa

Toỏn rời rạc Phần thứ nhất Lí THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toỏn rời rạc 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 Chương 2. BÀI TOÁN TỒN TẠI Giới thiệu bài toỏn Cỏc kỹ thuật chứng minh cơ bản Nguyờn lý Dirichlet Định lý Ramsey Toỏn rời rạc 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 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 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 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 = 4 k + 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 = 4 k+ 2, với k > 1. Toỏn rời rạc 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), ... Fall 2006 Toỏn rời rạc 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 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. B C D A Fall 2006 Toỏn rời rạc 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 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 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 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 Giả thuyết 3x + 1 Giả thuyết 3 x +1 (conjecture) Giả sử hàm f ( x ) trả lại x /2 nếu x là số chẵn và 3 x +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 là bằng 1. Fall 2006 Toỏn rời rạc Giả thuyết 3 x + 1 Giả thuyết 3 x +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*10 13 Fall 2006 Toỏn rời rạc 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*10 14 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*2 107,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 ẢO GIÁC Fall 2006 Toỏn rời rạc Fractals Fall 2006 Toỏn rời rạc A bit of humor: Computer terminology Fall 2006 Toỏn rời rạc Chương 2. BÀI TOÁN TỒN TẠI Giới thiệu bài toỏn Cỏc kỹ thuật chứng minh cơ bản Nguyờn lý Dirichlet Hệ đại diện phõn biệt Định lý Ramsey Fall 2006 Toỏn rời rạc 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 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 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 Vớ 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 2006 Toỏn rời rạc Vớ dụ: Chứng minh là số vụ tỷ Ký hiệu s = 2 1/2 . Theo định nghĩa, s thoả món phương trỡnh s 2 = 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 p 2 = 2 q 2 . Fall 2006 Toỏn rời rạc Vớ 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 p 2 . Do 2 là số nguyờn tố, nờn nú cũng là thừa số trong PTNT của p . Từ đú suy ra, 2 2 cũng xuất hiện trong PTNT của p 2 , và vỡ thế trong cả PTNT của 2 q 2 . Bằng cỏch chia hai vế cho 2, ta suy ra 2 là thừa số trong PTNT của q 2 . Tương tự như trờn (như đối với p 2 ) 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 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 k 1 và k 2 sao cho b = a k 1 và c = b k 2 . Suy ra c = b k 2 = a k 1 k 2 . Đặt k = k 1 k 2 . 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 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 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ử 2 a +1 là số nguyờn lẻ, khi đú 2 a +1 = ( a +1) 2 - a 2 . Vớ dụ 2. Số 100...01 (với 3 n -1 số khụng, trong đú n là số nguyờn dương) là hợp số. CM. Ta cú thể viết 100...01 = 10 3 n + 1, trong đú n là số nguyờn dương. Sử dụng hằng đẳng thức a 3 + b 3 = ( a+b )( a 2 - a b + b 2 ) với a = 10 n và b = 1, ta thu được (10 n ) 3 + 1 = (10 n + 1)(10 2 n - 10 n + 1). Do (10 n + 1) > 1 và (10 2 n - 10 n + 1) > 1 khi n là nguyờn dương nờn ta cú đpcm. Fall 2006 Toỏn rời rạc 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 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 < a 1  a 2  ...  a 7 < 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 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: a 1 + a 2  a 3 , a 2 + a 3  a 4 , a 3 + a 4  a 5 , a 4 + a 5  a 6 , a 5 + a 6  a 7 . Từ giả thiết a 1 , a 2 có giá trị lớn hơn 10, ta nhận được a 3 > 20. Từ a 2 > 10 và a 3 > 20, ta nhận được a 4 > 30, ..., cứ như vậy ta nhận được a 5 > 50 , a 6 > 80 và a 7 > 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 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 x 1 , x 2 , . . ., x 10 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ó x 1 + x 2 + x 3  13 , x 2 + x 3 + x 4  13 , . . . . . x 9 + x 10 + x 1  13 , x 10 + x 1 + x 2  13 , Fall 2006 Toỏn rời rạc 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( x 1 + x 2 + . . . + x 10 )  130. Mặt khác do 3( x 1 + x 2 + . . . + x 10 ) = 3 (0 + 1 + 2 + . . . + 9) = 135, suy ra 135 = 3( x 1 + x 2 + . . . + x 10 )  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 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 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 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 = 2 k và y = 2 m +1. Bõy giờ ta tớnh tổng x+y = 2 k + 2 m + 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 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 = k 2 . 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 = k 2 = 16 q 2 = 4(4 q 2 ) , 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 = k 2 = 16 q 2 + 8 q + 1= 4(4 q 2 + 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 = k 2 = 16 q 2 + 16 q + 4 = 4(4 q 2 + 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 = k 2 = 16 q 2 + 24 q + 9 = 4(4 q 2 + 6 q + 2) + 1, suy ra n mod 4 = 1. Fall 2006 Toỏn rời rạc 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 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)  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 2006 Toỏn rời rạc The “Domino Effect” 0 1 2 3 4 5 6 Bướ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 2006 Toỏn rời rạc 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 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 Qui 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<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. P là đỳng trong mọi tỡnh huống trước Fall 2006 Toỏn rời rạc 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 Vớ dụ 1 Chứng minh rằng luụn cú thể phủ kớn bàn cờ kớch thước 2 n  2 n (n > 1) bởi cỏc quõn bài hỡnh chữ T (T-omino). Fall 2006 Toỏn rời rạc Cơ sở qui nạp: Bảng 2 2 x 2 2 Fall 2006 Toỏn rời rạc Cơ sở qui nạp: Bảng 2 2 x 2 2 Fall 2006 Toỏn rời rạc Cơ sở qui nạp: Bảng 2 2 x 2 2 Fall 2006 Toỏn rời rạc Cơ sở qui nạp: Bảng 2 2 x 2 2 Fall 2006 Toỏn rời rạc Bước chuyển qui nạp Giả sử ta cú thể phủ kớn bàn cờ kớch thước 2 n  2 n . Ta phải chứng minh cú thể phủ kớn bàn cờ kớch thước 2 n +1  2 n +1 . Thực vậy, chia bàn cờ 2 n +1  2 n +1 ra thành 4 phần, mỗi phần kớch thước 2 n  2 n . 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ờ 2 n +1  2 n +1 ta thu được cỏch phủ cần tỡm. Fall 2006 Toỏn rời rạc 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 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 Vớ dụ 2 X Đ Đ Đ Đ Đ X X X Fall 2006 Toỏn rời rạc Vớ dụ 2 X Đ Đ Đ Đ Đ X X X A B Đ X Đ X X Đ X X Fall 2006 Toỏn rời rạc 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 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 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 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 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! 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. Paradox n +1 Tập thứ nhất gồm n con ngựa cựng màu Tập thứ hai gồm n con ngựa cựng màu Bước chuyển qui nạp Giả sử n con ngựa bất kỳ luụn cú cựng màu. Ta cần chứng minh n+ 1 con ngựa bất kỳ luụn cú cựng màu. Paradox Suy ra n +1 con ngựa cú cựng một màu! Bước chuyển qui nạp Giả sử n con ngựa bất kỳ luụn cú cựng màu. Ta cần chứng minh n+ 1 con ngựa bất kỳ luụn cú cựng màu. Paradox Lỗi ở đõu? 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ứ nhất gồm n= 1 con ngựa n =1 Tập thứ hai gồm n= 1 con ngựa Paradox Fall 2006 Toỏn rời rạc A bit of humor Fall 2006 Toỏn rời rạc Chương 2. BÀI TOÁN TỒN TẠI Giới thiệu bài toỏn Cỏc kỹ thuật chứng minh cơ bản Nguyờn lý Dirichlet Định lý Ramsey Fall 2006 Toỏn rời rạc 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 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 3.1. Phỏt biểu nguyờn lý (Pigeonhole Principle) Chứng minh. V iệ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 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 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 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 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ú 2 32 = 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 Nguyờn lý Dirichlet tổng quỏtGeneralized 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 Nguyờn lý Dirichlet tổng quỏtGeneralized 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 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 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ú 2 32 = 4 294 967 296 hàm răng khác nhau. Ta cần tìm số n nhỏ nhất để  n /2 32  = 3. Từ đó số người cần tìm là 2 2 32 + 1 = 8 589 934 593 . Fall 2006 Toỏn rời rạc 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 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 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ử a j là tổng số trận thi đấu cho đến hết ngày thứ j của đội. Khi đó a 1 , a 2 , ..., a 30 là dãy tăng các số nguyên dương và đồng thời 1  a j  45. Suy ra dãy a 1 + 14 , a 2 + 14 , ..., a 30 + 14 cũng là dãy tăng các số nguyên dương và 15  a j + 14  59 . Fall 2006 Toỏn rời rạc Vớ dụ 2 Tất cả có 60 số nguyên dương a 1 , a 2 , ..., a 30 , a 1 + 14 , a 2 + 14 , ..., a 30 + 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ố a 1 , ..., a 30 là đôi một khác nhau và các số a 1 + 14 , ..., a 30 + 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 a i = a j + 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 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à a 1 , a 2 , . . . , a n+ 1 . Viết mỗi một số a j trong n+ 1 số trên dưới dạng: a j = 2 k ( j ) q j , j = 1, 2, ..., n +1 trong đó k ( j ) là nguyên không âm, q j là số lẻ. Fall 2006 Toỏn rời rạc Vớ dụ 3 Các số q 1 , q 2 , ..., q n+ 1 là các số nguyên lẻ, mỗi số không lớn hơn 2 n . Do trong đoạn từ 1 đến 2 n chỉ có n số lẻ, nên từ nguyên lý Dirichlet suy ra là hai trong số các số q 1 , q 2 , ..., q n+ 1 là bằng nhau, tức là tìm được hai chỉ số i và j sao cho q i = q j = q . Khi đó a i = 2 k ( i ) q , a j = 2 k ( j ) q . Suy ra nếu k ( i ) < k ( j ) thì a j chia hết cho a i , còn nếu k ( i )  k ( j ) thì a i chia hết cho a j . Fall 2006 Toỏn rời rạc Vớ dụ 4 Vớ dụ 4. Trờn mặt phẳng cho 5 điểm cú toạ độ nguyờn M i ( x i , y i ), 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 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à M i , M j . Khi đú điểm giữa G ij của đoạn thẳng nối M i và M i cú toạ độ G ij = (( x i +x j )/2, ( y i +y j )/2). Do x i và x j cũng như y i và y j cú cựng tớnh chẵn lẻ nờn cỏc toạ độ của G ij 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 2 n + 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 Vớ dụ 5 Trước hết ta cần một số khỏi niệm. Cho a 1 , a 2 , a n 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 a i 1 , a i 2 , , a i m , trong đú 1  i 1 < i 2 < . . . < i m  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 Vớ dụ 5 Định lý: Mỗi dóy gồm n 2 +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 = 3 2 +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 Vớ dụ 5 Chứng minh: Giả sử a 1 , a 2 , , a n 2 +1 là dóy gồm n 2 +1 số phõn biệt. Gỏn cho mỗi số hạng a k của dóy số cặp cú thứ tự ( i k ,d k ), trong đú i k là độ dài của dóy con tăng dài nhất bắt đầu từ a k cũn d k là độ dài của dóy con giảm dài nhất bắt đầu từ a k . Vớ dụ: 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 a 2 = 11 , (2,4) a 4 = 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 đú i k và d k là cỏc số nguyờn dương  n , với k = 1, 2, ..., n 2 +1. Fall 2006 Toỏn rời rạc Vớ dụ 5 Do 1  i k , d k  n , nờn t heo qui tắc nhõn cú tất cả n 2 cặp cú thứ tự dạng ( i k ,d k ) khỏc nhau. Do ta cú tất cả n 2 + 1 cặp ( i k ,d k ), 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 a s và a t trong dóy đó cho với s < t sao cho i s = i t và d s = d t . Ta sẽ chỉ ra điều này là khụng thể xảy ra. Do cỏc số hạng của dóy là phõn biệt, nờn hoặc là a s a t . Fall 2006 Toỏn rời rạc Vớ dụ 5 Nếu a s < a t , khi đú do i s = i t , ta cú thể xõy dựng dóy con tăng độ dài i t +1 bắt đầu từ a s , bằng cỏch nối đuụi nú bởi dóy con tăng độ dài i t , bắt đầu từ a t . ... , a s , ..., a t , .... Suy ra dóy con tăng dài nhất bắt đầu từ a s cú độ dài ớt ra là i t + 1, nghĩa là i s > i t . Mõu thuẫn với giả thiết i s = i t . Tương tự như vậy, nếu a s > a t , ta cú thể chỉ ra d s phải lớn hơn d t , và cũng đi đến mõu thuẫn. Định lý được chứng minh. Fall 2006 Toỏn rời rạc Fall 2006 Toỏn rời rạc Chương 2. BÀI TOÁN TỒN TẠI Giới thiệu bài toỏn Cỏc kỹ thuật chứng minh cơ bản Nguyờn lý Dirichlet Định lý Ramsey Fall 2006 Toỏn rời rạc 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 Vớ dụ mở đầu P A B C E D 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. Fall 2006 Toỏn rời rạc Vớ dụ mở đầu P A B C E D Nếu cả 3 cung AB, AC, BC cú màu đỏ thỡ chỳng tạo thành một tam giỏc đỏ. Fall 2006 Toỏn rời rạc 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 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 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 K n 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 K n = ( 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 K n . Mỗi đoạn nối hai đỉnh u, v  V sẽ được gọi là một cạnh của K n và ký hiệu là ( u, v ) , và tập E được gọi là tập cạnh của K n . Fall 2006 Toỏn rời rạc 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 K 6 được tô bởi một trong hai màu xanh hoặc đỏ. Khi đó K 6 luôn chứa hoặc K 3 với tất cả các cạnh được tô màu xanh (gọi tắt là K 3 xanh) hoặc K 3 với tất cả các cạnh được tô màu đỏ (gọi tắt là K 3 đỏ). 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 K m với mỗi cạnh được tô bởi một trong hai màu xanh, đỏ luôn chứa hoặc là K i đỏ hoặc là K j xanh. Fall 2006 Toỏn rời rạc 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 K n bởi hai màu xanh, đỏ luôn tìm được hoặc K 2 đỏ hoặc K 7 xanh. R (2,7) là số nhỏ nhất có tính chất này. Fall 2006 Toỏn rời rạc Cỏc số Ramsey Xét một cách tô màu (tuỳ ý) các cạnh của K 7 . Rõ ràng hoặc là tìm được ít nhất một cạnh của K 7 đượ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ó K 2 đỏ. Còn nếu tất cả các cạnh đều tô bởi màu xanh thì ta có K 7 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 K 6 bởi màu xanh ta sẽ không tìm được K 2 đỏ và cũng không tìm được K 7 xanh. Vậy R (2,7) = 7. Fall 2006 Toỏn rời rạc 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 i 1  i 2 thì R ( i 1 , j )  R ( i 2 , j ). Fall 2006 Toỏn rời rạc 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 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 Ask questions! Fall 2006 Toỏn rời rạc Fall 2006 Toỏn rời rạc