Trang 2
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 2
Nội dung tài liệu
Trang 3
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 Toán rời rạc 3
Trang 4
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 4
Trang 5
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 5
Trang 6
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 6
Trang 7
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 Toán rời rạc 7
Trang 8
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 Toán rời rạc 8
Trang 9
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
Trang 10
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
Trang 11
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 11
Trang 12
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
Trang 13
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
Trang 14
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
Trang 15
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 n( )x = f( (...( ( ))...))f f x f(13) = 3* 13+1= 40 f(40) = 40 / 2= 20 nlÇn gäi hμmf f(20) = 20 / 2=10 • là bằng 1. f(10) =10 / 2= 5 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 Toán rời rạc 15
Trang 16
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
Trang 17
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
Hiển thị 17 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!