Phần thứ nhất
LÝ THUYẾT TỔ HỢP Combinatorial Theory
1
Fall 2006
Toán rời rạc
Fall 2008
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
2
Fall 2006
Toán rời rạc
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
3
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.
®Ó gi¶i ®¸p xem liÖu cã kh¶ n¨ng th¾ng hay kh«ng,
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 • 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.
4
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 s ao 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.”
5
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 Bc Cd Da
Dd Ca Bb Ac
Ba Ad Dc Cb
Cc Db Aa Bd
Mét lêi gi¶i trong trêng hîp n = 5 lµ
Aa Cd Eb Be Dc
Bb De Ac Ca Ed
Cc Ea Bd Db Ae
Dd Ab Ce Ec Ba
Ee Bc Da Ad Cb
6
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Õ nhng «ng ®· kh«ng thµnh c«ng. Tõ ®ã «ng ®· ®Ò ra mét gi¶ thuyÕt tæng qu¸t lµ: Kh«ng tån t¹i h×nh vu«ng la tinh trùc giao cÊp n = 4k + 2.
Tarri, n¨m 1901 chøng minh gi¶ thuyÕt ®óng víi n = 6,
b»ng c¸ch duyÖt tÊt c¶ mäi kh¶ n¨ng xÕp.
N¨m 1960 ba nhµ to¸n häc Mü lµ Boce, Parker, Srikanda chØ ra ®îc mét lêi gi¶i víi n = 10 vµ sau ®ã chØ ra ph ¬ng ph¸p x©y dùng h×nh vu«ng la tinh trùc giao cho mäi n = 4k+2, víi k > 1.
7
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Õ,
8
Fall 2006
Toán rời rạc
•H×nh häc x¹ ¶nh (Projective Geometry), •...
Bµi to ¸n 4 mµu
Cã nh÷ng bµi to¸n mµ néi dung cña nã cã thÓ gi¶i thÝch cho bÊt kú ai, tuy nhiªn lêi gi¶i cña nã th× ai còng cã thÓ thö t×m, nhng mµ khã cã thÓ t×m ®îc. Ngoµi ®Þnh lý Fermat th× bµi to¸n 4 mµu lµ mét bµi to¸n nh vËy.
Bµi to¸n cã thÓ ph¸t biÓu trùc quan nh sau: Chøng minh r»ng mäi b¶n ®å trªn mÆt ph¼ng ®Òu cã thÓ t« b»ng 4 mµu sao cho kh«ng cã hai níc l¸ng giÒng nµo l¹i bÞ t« bëi cïng mét mµu.
Chó ý r»ng, ta xem nh mçi níc lµ mét vïng liªn th«ng vµ hai níc ®îc gäi lµ l¸ng giÒng nÕu chóng cã chung biªn giíi lµ mét ®êng liªn tôc.
9
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.
A
B
C
D
10
Fall 2006
Toán rời rạc
Bài toán 4 màu
ấ ề ề ậ ư ủ ứ
ượ V n đ này đ ử
ừ Frederick Guthrie, còn Guthrie t
ế ự ệ t s ki n này t ườ c đ c p trong b c th c a Augustus De Morgan g i W. R. Hamilton năm 1852 (De Morgan ừ bi ng ủ i anh trai c a mình...)
ứ ề ượ ố c công b
ư ề ỗ ấ Trong 110 năm r t nhi u ch ng minh đ i. nh ng đ u có l
Năm 1976, Appel và Haken đã đ a ra ch ng minh
ư ứ
ệ ử ằ b ng máy tính đi n t !
11
Fall 2006
Toán rời rạc
K. Appel and W. Hankin, "Every planar map is 4 colorable," Bulletin of the AMS, Volume 82 (1976), 711712.
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
ướ ạ ồ ị ẳ ọ i d ng bài toán tô màu đ th ph ng. d
ả ế ầ i quy t Bài toán 4 màu đóng góp ph n quan
ệ ể ệ Vi c gi ọ ế ồ ị 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
12
Fall 2006
Toán rời rạc
tr ng.ọ
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).
13
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).
14
Fall 2006
Toán rời rạc
Giả thuyết 3x + 1
ế x+1 (conjecture)
Gi
i
ươ
ả thuy t 3 • Gi ả ử s hàm ố ẻ ớ s l
f(x) tr l ọ ố . V i m i s nguyên d
ả ạ x/2 n u ế x là s ch n và 3 x+1 n u ế x là i ng
ố ẵ x, luôn t n t
ồ ạ n sao cho
+ =
=
n
(13) 3*13 1 40
f
=
f
( ) x
f
=
=
(40) 40/ 2 20
f
( (...( ( ))...)) f f x 1 4 4 2 4 4 3 l�n g�i h�m f n
=
=
(20) 20/ 2 10
f
=
=
f
(10) 10/ 2 5 + =
=
(5) 3* 5 1 16
f
• là b ng 1. ằ
=
=
f
=
=
(16) 16/ 2 8 (8) 8/ 2 4
f
=
=
(4) 4/ 2 2
f
=
=
(2) 2/1 1
f
15
Fall 2006
Toán rời rạc
Giả thuyết 3x + 1
ả
ạ
thuy t 3
ế x+1: Đo n ch ọ ố ớ
ng trình sau đây luôn ươ
x:
ươ Gi ế k t thúc v i m i s nguyên d
ng
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.''
ứ
ớ ọ x (cid:0)
Đã ch ng minh v i m i
5.6*1013
16
Fall 2006
Toán rời rạc
Một số vấn đề mở Open problems
ố
ố ủ ổ ề n >2 đ u là t ng c a 2 s nguyên t ế ậ ọ n đ n t n 4*10 14 ế thuy t là đúng sinh đôi (Twin prime conjecture)
ỉ sinh đôi (nghĩa là ch chênh
Goldbach’s Conjecture • M i s nguyên ỗ ố • Đã ch ra là đúng v i m i ớ ỉ • Nhi u ng ả ằ ườ ề i cho r ng gi ố ặ ố C p s nguyên t • Có vô s c p s nguyên t ố ố ặ ố
107,001±1
• C p sinh đôi l n nh t: 318,032,361*2
ấ
ằ
17
ấ ạ ệ l ch nhau 2) ớ ặ • S này có 32,220 ch s ! ữ ố c cho r ng là đúng ả ẻ i s hoàn h o l (Odd perfect number) ề ữ ộ ế ượ c m t trong nh ng v n đ i quy t đ ố • Cũng đ ượ ồ ạ ố Không t n t ả N u b n gi
Toán rời rạc
ế này .... Fall 2006
ẢO GIÁC
18
Fall 2006
Toán rời rạc
Fractals
19
Fall 2006
Toán rời rạc
A bit of humor: Computer terminology
20
Fall 2006
Toán rời rạc
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
21
Fall 2006
Toán rời rạc
2. Các kỹ thuật chứng minh
ở ầ ứ ứ
ứ
ả
ứ
ề
ả
2.3. Ch ng minh b ng ph n đ (Proof by
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) ằ Contrapositive) ằ
ọ
ứ
2.4. Ch ng minh b ng qui n p toán h c (Proof by
ạ Mathematical Induction)
22
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 đ
ượ
ể ế ọ
23
Fall 2006
Toán rời rạc
ế c không? ế ả ờ i là: Không có bí quy t, không có phép màu. ộ ố ế ư ầ ề t m t s t t ộ ố ỹ ữ ắ Câu tr l ấ duy, hi u bi V n đ quan tr ng là c n bi ậ ơ ả ự ệ s ki n và n m v ng m t s k thu t c b n
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à
ả ấ ấ ơ
ố ứ ộ
ậ ặ t ho c suy ra
ế ừ ả gi ướ t
ể i đ c
ả ế ấ ưở ế thi c đó. ữ ườ ọ ầ i thích – c n cho ng ủ ng đ n c u trúc c a ch ng minh.
và không có nh h ứ
ứ
ế
ủ ơ ả ẽ ỗ ệ ề dãy các m nh đ , m i m t trong s chúng s • ho c là gi ặ ế ả ặ t, ho c là thi • k t lu n đ ế ự ượ c suy tr c ti p t ứ ả ế ừ các k t qu đã ch ng minh tr Ngoài ra có th có nh ng gi ả M t ch ng minh trình bày t ề i đ c đ ướ ố ẽ ấ ễ ặ ắ ế ữ ứ ỗ t s r t d theo dõi: M i ượ c ậ c d n d t đ n k t lu n ế ắ t ng m c do nh ng tình ti
24
Fall 2006
Toán rời rạc
ộ ướ c trong ch ng minh đ u rõ ràng ho c ít ra là đ b ườ ọ ượ ẫ ả i thích rõ ràng, ng gi ữ ặ mà không g p nh ng v không rõ ràng gây ra.
2
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:
ượ
i d ng
ộ ố ự M t s th c đ ướ ạ ễ di n d ự th c không là s h u t ế ể ể ố ữ ỷ n u nó có th bi u ọ c g i là s h u t ố ộ ố p/q, v i ớ p và q là các s nguyên. M t s ố s vô t ố ữ ỷ ượ ọ đ c g i là ỷ.
ị ọ ố ươ ơ ả Đ nh lý c b n c a s h c:
ủ ố ọ M i s nguyên d ấ ướ ạ
ẽ ọ ố
25
Fall 2006
Toán rời rạc
ố ẽ ế ắ ủ ố ộ ễ ể ể có th bi u di n m t cách duy nh t d ố các s nguyên t (s vi nguyên t ề ng đ u ủ i d ng tích c a ừ ố mà ta s g i là phân tích ra th a s t t PTNT) c a s đó. t là
2
Ví dụ: Chứng minh là số vô tỷ
ị ả ươ ng trình s tho mãn ph
ố ữ ỷ , thì ta có th vi ể ế t
Ký hi u ệ s = 21/2. Theo đ nh nghĩa, s2 = 2. N u ế s là s h u t s = p/q ố trong đó p và q là hai s nguyên. B ng cách chia cho ể gi ầ ế p và q không có chung n u c n, ta có th chung nào ngoài 1. ể
ế ả ằ t là thi ướ c c ướ
ng trình đ u tiên, sau khi
ế ộ ổ ươ ễ Thay bi u di n này vào ph ượ bi n đ i m t chút, ta thu đ ươ c ph ầ ng trình
26
Fall 2006
Toán rời rạc
p2 = 2 q2 .
2
Ví dụ: Chứng minh là số vô tỷ
ế ư Th nh ng, theo
ừ ố ệ
ế ằ
ừ ố ơ ả ủ ố ọ , 2 là th a s ị đ nh lý c b n c a s h c ố ố trong PTNT c a ủ p2 . Do 2 là s nguyên t , nên nó cũng là 2 cũng xu t ấ ủ p. T đó suy ra, 2 ừ th a s trong PTNT c a ủ p2, và vì th trong c PTNT c a ủ ả ế hi n trong 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
ư ươ ậ nh trên (nh đ i v i
ư ậ ố ủ q. Nh v y, ta th y ả ẫ ề ớ ư ố ớ p2) ta có th k t lu n 2 ể ế ấ p và q có ế p và thi t
ừ ố ướ ự ng t ừ ố c a là th a s nguyên t chung th a s 2. Đi u đó là mâu thu n v i gi q không có c chung nào ngoài 1.
Kh ng đ nh đ
.
27
Fall 2006
Toán rời rạc
ẳ ị ượ ứ c ch ng minh
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 ế
Đ nh lý. N u
ế a chia h t ế b và b chia h t ế c thì a chia
ắ ầ ầ ủ ấ c u c a tính ch t chia h t. ị h t ế c.
Proof. Theo gi ồ ạ
ế ế ị t, và đ nh nghĩa tính chia h t, ta suy
ả thi ố i các s nguyên ra t n t k1 và k2 sao cho
c = a k, do đó theo 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à
28
ố ế a chia h t ế c.
Toán rời rạc
ề ị đ nh nghĩa v tính chia h t, Fall 2006
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". N u ế a chia h t ế b và b chia h t ế c ụ ừ Trong ví d v a nêu, "P" là “ " 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 ế
ở
ể ị ư ế “P” và k t thúc b i "Q". Q
ự
ự
ứ
ạ
ạ ừ
ể
ạ
ự ắ ầ ừ suy di n b t đ u t P (cid:0) ... (cid:0) ứ ả ế ầ ớ ứ Ph n l n các ch ng minh là ch ng minh tr c ti p. Khi ph i ế ử ắ ầ ừ ứ ch ng minh tr c ti p, ch ng minh, b n nên th b t đ u t ư ố ngo i tr tình hu ng b n có lý do xác đáng đ không làm nh v y. ậ
29
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
ươ ng.
ẻ , khi đó s 2 ả ử a+1 là s nguyên l
ố ớ n1 s không, trong đó n là s ố
ươ ph ố CM. Gi 2a+1 = (a+1)2 a2. ố Ví d 2.ụ S 100...01 (v i 3 ng) là h p s . nguyên d
CM. Ta có th vi
ể ế
ử ụ ươ ợ ố 3n + 1, trong đó n là s ố t 100...01 = 10 ẳ ằ ng. S d ng h ng đ ng th c ứ a3 + b3 = (a+b)(a2 a
nguyên d b + b2) v i ớ a = 10n và b = 1, ta thu đ c ượ
30
ươ (10n)3 + 1 = (10n + 1)(102n 10n + 1). Do (10n + 1) > 1 và (102n 10n + 1) > 1 khi n là nguyên d ng
Toán rời rạc
nên ta có đpcm. Fall 2006
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 t r ng P và Not Q là đúng. Mâu thu n thu đ ả ớ
ả ế ứ ế
ậ ả ượ c có ế t đã thi
ộ ế ề ộ ạ ư ặ ẫ ế ằ thi ữ ể th là m t k t lu n trái v i m t trong nh ng gi ẳ cho ho c đi u phi lý, ch ng h n nh 1 = 0.
ủ ỷ ụ trong ví d
31
Fall 2006
Toán rời rạc
ố ư ậ ứ ở ầ ộ ậ Ch ng minh căn b c hai c a 2 là s vô t ụ ứ m đ u là m t ví d ch ng minh nh v y.
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ã:
... (cid:0)
a2
a7 < 100. 10 < a 1 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.
32
Toán rời rạc
Fall 2006 Gi¶ thiÕt ®iÒu nµy kh«ng x¶y ra.
(cid:0) (cid:0)
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 (cid:0) a2 + a3 (cid:0) a3 + a4 (cid:0) a4 + a5 (cid:0) a5 + a6 (cid:0)
a 3, a 4, a 5, a 6, a 7.
Tõ gi¶ thiÕt a1, a2 cã gi¸ trÞ lín h¬n 10, ta nhËn ®îc a 3 > 20. Tõ a 2 > 10 vµ a3 > 20, ta nhËn ®îc a4 > 30, ..., cø nh vËy ta nhËn ®îc a 5 > 50, a6 > 80 vµ a7 > 130.
33
Toán rời rạc
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ô Fall 2006 1.
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, 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ã
13,
13,
13,
34
Fall 2006
13, Toán rời rạc
x1 + x 2 + x 3 (cid:0) x2 + x 3 + x 4 (cid:0) . . . . . x9 + x 10 + x1 (cid:0) x10 + x1 + x2 (cid:0)
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
MÆt kh¸c do
ra 130. 3(x1 + x 2 + . . . + x 10) (cid:0)
3(x1 + x 2 + . . . + x 10) = 3 (0 + 1 + 2 + . . . + 9) = 135,
suy ra
M©u thuÉn thu ®îc ®· chøng tá kh¼ng ®Þnh trong
130. 135 = 3(x1 + x 2 + . . . + x 10) (cid:0)
35
Fall 2006
Toán rời rạc
vÝ dô lµ ®óng.
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 ỗ c n i v i đúng 5
ể ố ượ ố ớ ứ ạ
ộ thành m t m ng sao cho m i máy đ máy khác.
Gi
ượ ố ả ử ượ ạ i là tìm đ c cách n i 31 máy sao s ng
c l ượ ố ớ ố c n i v i đúng 5 máy khác. Khi đó s
i:ả Gi ỗ cho m i máy đ ố ượ l
ng kênh n i là 5(cid:0) 31/2 = 75,5 ?!
ượ ứ ẳ ị thu đ c đã ch ng minh kh ng đ nh trong ví
36
Fall 2006
Toán rời rạc
ề Đi u phi lý ụ d là đúng.
2.3. Chứng minh bằng phản đề (Proof by Contrapositive)
ả ứ ề ử ụ ự ươ ươ ng đ
Ch ng minh b ng ph n đ s d ng s t ủ ị
ệ ằ ề
(cid:0) ng ủ c a hai m nh đ "P kéo theo Q" và “Ph đ nh Q kéo theo ph đ nh P". Q)(cid:0) ủ ị (P (cid:0) (¬Q (cid:0) ¬P).
ủ ế
Ví d , kh ng đ nh “N u đó là xe c a tôi thì nó có màu ớ ng v i “N u xe đó không có màu ả ủ
ươ
ậ ậ ẳ ụ ị ế ươ ng đ m n" là t m n thì nó không ph i c a tôi".
Do đó, đ ch ng minh “N u P, Thì Q" b ng ph
ươ
ằ ủ ị ứ ề ể ả ứ ế
37
Fall 2006
Toán rời rạc
ủ ị ế 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“).
2.3. Chứng minh bằng phản đề
ố x+y là s ố
Ví d 1.ụ N u ế x và y là hai s nguyên sao cho x và y có cùng tính ch n l
ẵ ch n, thì ẵ ẻ .
ệ ề ủ ả ẳ
ị ẵ ẻ ế x CM. M nh đ ph n đ c a kh ng đ nh đã cho là “N u ủ ổ , thì t ng c a
ề ố ố ẻ và y là hai s nguyên không cùng ch n l chúng là s l ."
Vì th ta gi
ế s r ng
ả s r ng
ờ ẵ ẻ x và y không cùng ch n l . Không ẻ ẵ y là l x là ch n còn . Khi đó k và m sao cho x = 2k và y = x+y = 2k + 2m + 1 = 2(k+m)
ả ử ằ ả ử ằ ổ gi m t ng quát, gi ố ượ c các s nguyên ta tìm đ 2m+1. Bây gi ta tính t ng ố ẻ + 1, mà rõ ràng là s l ổ .
38
Fall 2006
Toán rời rạc
ụ ừ ẳ ả ị T đó suy ra kh ng đ nh cu ví d là đúng.
2.3. Chứng minh bằng phản đề
ế
ố
ươ
ằ
ặ
ng sao cho n mod 4 là b ng 2 ho c
Ví d 2.ụ N u n là s nguyên d
ế
ươ
ố
ế
ố
3, th thì n không là s chính ph ề
ẽ ứ
CM. Ta s ch ng minh m nh đ ph n đ : “N u n là s chính
ệ ả ằ
ng. ả ặ
ươ
ề ng thì n mod 4 ph i b ng 0 ho c 1."
ể ả
ố
ph Gi
s n = k
2. Có 4 tình hu ng có th x y ra.
ế
2
ả ử • N u k mod 4 = 0, thì k = 4q, v i q nguyên nào đó. Khi đó, n = k ớ
= 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.
39
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".
ả ử
ứ
ả
ố s có P và Not Q ta c
ẫ
ỉ
ả
ả ử
ả
ằ ứ Ch ng minh b ng ph n ch ng: Gi ề ắ 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 ươ ứ ụ ng có m c đích rõ ràng là: Ch ng minh Not P. Trong ph ẫ ả ố ắ ả 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ì.
40
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
ề P(n) là đúng
nhiên
ệ n.
ệ ứ
nh nguyên lý “hi u ng
ậ ứ ả ta ph i ch ng minh m nh đ ọ ố ự ớ v i m i s t ự ư ươ T ng t domino”.
ọ
ơ ồ ứ
S đ ch ng minh:
ứ
ạ “Nguyên lý qui n p toán h c ấ th nh t”
“The First Principle of Mathematical Induction”
ế
P(0) (cid:0) n(cid:0) 0 (P(n)(cid:0) P(n+1)) ậ (cid:0) n(cid:0) 0 P(n) K t lu n:
41
Fall 2006
Toán rời rạc
The “Domino Effect”
…
Bước #1: Domino #0 đổ. Bước #2: Với mọi n(cid:0) N, nếu domino #n đổ, thì domino #n+1 cũng đổ.
6
Kết luận: Tất cả các quân
5
4 bài domino đều đổ!
3
2 ề
1
0
42
Fall 2006
Toán rời rạc
Chú ý: ả đi u này x y ra ả ngay c khi có vô h nạ quân bài domino!
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 “ • M i t p con khác r ng các s nguyên không âm đ u có
ỗ
ư
ỏ
ề
ế
ủ ả ủ wellordering property”: ỗ ậ ỗ ấ ầ ử ỏ ph n t nh nh t”. N : (cid:0) m (cid:0) S (cid:0) (cid:0) (cid:0) ậ T đó suy ra t p { nh nh t
S : m (cid:0) S : (cid:0) n (cid:0) n n|(cid:0) P(n)} (n u khác r ng) có ế ấ m, th nh ng đi u đó là trái P(m−1) là đúng,
ừ ầ ử ph n t ứ ề ớ v i đi u đã ch ng minh: Ta có suy ra P((m−1)+1) là đúng?!
43
Fall 2006
Toán rời rạc
(cid:0) (cid:0)
Sơ đồ chứng minh bằng qui nạp yếu
ầ
ả ử
P(n) là đúng (cid:0) n (cid:0)
m .
P(m) là đúng.
ế
sả ử P(n) là đúng
ể
ứ ạ Ch ng minh
P(n+1)
ứ Gi ứ ạ Ch ng minh C s qui n p: ạ Gi Gi t qui n p: thi B c chuy n qui n p:
ạ
ậ Theo nguyên lý qui n p ta có
P(n)
m.
s ta c n ch ng minh ơ ở ả ướ là đúng. ế K t lu n: là đúng (cid:0) n (cid:0)
44
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)
0 (cid:0)
n P(k)) (cid:0)
P(n+1)
k (cid:0) ậ (cid:0) n(cid:0) 0: P(n)
ạ
(cid:0) n(cid:0) 0: ((cid:0) K t lu n S khác bi
ướ
ể
ế ự ệ ớ ơ ồ • B c chuy n qui n p s d ng gi
ứ
ế ở ỗ
t v i s đ qui n p “y u”
ch :
ạ ử ụ
ế m nhạ
ả
t
thi
ỏ ơ k 45 Fall 2006 Toán rời rạc ố ướ P là đúng trong m iọ tình hu ng tr c ả ử ứ ầ Gi s ta c n ch ng minh P(n) là đúng (cid:0) n (cid:0) 0. P(0) là đúng. sả ử P(k) là đúng (cid:0) 0 (cid:0) k (cid:0) t qui n p: thi C s qui n p:
Gi
n. P(n+1) là c chuy n qui n p: B ạ P(n) là K t lu n:
đúng (cid:0) n (cid:0) 0. 46 Fall 2006 Toán rời rạc 47 Fall 2006 Toán rời rạc 48 Fall 2006 Toán rời rạc 49 Fall 2006 Toán rời rạc 50 Fall 2006 Toán rời rạc 51 Fall 2006 Toán rời rạc ể ướ ủ ờ n (cid:0)
2n. Ta
ướ n+1 (cid:0)
c 2 Gi
ả ử
c 2
s ta có th ph kín bàn c kích th
ả
ph i ch ng minh có th ph kín bàn c kích th
2n+1. ể ủ ứ ờ ậ ờ n+1 (cid:0) Th c v y, chia bàn c 2 ế ả thi ự
ầ
ầ ướ 2n (cid:0)
c
ể ỗ
ỗ
ặ
ủ ầ ượ 2n. Theo gi
ở
ủ
2n+1 ta thu đ 52 Fall 2006 Toán rời rạc ầ
2n+1 ra thành 4 ph n, m i
ạ
ph n kích th
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 (cid:0)
c cách ph c n
tìm. ặ ườ ở ị Trên m t ph ng v ẳ
ng th ng
ả ử ụ ẳ
ỏ
ể ở ị ẳ ạ ở ẽ n đ
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 đ
ẳ
ng th ng v ỏ ạ ở ộ ị c chia
ở
b i n đ
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. 53 Fall 2006 Toán rời rạc ượ ộ ơ ở ặ ẳ ầ ẽ
ầ
c chia làm hai ph n, m t ph n s C s qui n p: Khi n = 1, m t ph ng đ ạ ạ
tô màu xanh, ph n còn l ẳ ế ườ ả ầ
ị
c h t ta v n1 đ ng th ng. Theo gi ả ử ẳ
ứ
Gi
s kh ng đ nh đúng v i n1, ta ch ng minh kh ng đ nh đúng v i n.
ự ậ
Th c v y, tr ỏ
i tô màu đ .
ớ
ẽ
ở
ườ ướ
ầ
ẳ ị
thi
ệ
ẳ ứ ẳ ườ ặ ề
ặ
ượ
c chia b i n đ ầ ủ
ẽ ữ ướ ở
c đó. Trái l
ượ ẳ
ặ ẳ ả ớ
ẳ
ể
ạ
ế
t qui n p có th
ờ
ặ
ả
ta
ầ
ng th ng th n. Đ ng th ng này chia m t ph ng ra làm hai ph n,
ầ
ẳ
ẳ
ng th ng
ạ
ử
nguyên màu đã tô tr
i, các
ầ ẽ ượ
ỗ
c xanh c tô màu đ o ng ỏ ộ ử ạ ặ ặ ở ẳ
cùng m t n a m t ph ng A ho c B là không 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
ẽ ườ
v đ
ọ
g i là ph n A và B. Các ph n c a m t ph ng đ
ặ
ở
bên n a m t ph ng B s gi
ử
ầ
ph n trong n a m t ph ng A m i ph n s đ
ỏ
thành đ và đ thành xanh. Rõ ràng:
• Hai ph n có chung c nh ườ ầ
có chung màu.
ầ • Hai ph n có chung c nh trên đ ử ẳ
ạ
tô cùng màu (do màu bên n a A b đ o ng ị
ng th ng th n rõ ràng cũng không b
ị ả
ị ứ
ượ
c).
ớ ọ ẳ ậ ạ
V y P(n) đúng. Theo qui n p kh ng đ nh đúng v i m i n. 54 Fall 2006 Toán rời rạc Đ X X X Đ Đ X Đ Đ 55 Fall 2006 Toán rời rạc Đ A X X Đ Đ X X Đ X X Đ Đ Đ X Đ 56 Fall 2006 Toán rời rạc 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
ở
ườ ứ
i đ ng
ạ
ứ
i trong hàng luôn đ ng c nh
ộ
ng c a đ i th ng đ i mình và m t ủ ộ ả ộ ể ế
hàng ngang sao cho ngo i tr hai ng
ườ
hai mép, m i ng
ủ
ộ ộ
m t đ i tr
ộ ưở
đ i tr ng c a đ i thua đ i mình trong gi i. 57 Fall 2006 Toán rời rạc 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 ứ ả ử n1) là đúng, ta ch ng minh P( s P( n) là đúng. Tr ế ướ ộ ng c a các đ i 1, 2,..., ộ ưở
ạ c h t, ta x p
ả ể ế ọ thi ế n1 đ i tr
ế
ả ệ ả ể ả t hàng đó là: ề
ế
thi 58 Fall 2006 Toán rời rạc (cid:0) (cid:0) (cid:0) ủ
n
t qui n p, luôn có th x p h ra thành
1. Theo gi
ầ
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
2 (cid:0)
1(cid:0) n1. ... (cid:0) Bây gi ờ ộ ưở ẽ ỗ
ta s tìm ch cho đ i tr ủ
ng c a đ i ộ n. Có 3 ắ
ộ n th ng đ i 1
1(cid:0) ầ
ộ , thì hàng c n tìm là:
2 (cid:0)
n1. ầ (cid:0) (cid:0) (cid:0) 2 (cid:0) ... (cid:0)
ộ n thua đ i ộ n1, thì hàng c n tìm là:
n1 (cid:0)
ắ ộ n1. ắ
ộ n th ng đ i ộ k. hàng g m
ị ộ
ữ ộ ưở ồ n1 đ i đã x p b ng cách
ủ ộ k1 ế
ằ
ng c a đ i (cid:0) (cid:0) (cid:0) 59 Fall 2006 Toán rời rạc tình hu ng:ố
• N u đ i
ế
n (cid:0)
• N u đ i
ế
... (cid:0)
1(cid:0)
n .
• N u đ i
ế
ộ
ộ n thua đ i 1 và th ng đ i
• G i ọ k là ch s nh nh t sao cho đ i
ấ
ỏ
ỉ ố
• Rõ ràng t n t
ư ậ
ồ ạ k nh v y.
i
• Hàng c n thu đ
ầ
ượ ừ
c t
ộ n vào v trí gi a đ i tr
ộ ưở
chèn đ i tr
ng đ i
và đ i ộ k. 1(cid:0) 2 (cid:0) ...(cid:0) k-1(cid:0) k (cid:0) k+1 (cid:0) ...(cid:0) n-1 (cid:0) (cid:0) (cid:0) n
Hàng cần tìm:
k-1(cid:0)
...(cid:0)
1(cid:0) n (cid:0) k (cid:0) k+1 (cid:0) ...(cid:0) n-1 60 Fall 2006 Toán rời rạc (cid:0) (cid:0) 61 Fall 2006 Toán rời rạc 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 62 Fall 2006 Toán rời rạc 3.1. Phát biểu nguyên lý
3.2. Các ví dụ ứng dụng 63 Fall 2006 Toán rời rạc ế ế ộ ề
ượ ố ượ
ơ n đ i t
ộ
ấ ng vào
ộ ứ ờ
n cái h p thì bao gi
ố
c ít nh t m t cái h p ch a ít ra là hai đ i 64 Fall 2006 Toán rời rạc N u x p nhi u h n
cũng tìm đ
ượ
ng.
t ơ ứ
ả ỉ
s ng ộ ậ
ượ ạ
c l
ơ ộ ỗ ộ ượ
ố ượ ề ả ộ
ổ
t quá
ượ
ng đ ế
thi t là có nhi u h n
. 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
i là
ứ
ượ
c cái h p nào ch a không ít h n 2
không tìm đ
ứ
ề
ố ượ
đ i t
ng. Đi u đó có nghĩa là m i cái h p ch a
ố
ừ
ộ ố ượ
ng. T đó suy ra t ng s
không quá m t đ i t
ố ượ
n,
n cái h p là không v
ng x p trong
đ i t
ơ n đ i t
ế
ớ
c
trái v i gi
ế
x p trong chúng 65 Fall 2006 Toán rời rạc ượ c nhà toán h c ng ườ
ế ấ ề ệ ứ
ọ
i Đ c là Dirichlet
ả
i quy t r t nhi u bài toán h p. ậ ủ ượ ng đ ả ộ ố ượ
ở c thay b i các cái gi ề ả 66 Fall 2006 Toán rời rạc ượ
ơ n qu táo vào n cái gi
ỏ ứ ỏ
ượ ấ ậ
ậ
L p lu n trên đã đ
ậ ụ
v n d ng thành công vào vi c gi
ồ ạ ổ ợ
i t
t n t
ậ
Trong l p lu n c a Dirichlet, các đ i t
qu táo còn các cái h p đ
đem b nhi u h n
ộ
tìm đ c ít nh t m t cái gi c xét là các
ế
ỏ
: “N u
ờ
ỏ
cũng
thì bao gi
ả
ch a ít ra là 2 qu táo”. ậ ậ ệ ạ ượ
i đ c trình bày ồ Trong tài li u ti ng Anh l p lu n đó l
trong ngôn ng c a các con chim b câu: ồ ơ ế ề ờ ấ ứ ồ ồ ề ồ ế ậ ợ ư ề ạ ầ ử ượ
ượ ộ ậ ậ c phân ho ch
c m t t p con đ
cũng tìm đ 67 Fall 2006 Toán rời rạc ế
ữ ủ
ố
“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 ít nh t 1 cái l ng ch a
cũng tìm đ
í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
ờ
thành n t p con, thì bao gi
ự ượ
ạ
trong phân ho ch đó có l c l ng ít ra là 2” 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? 68 Fall 2006 Toán rời rạc 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. 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.
ấ ả ỉ
i:ả T t c ch có Gi
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û. 69 Fall 2006 Toán rời rạc ỏ ả
ng qu táo b vào
ề ầ
ỏ ố ượ
ng cái gi ỏ ứ ả ề ự ồ ạ
i cái gi
ợ
ườ ử ụ ư ậ ố
ỏ ượ
k cái gi
t quá s
v
ị
ẳ
nhi u l n thì rõ ràng kh ng đ nh trong
ch a ít ra là 2 qu táo là
ng h p nh v y ta s d ng nguyên lý Khi s l
ượ
l
nguyên lý v s t n t
quá ít. Trong tr
Dirichlet t ng quát sau đây: ổ ỏ ỏ “N u đem b n qu táo vào k cái gi
c ít nh t m t cái gi ượ ỏ ứ ế
tìm đ ch a ít ra là (cid:0) ọ ấ
ệ (cid:0)
đây ký hi u ả
ờ
cũng
thì bao gi
(cid:0) n/k(cid:0) qu táo”.
ả
ộ
(cid:0) g i là ph n nguyên già c a s th c
ủ ố ự (cid:0)
ơ
ớ
ỏ ấ ố ị 70 Fall 2006 Toán rời rạc (cid:0) Ở
ầ
theo đ nh nghĩa là s nguyên nh nh t còn l n h n
ặ ằ
ho c b ng . ứ ả ử ẳ 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
(cid:0) n/k(cid:0) 1 qu táo. T đó
ừ
ả
ỏ ứ
ch a không quá
cái gi
ỏ
ổ
k cái gi
suy ra t ng s qu táo b trong
không
ượ
t quá
v k((cid:0) n/k(cid:0) 1) < k((n/k+1) 1)) = n. ẫ ượ ứ Mâu thu n thu đ c đã ch ng minh nguyên lý. 71 Fall 2006 Toán rời rạc 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 (cid:0) 100/12(cid:0) = 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? 72 Toán rời rạc 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 (cid:0) n/5(cid:0) = 6. Sè nguyªn nhá nhÊt ®ã lµ n = 5(cid:0) 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 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? ấ ả ỉ
i:ả T t c ch có Gi
232 = 4 294 967 296
hµm r¨ng kh¸c nhau. Ta cÇn t×m sè n
nhá nhÊt ®Ó (cid:0) n/232(cid:0) = 3. Tõ ®ã sè ngêi
cÇn t×m lµ 2(cid:0) 232 + 1 = 8 589 934 593. 73 Fall 2006 Toán rời rạc ụ ứ ụ ơ ả ượ ự ọ ứ ạ
Trong các ví d ng d ng ph c t p h n
ả
ỏ
và qu táo
ơ ấ
c l a ch n khôn khéo h n r t ủ
c a nguyên lý Dirichlet, cái gi
ầ
c n ph i đ
nhi u.ề ộ ố ụ ầ ư
ẽ
Trong ph n này ta s xét m t s ví d nh v y.ậ 74 Fall 2006 Toán rời rạc 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. 75 Fall 2006 Toán rời rạc VÝ dô 2. Trong mét th¸ng gåm 30 ngµy mét ®éi bãng
chuyÒn thi ®Êu mçi ngµy Ýt nhÊt mét trËn, nhng kh«ng
ch¬i qu¸ 45 trËn. H·y chøng minh r»ng ph¶i t×m ®îc mét
giai ®o¹n gåm mét sè ngµy liªn tôc nµo ®ã trong th¸ng
sao cho trong giai ®o¹n ®ã ®éi ch¬i ®óng 14 trËn. Gi¶i: Gi¶ sö a j lµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø j cña ®éi. Khi ®ã a1, a2, ..., a 30 lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ ®ång thêi 1 (cid:0) 45. aj (cid:0) 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 (cid:0) aj +14 (cid:0) 76 Fall 2006 Toán rời rạc 59. TÊt c¶ cã 60 sè nguyªn d¬ng a 1, a2, ..., a 30, a1+14, a 2+14, ..., a 30+14, 77 Fall 2006 Toán rời rạc 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, ..., a 30 lµ
®«i mét kh¸c nhau vµ c¸c sè a1+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 = 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. trong ®ã tÊt c¶ ®Òu nhá h¬n hoÆc b»ng 59. 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, . . . , a n+1 . ViÕt mçi mét sè aj trong n+1 sè trªn díi d¹ng: aj = 2k(j)qj , j = 1, 2, ..., n+1 trong ®ã k(j) lµ nguyªn kh«ng ©m, qj lµ sè lÎ. 78 Fall 2006 Toán rời rạc 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 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, q 2, ..., q n+1 lµ b»ng nhau, tøc lµ t×m ®îc hai
chØ sè i vµ j sao cho qi = q j = q. nÕu k(i) (cid:0) Khi ®ã
ai = 2k(i)q, aj = 2k(j)q.
Suy ra nÕu k(i) < k(j) th× aj chia hÕt cho ai, cßn
k(j) th× a i chia hÕt cho aj. 79 Fall 2006 Toán rời rạc ẳ ặ ạ ộ ể ằ ể ạ ố
ạ ộ ữ ể ộ 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 ). 80 Fall 2006 Toán rời rạc ả ượ ộ ừ
ứ ể ạ ẳ c m t nhóm
Mi, Mj. Khi đó đi m ể T đó theo nguyên lý Dirichlet ph i tìm đ
ch a ít ra là 2 đi m, ch ng h n đó là
ạ
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 ố ẳ c ch ng minh. Kh ng đ nh c a ví d có th t ng quát cho không gian ứ
ị ụ ẵ ẻ
nên các
ụ
ủ
ị
ạ ộ ủ Gij là các s nguyên. Kh ng đ nh c a ví d
to đ c a
ượ
đ
ẳ
ề ể ạ
ể ộ 81 Fall 2006 ố
ạ ộ ể ổ
ủ
n
ạ
ề
nchi u cho 2
n + 1 đi m có to
chi u: “Trong không gian
ộ
ể
ượ
đ 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”. ữ
Toán rời rạc ầ ộ ố ướ ế c h t ta c n m t s khái ni m. ố ự ượ ọ ủ ố
c a dãy s đã cho. c g i là đ dàiộ
ủ ạ ệ
Tr
Cho a1,a2, … an là dãy s th c.
n đ
Ta g i ọ dãy con c a dãy đã cho là dãy có d ng ai1, ai2, …, aim, trong n ế ứ ỗ ố ạ ớ đó 1 (cid:0)
Dãy s đ ơ ố ạ ỗ ố ạ ứ ế Dãy s đ ặ ủ ặ ủ 82 Fall 2006 Toán rời rạc M i dãy g m ồ n2+1 s ố phân bi ứ ặ ộ ặ
ả ặ tệ (nghĩa là
ỗ
ừ
ầ ử
là khác nhau t ng đôi) luôn ch a ho c
n+1 ho c dãy con gi m ố ạ ả ặ các ph n t
dãy con tăng ng t đ dài
ặ ộ
n+1.
ng t đ dài
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
ả
ho c dãy con gi m ng t đ dài 4 83 Fall 2006 Toán rời rạc ng t đ dài 4 ph n t
ph n t 1, 4, 6, 12
1, 4, 6, 7
11, 9, 6, 5 Ch ng minh: Gi ố ặ ủ s
t. Gán cho m i s h ng ủ
ủ ả ứ
ệ
phân bi
(
th t
nh t b t đ u t
nh t b t đ u t ả ử a1, a2, …, an2+1 là dãy g m ồ n2+1 s ố
ỗ ố ạ
ak c a dãy s c p có
ộ
ứ ự ik,dk), trong đó ik là đ dài c a dãy con tăng dài
ộ
ấ ắ ầ ừ ak còn dk là đ dài c a dãy con gi m dài
ấ ắ ầ ừ ak. ụ Ví d : 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 a2 = 11 , (2,4)
a4 = 1 , (4,1) ồ ạ ư s không t n t ố i dãy tăng cũng nh dãy
n+1. Khi đó ik và dk là các s nguyên 84 Fall 2006 Toán rời rạc (cid:0) ả ử
ờ
Bây gi
gi
ộ
ả
gi m có đ dài
ươ
d ng n, v i ớ k = 1, 2, ..., n2+1. Do 1 (cid:0) ắ ấ ả n2 c p ặ t c Do ta có t có th t ik, dk (cid:0)
ứ ự ạ
d ng ( t c ik,dk), nên theo nguyên lý T c là t n t ồ ạ ứ as và at trong dãy đã cho v i ớ n, nên theo qui t c nhân có t
ik,dk) khác nhau.
ấ ả n2 + 1 c p (ặ
ố
Dirichlet, hai trong s chúng là trùng nhau.
ố ạ
i hai s h ng
s ẽ ỉ ủ 85 Fall 2006 Toán rời rạc ặ ề
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à ể ả
ệ
as > at. as < at ho c là ự ố ể
N u ế as < at, khi đó do is = it , ta có th xây d ng dãy con
ở
ắ ầ ừ as, b ng cách n i đuôi nó b i it+1 b t đ u t ộ ộ
tăng đ dài
dãy con tăng đ dài ằ it, b t đ u t ắ ầ ừ at. Suy ra dãy con tăng dài nh t b t đ u t ... , as , ..., at , .... ẫ ớ ấ ắ ầ ừ as có đ dài ít ra
ả
là it + 1, nghĩa là is > it. Mâu thu n v i gi
thi ộ
ế is= it.
t ự ư ậ ể ỉ ds ph i ả ế as > at, ta có th ch ra
nh v y, n u
ẫ
ế ươ
ng t
T
ơ dt, và cũng đi đ n mâu thu n.
ớ
l n h n 86 Fall 2006 Toán rời rạc ượ ứ ị
Đ nh lý đ c ch ng minh. 87 Fall 2006 Toán rời rạc 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 88 Fall 2006 Toán rời rạc 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 ®á. 89 Fall 2006 Toán rời rạc A P 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. 90 Fall 2006 Toán rời rạc A ế ả P B N u c 3 cung
AB, AC, BC có
ỏ
màu đ thì chúng
ộ
ạ
t o thành m t
tam giác đ .ỏ C E D 91 Fall 2006 Toán rời rạc 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.
ố
ư
ụ ể ấ ằ ố
ữ ẳ 92 Fall 2006 Toán rời rạc ẽ ở n > 6 thì kh ng ẳ
ế
Có th th y r ng n u thay con s 6 b i
ụ ẫ
ế
ị
đ 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 Nh v y có th th y 6 là ư ậ ể ỏ ị giá tr ị n nh nh t ẳ
ấ đ kh ng đ nh 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. 93 Fall 2006 Toán rời rạc ể ấ
. ụ
trong ví d là đúng §Ó cã thÓ ph¸t biÓu nh÷ng kÕt qu¶ tæng qu¸t h¬n §Þnh ng hÜ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. V sÏ ®îc gäi lµ mét c ¹nh cña • Mçi ®o¹n nèi hai ®Ønh u, v (cid:0) Kn vµ ký hiÖu lµ (u, v), vµ tËp E ®îc gäi lµ tËp c¹nh cña Kn. 94 Fall 2006 Toán rời rạc chóng ta cÇn ®Õn mét sè kh¸i niÖm. 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. 95 Fall 2006 Toán rời rạc §Þnh ng hÜa 2. Gi¶ s ö i vµ j lµ hai s è nguyªn s ao cho
i (cid:0)
2. S è nguyªn d¬ng m cã tÝ nh chÊt (i,j)
R am s e y 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. 2, j (cid:0) 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 ng hÜa 3. S è R am s e y R (i,j) lµ s è nguyªn d¬ng nhá nhÊt cã tÝ nh chÊt (i,j)R am s e y. 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. 96 Fall 2006 Toán rời rạc 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) (cid:0) Nhng R (2,7) kh«ng thÓ nhá h¬n 7, bëi v× nÕu t« tÊt
c¶ c¸c c¹nh cña K6 bëi mµu xanh ta sÏ kh«ng t×m ®
îc K2 ®á vµ còng kh«ng t×m ®îc K7 xanh. VËy R (2,7) = 7. 97 Fall 2006 Toán rời rạc 7. 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 > •NÕu m kh«ng cã tÝnh chÊt (i,j)-Ramsey, th× mäi m còng cã tÝnh chÊt nµy; sè n < m còng kh«ng cã tÝnh chÊt nµy; •NÕu i1 (cid:0) 98 Fall 2006 Toán rời rạc i2 th× R (i1,j) (cid:0) R (i2,j). 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 (cid:0)
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. 2, j (cid:0) §Þnh lý Rams e y. NÕu i (cid:0) 2, j (cid:0) 99 Fall 2006 Toán rời rạc 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)R am s e y (tõ ®ã s uy ra s è R (i,j) lµ tån t¹i). ừ ề ộ ố ở 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 đã đ
ị ượ
ớ Vi c xác đ nh ị i, j c th luôn là các bài ỉ
c nghiên c u.
ữ
R(i,j) v i nh ng giá tr
ườ ụ ể
ườ ế h p không t m th ớ
i ta m i bi t ệ
ổ ợ
ầ
toán t
ớ ấ
ị ủ R(i, j) v i r t ít giá tr c a (
giá tr c a ệ
ng. Hi n nay ng
ị ủ i,j). 100 Fall 2006 Toán rời rạc 101 Fall 2006 Toán rời rạc 102 Fall 2006 Toán rời rạc 103 Fall 2006 Toán rời rạcSơ đồ chứng minh bằng qui nạp mạnh
ơ ở
ứ
ạ Ch ng minh
ế
ả
ạ Gi
ể
ứ
ạ Ch ng minh
ướ
đúng.
ế
ậ Theo nguyên lý qui n p ta có
Ví dụ 1
Chứng minh rằng luôn có thể phủ kín bàn
2n (n > 1) bởi các quân
cờ kích thước 2n (cid:0)
bài hình chữ T (T-omino).
Cơ sở qui nạp: Bảng 22 x 22
Cơ sở qui nạp: Bảng 22 x 22
Cơ sở qui nạp: Bảng 22 x 22
Cơ sở qui nạp: Bảng 22 x 22
Bước chuyển qui nạp
VÍ DỤ 2
Ví dụ 2
Ví dụ 2
Ví dụ 2
B
X
X
Ví dụ 3
Ví dụ 3
Ví dụ 3
Ví dụ 3
A bit of humor…
Chương 2. BÀI TOÁN TỒN TẠI
3. Nguyên lý Dirichlet
3.1. Phát biểu nguyên lý
(Pigeonhole Principle)
3.1. Phát biểu nguyên lý
(Pigeonhole Principle)
ứ
ệ
ậ
3.1. Phát biểu nguyên lý
(Pigeonhole Principle)
3.1. Phát biểu nguyên lý
(Pigeonhole Principle)
Ví dụ
Ví dụ
Nguyên lý Dirichlet tổng quát
Generalized Pigeonhole Principle
Nguyên lý Dirichlet tổng quát
Generalized Pigeonhole Principle
Ví dụ
Ví dụ
3.2. Các ví dụ ứng dụng
Ví dụ 1
Ví dụ 2
Ví dụ 2
Ví dụ 3
Ví dụ 3
Ví dụ 4
Ví dụ 4
Ví dụ 5
ỏ
ặ n u m i s h ng đ ng sau luôn nh
i1 < i2 < . . . < im (cid:0)
ố ượ ọ
tăng ng tặ n u m i s h ng đ ng sau luôn l n
c g i là
ứ
ướ
h n s h ng đ ng tr
c.
ố ượ ọ
ả
c g i là
gi m ng t
ứ
ướ
ơ ố ạ
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
ả
Ví dụ 5
ị
Đ nh lý:
Ví dụ 5
Ví dụ 5
Ví dụ 5
Chương 2. BÀI TOÁN TỒN TẠI
Ví dụ mở đầu
Ví dụ mở đầu
Ví dụ mở đầu
Phân tích ví dụ
Phân tích ví dụ
Các số Ramsey
Các số Ramsey
Các số Ramsey
Các số Ramsey
Các số Ramsey
Các số Ramsey
Các số Ramsey
Ask questions!
