Nội dung

Mét sè chuyªn ®Ò vÒ tæ hîp dµnh cho häc sinh cã n¨ng khiÕu to¸n bËc trung häc phæ th«ng Môc lôc Lêi c¶m ¬n 1 Më ®Çu 3 Ch­¬ng 1. KiÕn thøc c¬ b¶n 6 1.1. Quy t¾c céng vµ quy t¾c nh©n . . . . . . . . . . . . . . . . . 6 1.2. Ho¸n vÞ vµ tæ hîp . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3. Nguyªn lý chuång chim bå c©u (Nguyªn lý Dirichlet) . . . . 9 1.4. Ho¸n vÞ vµ tæ hîp tæng qu¸t . . . . . . . . . . . . . . . . . . 11 1.5. C«ng thøc bao hµm vµ lo¹i trõ Ch­¬ng 2. . . . . . . . . . . . . . . . . . 14 Mét sè chuyªn ®Ò vÒ tæ hîp dµnh cho häc sinh cã n¨ng khiÕu to¸n bËc trung häc phæ th«ng 17 2.1. Chuyªn ®Ò 1: Quy t¾c céng vµ quy t¾c nh©n . . . . . . . . . . 18 2.2. Chuyªn ®Ò 2: Ho¸n vÞ vµ tæ hîp 2.3. Chuyªn ®Ò 3: Nguyªn lý chuång chim bå c©u . . . . . . . . . 29 2.4. Chuyªn ®Ò 4: C¸c sè Ramsey . . . . . . . . . . . . . . . . . . 32 2.5. Chuyªn ®Ò 5: C¸c sè Catalan . . . . . . . . . . . . . . . . . . 38 2.6. Chuyªn ®Ò 6: C¸c sè Stirling . . . . . . . . . . . . . . . . . . 41 2.7. Chuyªn ®Ò 7: Ho¸n vÞ vµ tæ hîp tæng qu¸t . . . . . . . . . . . 47 2.8. Chuyªn ®Ò 8: Nguyªn lý bao hµm vµ lo¹i trõ 2.9. Chuyªn ®Ò 9: Nh÷ng sù x¸o trén vµ nh÷ng sù s¾p ®Æt tr­íc . . 54 2.10. Chuyªn ®Ò 10: §¹i l­îng bÊt biÕn Ch­¬ng 3. Mét sè bµi tËp ®Ò nghÞ . . . . . . . . . . . . . . . . 23 . . . . . . . . . 50 . . . . . . . . . . . . . . . 57 60 2 Më ®Çu Cã thÓ nãi t­ duy vÒ tæ hîp ra ®êi tõ rÊt sím. Vµo thêi nhµ Chu, ng­êi ta ®· biÕt ®Õn c¸c h×nh vÏ cã liªn quan ®Õn nh÷ng h×nh vu«ng thÇn bÝ. Thêi cæ Hy l¹p, nhµ triÕt häc Kxenokrat, sèng ë thÕ kû thø 4 tr­íc c«ng nguyªn, ®· biÕt tÝnh sè c¸c tõ kh¸c nhau lËp tõ mét b¶ng ch÷ c¸i cho tr­íc. Nhµ to¸n häc Pitago vµ c¸c häc trß cña «ng ®· t×m ra nhiÒu con sè cã tÝnh chÊt ®Æc biÖt. ViÖc t×m ra ®­îc c¸c sè nh­ vËy ®ßi hái ph¶i cã mét nghÖ thuËt tæ hîp nhÊt ®Þnh. Tuy nhiªn, cã thÓ nãi r»ng, lý thuyÕt tæ hîp ®­îc h×nh thµnh nh­ mét ngµnh to¸n häc míi vµ qu·ng thÕ kû 17 b»ng mét lo¹t c¸c c«ng tr×nh nghiªn cøu nghiªm tóc cña c¸c nhµ to¸n häc xuÊt s¾c nh­ Pascal, Fermat, Leibnitz, Euler...MÆc dï vËy, trong suèt hai thÕ kû r­ìi, tæ hîp kh«ng cã vai trß nhiÒu trong viÖc nghiªn cøu tù nhiªn. §Õn nay, víi sù hç trî ®¾c lùc cña m¸y tÝnh , tæ hîp ®· chuyÓn sang lÜnh vùc to¸n øng dông víi sù ph¸t triÓn m¹nh mÏ, cã nhiÒu kÕt qu¶ cã Ých cho con ng­êi. NhËn thøc ®­îc vai trß cña lý thuyÕt tæ hîp ®èi víi ®êi sèng hiÖn ®¹i. Lý thuyÕt tæ hîp ®· ®­îc ®­a vµo ch­¬ng tr×nh häc phæ th«ng vµ chiÕm mét phÇn trong c¸c kú thi to¸n quèc gia vµ quèc tÕ. Tuy nhiªn, ë n­íc ta, tµi liÖu viÕt vÒ tæ hîp ch­a nhiÒu. Do ®ã, b¶n luËn v¨n nµy sÏ cung cÊp thªm mét tµi liÖu vÒ tæ hîp cho häc sinh phæ th«ng; ®Æc biÖt lµ dµnh cho nh÷ng em häc sinh cã n¨ng khiÕu m«n to¸n. Chóng t«i hi väng luËn v¨n nµy sÏ ®¸p øng ®­îc phÇn nµo lßng yªu thÝch kh¸m ph¸ to¸n häc cña c¸c em. §ång thêi ®©y còng lµ mét tµi liÖu ®Ó c¸c ®ång nghiÖp tham kh¶o. LuËn v¨n gåm ba ch­¬ng. Ch­¬ng mét chóng t«i tr×nh bµy mét sè kiÕn 4 thøc c¬ b¶n cña tæ hîp theo mét l«gic kh¸c so víi s¸ch phæ th«ng nh»m g©y sù míi l¹ cho häc sinh. Ch­¬ng hai lµ träng t©m cña luËn v¨n. Trong ch­¬ng nµy, häc sinh ®­îc t×m hiÓu m­êi chuyªn ®Ò: Chuyªn ®Ò 1: Quy t¾c céng vµ quy t¾c nh©n. Chuyªn ®Ò 2: Ho¸n vÞ vµ tæ hîp. Chuyªn ®Ò 3: Nguyªn lý chuång chim bå c©u. Chuyªn ®Ò 4: C¸c sè Ramsey. Chuyªn ®Ò 5: C¸c sè Catalan. Chuyªn ®Ò 6: C¸c sè Stirling. Chuyªn ®Ò 7: Ho¸n vÞ vµ tæ hîp tæng qu¸t. Chuyªn ®Ò 8: Nguyªn lý bao hµm vµ lo¹i trõ. Chuyªn ®Ò 9: Nh÷ng sù x¸o trén vµ nh÷ng sù s¾p ®Æt tr­íc. Chuyªn ®Ò 10: §¹i l­îng bÊt biÕn. Trong mçi chuyªn ®Ò, c¸c bµi tËp th­êng ®­îc dÉn d¾t theo nh÷ng chñ ®Ò nhÊt ®Þnh. Qua ®ã häc sinh tù t×m thÊy cho m×nh nh÷ng kiÕn thøc liªn quan ®Õn chñ ®Ò ®­îc nªu. §ång thêi, mçi bµi ®Òu cã lêi gi¶i chi tiÕt, ng¾n gän, ®Çy s¸ng t¹o vµ bÊt ngê. C¸c lêi gi¶i nµy Ýt gÆp trong c¸c tµi liÖu vÒ tæ hîp cã trªn thÞ tr­êng. T¸c gi¶ hi väng chÝnh ®iÒu nµy kÝch thÝch sù ham hiÓu biÕt, lßng say mª cña c¸c häc sinh cã n¨ng khiÕu to¸n. Ch­¬ng ba cã néi dung lµ nh÷ng bµi tËp ®Ò nghÞ ®­îc chän lùa kÜ l­ìng; nh»m gióp c¸c em vËn dông nh÷ng kiÕn thøc thu ®­îc tõ hai ch­¬ng tr­íc ®Ó n©ng cao kü n¨ng gi¶i to¸n tæ hîp cña m×nh. Sau mét thêi gian nghiªn cøu luËn v¨n ®· ®­îc hoµn thµnh. Tuy nhiªn sÏ kh«ng tr¸nh khái nhiÒu sai sãt. KÝnh mong sù gãp ý cña quý thÇy c«, c¸c b¹n ®ång nghiÖp vµ c¸c em häc sinh. Chóng t«i xin ch©n thµnh c¶m ¬n! 5 Ch­¬ng 1 KiÕn thøc c¬ b¶n 1.1. Quy t¾c céng vµ quy t¾c nh©n Quy t¾c céng: NÕu Ei (i = 1, ..., k) lµ k sù kiÖn tho¶ m·n: (i) Kh«ng cã hai sù kiÖn nµo trong sè chóng x¶y ra ®ång thêi (ii) Ei cã thÓ x¶y ra theo th× mét trong k ni sù kiÖn cã thÓ x¶y ra theo Mét líp häc cã VÝ dô 1.1.1 18 + 12 = 30 c¸ch 18 (n1 + n2 + ... + nk ) c¸ch. häc sinh nam vµ 12 häc sinh n÷ th× cã c¸ch chän mét häc sinh (kh«ng kÓ nam, n÷) lµm ng­êi ®¹i diÖn cho líp. VÝ dô 1.1.2 Gi¶ thiÕt E lµ sù kiÖn chän c¸c sè nguyªn tè nhá h¬n lµ sù kiÖn chän c¸c sè tù nhiªn ch½n nhá h¬n Th×: E cã 4 c¸ch x¶y ra, F cã 4 tè ch½n nªn mét trong hai sù kiÖn 10. c¸ch x¶y ra. Nh­ng v× E hoÆc F 10 vµ F 2 lµ mét sè nguyªn cã thÓ x¶y ra theo 4+4−1 = 7 c¸ch. Quy t¾c nh©n: n1 c¸ch; E2 NÕu cã thÓ x¶y ra theo ra nh­ thÕ nµo); E1 vµ E2 Ei (i = 1, ..., k) E3 n2 lµ k sù kiÖn vµ E1 c¸ch (kh«ng phô thuéc ®Õn viÖc cã thÓ x¶y ra theo n3 VÝ dô 1.1.3 nk − 1) sù kiÖn tr­íc x¶y ra nh­ thÕ nµo), th× k ra ®ång thêi theo n1 .n2 .n3 ...nk Mét gi¸ s¸ch cã E1 x¶y c¸ch (kh«ng phô thuéc ®Õn viÖc x¶y ra nh­ thÕ nµo),...,Ek cã thÓ x¶y ra theo thuéc ®Õn (k cã thÓ x¶y ra theo c¸ch (kh«ng phô sù kiÖn cã thÓ x¶y c¸ch. 6 quyÓn s¸ch tiÕng Anh ®«i mét kh¸c nhau; 8 quyÓn s¸ch tiÕng Ph¸p ®«i mét kh¸c nhau vµ 10 quyÓn s¸ch tiÕng §øc ®«i mét kh¸c nhau. (i) Cã 6.8.10 = 480 c¸ch chän lÊy 3 quyÓn s¸ch trong ®ã mçi quyÓn mét 6 thø tiÕng. (ii) Cã 6 + 8 + 10 = 24 c¸ch chän lÊy 1 quyÓn s¸ch bÊt kú trong sè c¸c quyÓn s¸ch nãi trªn. NÕu mét bµi thi tr¾c nghiÖm cã VÝ dô 1.1.4 8 c©u hái mçi c©u hái cã 3 ph­¬ng ¸n tr¶ lêi (mét ph­¬ng ¸n ®óng vµ hai ph­¬ng ¸n sai). VËy sè c¸ch chän c©u tr¶ lêi cña tÊt c¶ 1.2. Ho¸n vÞ vµ tæ hîp Cho X §Þnh nghÜa 1.2.1 phÇn tö vµ r lµ mét sè nguyªn kh«ng n. r-ho¸n vÞ cña X Mét lµ mét bé s¾p thø tù gåm r phÇn tö n phÇn tö cña X . Mét Sè n lµ mét tËp hîp bao gåm ©m nhá h¬n hoÆc b»ng tõ 8 c©u hái trªn lµ 38 = 6561 c¸ch. n-ho¸n vÞ cña X ®­îc gäi lµ mét ho¸n vÞ cña X. r-ho¸n vÞ cña mét tËp hîp n phÇn tö ®­îc ký hiÖu lµ P (n, r). VÝ dô 1.2.2 {2, 3, 4} vµ {2, 4, 3} lµ hai 3-ho¸n vÞ kh¸c nhau cña X = {1, 2, 3, 4, 5}. §Þnh nghÜa 1.2.3 Mét r-tæ hîp cña X lµ mét tËp con gåm r phÇn tö cña X . r-tæ hîp cña mét tËp hîp n phÇn tö ®­îc ký hiÖu lµ C(n, r). n! §Þnh lý 1.2.4 (i) P (n, r) = (n − r)! P (n, r) n! (ii) C(n, r) = = = C(n, n − r) r! r!(n − r)! Sè ë ®©y chóng ta ®­a ra hµm giai thõa: m! ≡ (1).(2)...(m) Chøng minh: tiªn trong r (i) Cã vÞ trÝ; cã n vµ 0! ≡ 1 c¸ch chän mét phÇn tö bÊt kú cña (n − 1) c¸ch X chän mét phÇn tö tõ nhãm tö cßn l¹i ®Ó chiÕm vÞ trÝ thø hai trong sè r vµo vÞ trÝ ®Çu (n − 1) phÇn vÞ trÝ. Chó ý r»ng sè c¸ch chän phÇn tö chiÕm vÞ trÝ thø hai kh«ng phô thuéc vµo c¸ch chän phÇn tö chiÕm ë vÞ trÝ thø nhÊt nh­ thÕ nµo. 7 Do ®ã theo quy t¾c nh©n, hai vÞ trÝ ®Çu tiªn cã thÓ lÊp ®Çy bëi r c¸ch...vµ tÊt c¶ n(n − 1) vÞ trÝ cã thÓ lÊp ®Çy bëi: n! (n − r)! P (n, r) = n(n − 1)...(n − r + 1) = c¸ch. (ii) §Ó ®¸nh gi¸ C(n, r), chó ý r»ng mét r-ho¸n vÞ cña tËp hîp n phÇn tö X r-tËp con nµo ®ã cña X . lµ ho¸n vÞ cña mét H¬n n÷a, nh÷ng r-tËp con ph©n biÖt sinh ra r-tæ hîp ph©n biÖt. Do ®ã, b»ng quy t¾c céng ta cã: P (n, r) = P (r, r) + P (r, r) + ... + P (r, r) Sè c¸c sè h¹ng ë vÕ ph¶i lµ sè c¸c r-tËp con cña X tøc lµ C(n, r). Do ®ã ta cã: P (n, r) = C(n, r)P (r, r) = C(n, r)r! Mçi r-tËp con cña X (n − r)-tËp con. cã mét tËp con bï duy nhÊt lµ Tõ ®ã ta cã mét quan hÖ quan träng lµ: C(n, r) = C(n, n − r) §Æc biÖt, sè ho¸n vÞ cña n phÇn tö lµ: P (n, n) = n! NhËn xÐt 1.2.5 hîp cã r- ho¸n vÞ cña mét tËp cña n phÇn tö, mét r- tæ Trong ch­¬ng tr×nh phæ th«ng, mét n phÇn tö ®­îc gäi lµ mét chØnh hîp chËp r hîp cña mét tËp hîp cã n phÇn tö ®­îc gäi lµ mét tæ hîp chËp r cña n phÇn tö ®ã. VÝ dô 1.2.6 Mét c©u l¹c bé gåm 9 häc sinh khèi 10. 4 häc sinh khèi 11; 3 12 häc sinh khèi 12; 10 häc sinh khèi 11; CÇn lËp ra mét ban ®¹i diÖn gåm: häc sinh khèi 10. 8 VËy ta cã: 4 häc sinh khèi C(12, 4) = 12; 12! = 495 4!8! c¸ch chän 4 häc sinh khèi 12; C(10, 4) = 210 c¸ch chän 4 häc sinh khèi 11; C(9, 3) = 84 c¸ch chän 3 häc sinh khèi chän ra ban ®¹i diÖn trªn lµ: 1.3. 10. B»ng quy t¾c nh©n, sè c¸ch ®Ó 495.210.84 = 8731800 c¸ch. Nguyªn lý chuång chim bå c©u (Nguyªn lý Dirichlet) Mét sè kÕt qu¶ s©u s¾c cña lý thuyÕt tæ hîp xuÊt ph¸t tõ mét mÖnh ®Ò ®¬n gi¶n: NÕu n chuång chim bå c©u lµ n¬i tró Èn cña Ýt nhÊt (n + 1) con chim bå c©u th× cã Ýt nhÊt mét chuång chim chøa tõ hai con chim bå c©u trë lªn. VÝ dô 1.3.1 Gi¶ thiÕt r»ng cã nhiÒu chiÕc tÊt ®á, nhiÒu chiÕc tÊt tr¾ng vµ nhiÒu chiÕc tÊt xanh ë trong hép. Hái ph¶i lÊy tõ hép ®ã ra Ýt nhÊt bao nhiªu chiÕc tÊt (khi lÊy kh«ng nh×n vµo bªn trong) ®Ó ch¾c ch¾n ®­îc 2 chiÕc cïng mµu. Gi¶i Mçi mét mµu ®­îc coi nh­ mét chuång chim bå c©u vËy lÊy n = 3. Do ®ã, nÕu n + 1 = 4 chiÕc tÊt th× Ýt nhÊt cã hai chiÕc tÊt cïng mµu. Mét tæng qu¸t ®¬n gi¶n cña nguyªn lý chuång chim bå c©u nh­ sau: NÕu k n chuång chim bå c©u lµ n¬i tró Èn cña kn + 1 con chim bå c©u víi lµ mét sè nguyªn d­¬ng th× Ýt nhÊt cã mét chuång chøa tõ k + 1 con chim bå c©u trë lªn. VÝ dô 1.3.2 vÉn cã T­¬ng tù nh­ vÝ dô 1.3.1 nÕu cÇn lÊy 6 chiÕc tÊt cïng mµu th× ta n = 3 vµ ®Ó ®¶m b¶o r»ng mét (hay nhiÒu h¬n) trong sè c¸c chuång ®ã chøa k+1 = 6 (hoÆc nhiÒu h¬n) con chim bå c©u th× chóng ta ph¶i lÊy kn + 1 = 16 con chim. Do ®ã ®¸p sè lµ 16 chiÕc tÊt. VÝ dô 1.3.3 Mét tñ chøa chiÕc mµu tr¾ng vµ 20 chiÕc ¸o s¬ mi trong ®ã cã 4 chiÕc mµu ®á; 7 9 chiÕc mµu xanh. Hái ph¶i lÊy ra Ýt nhÊt bao nhiªu chiÕc ¸o (khi lÊy kh«ng ®­îc nh×n vµo tñ) ®Ó lÊy ®­îc 9 r = 4, 5, 6, 7, 8, 9 chiÕc ¸o cïng mµu? Gi¶i ∗) Tr­êng hîp 1: r = 4 = k + 1. Suy ra k = 3. Cã 3 mµu nªn n = 3. Do ®ã, cÇn ph¶i lÊy ra Ýt nhÊt kn + 1 = 3.3 + 1 = 10 chiÕc ¸o s¬ mi. ∗) Tr­êng hîp 2: r = 5 = k + 1. Suy ra k = 4. Ph©n tÝch ®¬n gi¶n nhÊt, chóng ta t­ëng t­îng r»ng nh÷ng chiÕc ¸o ®­îc lÊy ra tõ tñ mét c¸ch tuÇn tù. T×nh huèng "l·ng phÝ" sù di chuyÓn nhÊt lµ 4 chiÕc ¸o lÊy ta ®Çu tiªn cïng mµu ®á. Do ®ã c¸c chiÕc cßn l¹i ph¶i lÊy ra cã mµu xanh hoÆc mµu tr¾ng. §Ó ch¾c ch¾n r=5 chiÕc ¸o lÊy ra cã cïng mµu th× nhÊt cã mµu xanh hoÆc mµu tr¾ng cÇn lÊy ra lµ: n = 2. Sè l­îng ¸o Ýt kn + 1 = 4.2 + 1 = 9 (theo nguyªn lý chuång chim bå c©u). VËy cÇn lÊy ra Ýt nhÊt 4 + 9 = 13 chiÕc ¸o. ∗) Tr­êng hîp 3: r = 6 = k + 1. Suy ra k = 5. T­¬ng tù nh­ tr­êng hîp 2, kÕt qu¶ lµ 4 + kn + 1 = 4 + 5.2 + 1 = 15 chiÕc ¸o cÇn ph¶i lÊy ra. ∗) Tr­êng hîp 4: r = 7 = k + 1. Suy ra k = 6. T­¬ng tù kÕt qu¶ lµ 4 + kn + 1 = 4 + 6.2 + 1 = 17 chiÕc ¸o cÇn ph¶i lÊy ra. ∗) Tr­êng hîp 5: r = 8 = k + 1. Suy ra k = 7. B©y giê nÕu lÊy ra nh÷ng chiÕc ¸o mµu ®á hoÆc mµu tr¾ng th× ®Òu v« gi¸ trÞ. Do ®ã sè chiÕc ¸o cÇn lÊy ra lµ: ∗) 4 + 7 + kn + 1 = 4 + 7 + 7.1 + 1 = 19 chiÕc. Tr­êng hîp 6: r = 9 = k + 1. T­¬ng tù nh­ tr­êng hîp 5 ta cã kÕt qu¶: 4 + 7 + kn + 1 = 4 + 7 + 8.1. + 1 = 20 chiÕc ¸o cÇn ph¶i lÊy ra. Cho S lµ mét tËp hîp, t¹o thµnh bëi ®èi t­îng cã dÊu hiÖu t­îng cã dÊu hiÖu tËp con gåm vr n. 2; x3 ≥ x2 KÝ hiÖu vr x1 ®èi t­îng cã dÊu hiÖu ®èi t­îng cã dÊu hiÖu 1; x2 ≥ x1 3,..., xn ≥ xn−1 ®èi lµ sè nguyªn nhá nhÊt tho¶ m·n tÊt c¶ c¸c phÇn tö cña S mµ mçi tËp con chøa Ýt nhÊt 10 r ®èi t­îng cã cïng mét dÊu hiÖu. Khi ®ã:    n(r − 1) + 1,       (n − 1)(r − 1) + 1 + x1 ,    vr = (n − 2)(r − 1) + 1 + x1 + x2 ,      ..........................................      (1)(r − 1) + 1 + x + x + ... + x , 1 2 n−1 §Þnh nghÜa 1.3.4 NÕu x r ≤ x1 x1 < r ≤ x2 x2 < r ≤ x 3 xn−1 < r ≤ xn lµ mét sè thùc th× phÇn nguyªn cña lµ sè nguyªn lín nhÊt nhá h¬n hoÆc b»ng kÝ hiÖu [x] x. n chuång th× Ýt nhÊt mét h (m − 1) i chuång chøa tõ p + 1 con trë lªn víi p = . n Chøng minh: Gi¶ sö ng­îc l¹i, tÊt c¸c chuång ®Òu chøa nhiÒu nhÊt p con m − 1 = m−1 < m chim. VËy sè chim bå c©u nhá h¬n hoÆc b»ng np ≤ n n §Þnh lý 1.3.5 NÕu nhèt m x, con chim bå c©u vµo (m©u thuÉn). VÝ dô 1.3.6 cã p= 1.4. h 25 i 7 Gi¶ sö cã 26 sinh viªn (m = 26) vµ 7 chiÕc « t« ®Ó chë hä. VËy = 3. Do ®ã cã Ýt nhÊt mét chiÕc « t« chë tõ 4 sinh viªn trë lªn. Ho¸n vÞ vµ tæ hîp tæng qu¸t §Þnh nghÜa 1.4.1 NÕu X lµ mét ®a tËp gåm ph©n biÖt), bÊt kú mét sù s¾p xÕp nµo cña mét r-ho¸n vÞ tæng qu¸t cña X tæng qu¸t cña X ). VÝ dô 1.4.2 §a tËp (nÕu n vËt (kh«ng cÇn thiÕt ph¶i r ≤ n vËt tõ ®a tËp X ®­îc gäi lµ r = n chóng ta gäi ®¬n gi¶n lµ ho¸n vÞ X = {A, A, B, B, B, C, C} cã AABCBBC lµ mét ho¸n vÞ tæng qu¸t cña X. ni (i = 1, 2, ..., k), r vµ n lµ k + 2 sè nguyªn d­¬ng tho¶ m·n n1 + n2 + P (n, r) ... + nk = r ≤ n ta ®Æt P (n; n1 , n2 , ..., nk ) ≡ n1 !n2 !...nk ! NÕu 11