Bài giảng Toán rời rạc - Phần thứ nhất: Lý thuyết tổ hợp - Chương 2: Bài toán tồn tại - Nguyễn Đức Nghĩa
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
2
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
Fall 2006
3
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
4
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
5
Toán rời rạc
Bài toán về 36 sĩ quan
⚫ S•ử dAụn, Bg,: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
Fall 2006
6
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.
Fall 2006
7
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Õ nhng 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
8
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, 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.
Fall 2006
9
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
Fall 2006
10
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
11
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
12
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
13
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
14
Toán rời rạc
Giả thuyết 3x + 1
⚫ Giả thuyết 3x+1 (conjecture)
• Giả sử hàm f(x) trả lại x/2 nếu x là số chẵn và 3x+1 nếu x là số
lẻ. Với mọi số nguyên dương x, luôn tồn tại n sao cho
f (13) = 3*13 +1 = 40
f n (x) = f ( f (...( f (x))...))
f (40) = 40 / 2 = 20
n lÇn gäi hµm f
f (20) = 20 / 2 = 10
f (10) = 10 / 2 = 5
• là bằng 1.
f (5) = 3*5 +1 = 16
f (16) = 16 / 2 = 8
f (8) = 8/ 2 = 4
f (4) = 4 / 2 = 2
f (2) = 2 /1 = 1
Fall 2006
15
Toán rời rạc
Giả thuyết 3x + 1
⚫ Giả thuyết 3x+1: Đoạn chương trình sau đây luôn
kết thúc với mọi số nguyên dương x:
repeat
if x mod 2 = 0 then x:= x div 2
else x:= 3*x +1
until x=1;
⚫ Paul Erdös commented concerning the intractability
of the 3x+1 problem: ``Mathematics is not yet ready
for such problems.''
⚫ Đã chứng minh với mọi x 5.6*1013
Fall 2006
16
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*1014
• Nhiều người cho rằng giả thuyết là đúng
⚫ Cặp số nguyên tố sinh đôi (Twin prime conjecture)
• Có vô số cặp số nguyên tố sinh đôi (nghĩa là chỉ chênh lệch
• nChặapus2in)h đôi lớn nhất: 318,032,361*2107,001±1
•Số này có 32,220 chữ số!
• Cũng được cho rằng là đúng
⚫ Không tồn tại số hoàn hảo lẻ (Odd perfect number)
⚫ Nếu bạn giải quyết được một trong những vấn đề này ....
Fall 2006
17
Toán rời rạc
Fall 2006
18
Toán rời rạc
A bit of humor: Computer terminology
Fall 2006
20
Toán rời rạc
Tải về để xem bản đầy đủ
103 trang
25280
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán rời rạc - Phần thứ nhất: Lý thuyết tổ hợp - Chương 2: Bài toán tồn tại - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_toan_roi_rac_phan_thu_nhat_ly_thuyet_to_hop_chuong.ppt
