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

Chia sẻ: Diên Vu | Ngày: | Loại File: PPT | Số trang:108

Thêm vào BST

Báo xấu

88
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Toán rời rạc (Phần I: Lý thuyết tổ hợp): Chương 2(tt) - Nguyễn Đức Nghĩa

Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2009 Toán rời rạc 1
Nội dung Chương 0. Mở đầu Chương 1. Bài toán đếm Chương 2. Bài toán tồn tại Chương 3. Bài toán liệt kê tổ hợp Chương 4. Bài toán tối ưu tổ hợp Toán rời rạc 2
Chương 2. BÀI TOÁN TỒN TẠI 1. Giới thiệu bài toán 2. Các kỹ thuật chứng minh cơ bản 3. Nguyên lý Dirichlet 4. Định lý Ramsey Toán rời rạc 3
1. Giới thiệu bài toán  Trong ch¬ng tríc, ta ®· tËp trung chó ý vµo viÖc ®Õm sè c¸c cÊu h×nh tæ hîp. Trong nh÷ng bµi to¸n ®ã sù tån t¹i cña c¸c cÊu h×nh lµ hiÓn nhiªn vµ c«ng viÖc chÝnh lµ ®Õm sè phÇn tö tho¶ m·n tÝnh chÊt ®Æt ra.  Tuy nhiªn, trong rÊt nhiÒu bµi to¸n tæ hîp, viÖc chØ ra sù tån t¹i cña mét cÊu h×nh tho¶ m·n c¸c tÝnh chÊt cho tríc lµ hÕt søc khã kh¨n. • Ch¼ng h¹n, khi mét kú thñ cÇn ph¶i tÝnh to¸n c¸c níc ®i cña m×nh ®Ó gi¶i ®¸p xem liÖu cã kh¶ n¨ng th¾ng hay kh«ng, • Mét ngêi gi¶i mËt m· cÇn t×m kiÕm ch×a kho¸ gi¶i cho mét bøc mËt m· mµ anh ta kh«ng biÕt liÖu ®©y cã ®óng lµ bøc ®iÖn thËt ®îc m· ho¸ cña ®èi ph¬ng hay kh«ng, hay chØ lµ bøc mËt m· gi¶ cña ®èi ph ¬ng tung ra nh»m ®¶m b¶o an toµn cho bøc ®iÖn thËt ...  Trong tæ hîp xuÊt hiÖn mét vÊn ®Ò thø hai rÊt quan träng lµ: xÐt sù tån t¹i cña c¸c cÊu h×nh tæ hîp víi c¸c tÝnh chÊt cho tr íc - b µi to ¸n tån t¹i tæ hîp .  NhiÒu bµi to¸n tån t¹i tæ hîp ®· tõng th¸ch thøc trÝ tuÖ nh©n lo¹i vµ ®· lµ ®éng lùc thóc ®Èy sù ph¸t triÓn cña tæ hîp nãi riªng vµ to¸n häc nãi chung. Toán rời rạc 4
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.” Toán rời rạc 5
Bài toán về 36 sĩ quan  Sử dụng: • A, B, C, D, E, F ®Ó chØ c¸c phiªn hiÖu trung ®oµn, • a, b, c, d, e, f ®Ó chØ c¸c cÊp bËc sÜ quan.  Bµi to¸n nµy cã thÓ tæng qu¸t ho¸ nÕu thay con sè 6 bëi n.  Trong trêng hîp n =4, mét lêi gi¶i cña bµi to¸n 16 sü quan lµ Ab Dd Ba Cc Bc Ca Ad Db Cd Bb Dc Aa Da Ac Cb Bd  Mét lêi gi¶i trong trêng hîp n =5 lµ Aa Bb Cc Dd Ee Cd De Ea Ab Bc Eb Ac Bd Ce Da Be Ca Db Ec Ad Dc Ed Ae Ba Cb Toán rời rạc 6
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. Toán rời rạc 7
Bài toán về 36 sĩ quan  Tëngchõ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 Toán rời rạc Geometry), 8
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 Toán rời rạc 9
Bài toán 4 màu  Con sè 4 kh«ng ph¶i lµ ngÉu nhiªn. Ngêi ta ®· chøng minh ®îc r»ng mäi b¶n ®å ®Òu ® îc t« víi sè mÇu lín h¬n 4, cßn víi sè mÇu Ýt h¬n 4 th× kh«ng t« ®îc. Ch¼ng h¹n b¶n ®å gåm 4 níc ë h×nh díi kh«ng thÓ t« ®îc víi sè mÇu Ýt h¬n 4. A B C D Fall 2006 Toán rời rạc 10
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), 711712. Fall 2006 Toán rời rạc 11
Bài toán 4 màu  Trong ngôn ngữ toán học, bài toán 4 màu được phát biểu dưới dạng bài toán tô màu đồ thị phẳng.  Việc giải quyết Bài toán 4 màu đóng góp phần quan trọng vào việc phát triển lý thuyết đồ thị.  Bài toán tô màu đồ thị có nhiều ứng dụng thực tế quan trọng. Fall 2006 Toán rời rạc 12
Hình lục giác thần bí  N¨m 1910 Clifford Adams ®Ò ra bµi to¸n h×nh lôc gi¸c thÇn bÝ sau: trªn 19 « lôc gi¸c (xem h×nh vÏ ë díi) h·y ®iÒn vµo c¸c sè tõ 1 ®Õn 19 sao cho tæng theo 6 h íng cña lôc gi¸c lµ b»ng nhau (vµ ®Òu b»ng 38). Fall 2006 Toán rời rạc 13
Hình lục giác thần bí  Sau 47 n¨m trêi kiªn nhÉn cuèi cïng «ng ta ®· t×m ®îc lêi gi¶i.  Sau ®ã v× s¬ ý ®¸nh mÊt b¶n th¶o «ng ta ®· tèn thªm 5 n¨m ®Ó kh«i phôc l¹i. N¨m 1962 Adams ®· c«ng bè lêi gi¶i ®ã.  ThËt kh«ng thÓ ngê lµ ®ã lµ lêi gi¶i duy nhÊt (nÕu kh«ng tÝnh ®Õn c¸c lêi gi¶i sai kh¸c nhau bëi phÐp biÕn h×nh ®¬n gi¶n). Fall 2006 Toán rời rạc 14
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 ) = 1f (4f (...( 4 2f (4x ))...)) 43 f (40) = 40/ 2 = 20 n l� n g� i h� mf f (20) = 20/ 2 = 10 f (10) = 10/ 2 = 5 f (5) = 3* 5+ 1 = 16 • là bằng 1. f (16) = 16/ 2 = 8 f (8) = 8/ 2 = 4 f (4) = 4/ 2 = 2 f (2) = 2/1 = 1 Fall 2006 Toán rời rạc 15
Giả thuyết 3x + 1  Giả thuyết 3x+1: Đoạn chương trình sau đây luôn kết thúc với mọi số nguyên dương x: repeat if x mod 2 = 0 then x:= x div 2 else x:= 3*x +1 until x=1;  Paul Erdös commented concerning the intractability of the 3x+1 problem: ``Mathematics is not yet ready for such problems.''  Đã chứng minh với mọi x 5.6*1013 Fall 2006 Toán rời rạc 16
Một số vấn đề mở Open problems  Goldbach’s Conjecture • Mỗi số nguyên n >2 đều là tổng của 2 số nguyên tố • Đã chỉ ra là đúng với mọi n đến tận 4*1014 • Nhiều người cho rằng giả thuyết là đúng  Cặp số nguyên tố sinh đôi (Twin prime conjecture) • Có vô số cặp số nguyên tố sinh đôi (nghĩa là chỉ chênh lệch nhau 2) • Cặp sinh đôi lớn nhất: 318,032,361*2107,001±1 • Số này có 32,220 chữ số! • Cũng được cho rằng là đúng  Không tồn tại số hoàn hảo lẻ (Odd perfect number)  Nếu bạn giải quyết được một trong những vấn đề này .... Fall 2006 Toán rời rạc 17
ẢO GIÁC Fall 2006 Toán rời rạc 18
Fractals Fall 2006 Toán rời rạc 19
A bit of humor: Computer terminology Fall 2006 Toán rời rạc 20