Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2008 Fall 2006 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 Fall 2006 Toán rời rạc 2 Chương 2. BÀI TOÁN TỒN TẠI 1. 2. 3. 4. Fall 2006 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 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. Fall 2006 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 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