Bài giảng Toán rời rạc - Phần 1: Lý thuyết tổ hợp - Chương 2: Bài toán tồn tại - Nguyễn Đức Nghĩa

Fall 2006 
Toán rời rạc 
Phần thứ nhất 
LÝ THUYẾT TỔ HỢP 
Combinatorial Theory 
Fall 2008 
Fall 2006 
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 
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 
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. 
Fall 2006 
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.” 
Fall 2006 
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 
Fall 2006 
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. 
Fall 2006 
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 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 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 đề (P ... 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