Đang chuẩn bị liên kết để tải về tài liệu:
Bài giảng Toán rời rạc (Phần I: Lý thuyết tổ hợp): Chương 2 - Nguyễn Đức Nghĩa

Chương 2 - Bài toán tồn tại. Nội dung chính được trình bày trong chương này gồm có: 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. . | Fall 2006 Toán rời rạc Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2008 Fall 2006 Toán rời rạc 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 Chương 2. BÀI TOÁN TỒN TẠI 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 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. 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 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 Bài toán về 36 sĩ quan Sử . | Fall 2006 Toán rời rạc Phần thứ nhất LÝ THUYẾT TỔ HỢP Combinatorial Theory Fall 2008 Fall 2006 Toán rời rạc 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 Chương 2. BÀI TOÁN TỒN TẠI 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 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. 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