Một số chuyên đề về tổ hợp dành cho học sinh giỏi Toán

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 Tõ NhËn xÐt 1.4.3 P (n, r) = P (n, n) (n − r)! ta cã: P (n; n1 , n2 , ..., nk ) = P (n; n1 , n2 , ..., nk , n − r) VÝ dô 1.4.4 P (18, 3 + 4 + 6) P (18, 13) 18! = = 3!4!6! 3!4!6! 3!4!6!5! P (18; 3 + 4 + 6 + 5) = 3!4!6!5! = P (18; 3, 4, 6, 5) Ta nhËn ®­îc c«ng thøc cho sè ho¸n P (18; 3, 4, 6) = vÞ cña mét ®a tËp bëi ®Þnh lý sau: Sè c¸c ho¸n vÞ tæng qu¸t cña mét ®a tËp §Þnh lý 1.4.5 gièng nhau cã cïng dÊu hiÖu i (i = 1, 2, ..., k) lµ X bao gåm P (n; n1 , n2 , ..., nk ); ni vËt ë ®©y n = n1 + n2 + ... + nk . Chøng minh: cña X Gäi p lµ ph©n biÖt th× vÞ t¹o bëi n1 lµ tæng sè c¸c ho¸n vÞ tæng qu¸t cña n1 ho¸n vÞ t¨ng lªn NÕu n vËt P (n, n) lµ sè ho¸n vÞ cña X . Khi ®ã, so s¸nh sè ho¸n vËt ph©n biÖt cã dÊu hiÖu ho¸n vÞ t¹o bëi X. 1 vµ n − n1 vËt gièng nhau cã dÊu hiÖu phÇn tö cßn l¹i víi sè 1 vµ n − n1 vËt cßn l¹i th× sè n1 ! lÇn. §iÒu nµy còng ®óng ®èi víi nh÷ng vËt cã dÊu hiÖu i (i = 2, 3, ..., k). Do ®ã theo quy t¾c nh©n, ®Æt q = n1 !n2 !...nk ! th× ta cã: p= VÝ dô 1.4.6 X P (n, n) = P (n; n1 , n2 , ..., nk ) q X = {C, E, E, I, M, M, O, T, T } th× sè ho¸n vÞ tæng qu¸t cña lµ: P (9, 1, 2, 1, 2, 1, 2) = NhËn xÐt 1.4.7 9! = 45360 1!2!1!2!1!2! Trong ch­¬ng tr×nh phæ th«ng, ho¸n vÞ tæng qu¸t gäi lµ ho¸n vÞ lÆp. VÝ dô 1.4.8 Hái cã bao nhiªu c¸ch xÕp hÕt 4 qu¶ bãng mµu ®á gièng nhau; 3 qu¶ bãng mµu tr¾ng gièng nhau; 5 qu¶ bãng mµu xanh gièng nhau, vµo 18 vÞ trÝ th¼ng hµng cho tr­íc (mçi vÞ trÝ cã nhiÒu nhÊt Gi¶i 12 1 bãng). Sè c¸ch xÕp lµ: P (18; 4, 3, 5) = Gi¶ sö r»ng r X n lµ tËp hîp 18! = 514594080 4!3!5!6! S phÇn tö vµ lµ mét tËp con bÊt kú cña phÇn tö. Mét sù ph©n chia cã quan t©m ®Õn thø tù cña r-tæ hîp tæng qu¸t cña X. NÕu r = n, S X cã ®­îc gäi lµ mét chóng ta cã kh¸i niÖm tæ hîp tæng qu¸t cña X. Sè r-tæ « chøa thø ®ã hîp tæng qu¸t cña 2.;...; nk X cã n1 phÇn tö ë « chøa thø phÇn tö ë « chøa thø n1 + n2 + ... + nk = r k kÝ hiÖu 1; n2 phÇn tö ë C(n; n1 , n2 , ..., nk ) trong lµ: C(n; n1 , n2 , ..., nk ) = C(n, n1 )C(n − n1 , n2 )....C(n − n1 − n2 − ... − nk−1 ) = P (n, r) n! = n1 !n2 !...nk !(n − r)! n1 !n2 !...nk ! (1.1) C(n; n1 , n2 , ..., nk ) = P (n; n1 , n2 , ..., nk ) trong ®ã n1 + n2 + §Þnh lý 1.4.9 ... + nk = r ≤ n VÝ dô 1.4.10 Cã 17 sinh viªn muèn ®i dù tiÖc vµ cã 5 « t« ®Õn ®ãn hä. Tuy nhiªn sè chç ngåi cßn trèng trªn cho 5 xe lµ 4, 4, 2, 5 vµ 1. Do ®ã chØ ®ñ chç ngåi 16 sinh viªn. VËy sè c¸ch chë 16 sinh viªn trong 17 sinh viªn trªn lµ: C(17; 4, 4, 2, 5, 1) = HÖ qu¶ 1.4.11 17! 4!4!2!5!1!1! Sè c¸ch ph©n chia (kh«ng quan t©m ®Õn thø tù) cña mét tËp hîp cã lùc l­îng n thµnh p1 tËp con cã lùc l­îng n1 , p2 tËp con cã lùc l­îng n2 ,...,pk tËp con cã lùc l­îng nk (trong ®ã c¸c ni (i = 1, 2, ..., k) lµ ph©n biÖt k P vµ pi ni = n) ®­îc cho bëi c«ng thøc: i=1 p sè h¹ng p sè h¹ng p sè h¹ng z 1 }| { z 2 }| { z k }| { C(n; n1 , ...n1 , n2 , ...n2 , ..., nk , ...nk ) n! = p1 !p2 !...pk ! [p1 !(n1 !)p1 ][p2 !(n2 !)p2 ]...[pk !(nk !)pk ] 13 Gi¶ sö cã 12 sinh viªn tham gia ch­¬ng tr×nh "TiÕp søc mïa VÝ dô 1.4.12 thi '' . Hä cÇn cã mÆt t¹i mét bÕn xe A. (i) Sè c¸ch ph©n c«ng 12 sinh viªn nµy lµm viÖc vµo ba buæi s¸ng, chiÒu, tèi; mçi buæi 4 ng­êi kh¸c nhau lµ C(12; 4, 4, 4) (ii) Sè c¸ch ph©n chia 12 sinh viªn nµy thµnh ba nhãm, mçi nhãm cã 4 ng­êi kh¸c nhau lµ (ii) C(12; 4, 4, 4)/3! Sè c¸ch ph©n chia 12 sinh viªn nµy ®øng vµo 4 cöa (mçi cöa mét sinh C(12; 4, 4, 4) .4! 3! viªn) lµ NhËn xÐt 1.4.13 Ngoµi ra, trong ch­¬ng tr×nh phæ th«ng chóng ta cßn sö dông ®Õn hai kh¸i niÖm chØnh hîp lÆp vµ tæ hîp lÆp: ChØnh hîp lÆp: Cho tËp hîp X gåm n phÇn tö. Mçi d·y cã ®é dµi r gåm c¸c phÇn tö cña tËp X, mµ mçi phÇn tö cã thÓ lÆp l¹i nhiÒu lÇn vµ ®­îc s¾p xÕp theo mét thø tù nhÊt ®Þnh ®­îc gäi lµ mét chØnh hîp lÆp chËp phÇn tö thuéc tËp X. Sè chØnh hîp lÆp chËp tõ tËp r phÇn tö ®Õn tËp Tæ hîp lÆp: r cña r cña n phÇn tö b»ng sè ¸nh x¹ n phÇn tö vµ b»ng nr . Cho tËp hîp X gåm nhÊt thiÕt ph¶i nhá h¬n n) cña n n phÇn tö. Mét tæ hîp lÆp chËp r (r kh«ng phÇn tö thuéc X lµ mét bé gåm r phÇn tö, mµ mçi phÇn tö nµy lµ mét trong nh÷ng phÇn tö cña X. Sè tæ hîp lÆp chËp cña n r n phÇn tö b»ng C(n + r − 1, r). 1.5. C«ng thøc bao hµm vµ lo¹i trõ Sè l­îng phÇn tö cña mét tËp hîp h÷u h¹n A ®­îc kÝ hiÖu lµ n(A) hay | A |. Ta dÔ dµng chøng minh ®­îc r»ng: n(A ∪ B) = n(A) + n(B) − n(A ∩ B) trong ®ã A vµ B lµ c¸c tËp hîp h÷u h¹n. Do ®ã ®Ó tÝnh sè phÇn tö cña A ∪ B , chóng ta céng n(A) vµ n(B) sau ®ã trõ ®i 14 n(A ∩ B) tõ tæng ®ã (chóng ta lo¹i trõ ®i nh÷ng g× lµ chung cña hai tËp hîp). §©y lµ ý t­ëng cña nguyªn lý bao hµm vµ lo¹i trõ. NÕu A lµ mét tËp con cña X A trong X ta ký hiÖu phÇn bï cña lµ A0 . Khi A vµ B lµ hai tËp con cña X th× ta cã ®¼ng thøc sau:  0 n (A ∪ B) = n(X) − n(A ∪ B) = n(X) − [n(A) + n(B) + n(A ∩ B)] ®ã nÕu  Nh­ng (A ∪ B)0 = A0 ∩ B 0 do ®ã: n(A0 ∩ B 0 ) = n(X) − [n(A) + n(B)] + n(A ∩ B) §Þnh nghÜa 1.5.1 nµo ®ã cña NÕu x lµ mét phÇn tö bÊt kú cña X vµ A lµ mét tËp con X , th× phÐp ®Õm cña x trong A b»ng 1 nÕu x ë trong A vµ b»ng 0 nÕu x kh«ng ë trong A. Sieve ®· chøng minh mét ®Þnh lý tæng qu¸t sau: §Þnh lý 1.5.2 (C«ng thøc Sieve.) NÕu mét tËp h÷u h¹n X A1 , A2 , ..., Am lµ nh÷ng tËp con cña th×: n(A01 ∩ A02 ∩ ... ∩ A0m ) = n(X) − S1 + S2 − ... + (−1)m Sm trong ®ã Sk lµ ký hiÖu cña tæng c¸c lùc l­îng cña tÊt c¶ nh÷ng nhau ®­îc t¹o ra tõ k -bé giao m tËp hîp ë trªn. P (S1 = n(A1 ) + n(A2 ) + ... + n(Am ); S2 = n(Ai ∩ Aj ), ....) i,j=1,m i6=j Chøng minh: ®Õm cña x LÊy x lµ mét phÇn tö tuú ý cña tËp hîp X .Ta chØ ra r»ng phÐp cã kÕt qu¶ gièng nhau ë c¶ hai vÕ cña ph­¬ng tr×nh trªn. Chóng ta quan t©m tíi 2 tr­êng hîp: (i) x kh«ng lµ phÇn tö cña bÊt kú tËp hîp nµo trong sè m tËp hîp trªn. (ii) x lµ phÇn tö cña ®óng r tËp hîp trong sè m tËp hîp trªn, r ≥ 1; chóng ta lu«n cã thÓ gi¶ thiÕt lµ A1 , A2 , ..., Ar . Trong tr­êng hîp ®Çu, phÐp ®Õm cña x b»ng 1 ë c¶ hai vÕ cña ph­¬ng tr×nh. Trong tr­êng hîp sau, phÐp ®Õm cña x ë vÕ tr¸i b»ng 0. §èi víi vÕ ph¶i chóng ta cã: Sk = X n(Ai1 ∩ Ai2 ∩ ... ∩ Aik ) 15 (k = 1, 2, ..., m) PhÐp ®Õm cña x ë vÕ ph¶i lµ: 1 − C(r, 1) + C(r, 2) − C(r, 3) + ... + (−1)r C(r, r) = (1 − 1)r = 0 §Þnh lý 1.5.3 Víi ký hiÖu gièng nh­ ®Þnh lý 1.7 n(A1 ∪ A2 ∪ ... ∪ Am ) = S1 − S2 + ... + (−1)m−1 Sm Chøng minh: Ta cã n(A1 ∪ A2 ∪ ... ∪ Am ) = n(X) − n(A01 ∩ A02 ∩ ... ∩ A0m ) suy ra ®iÒu ph¶i chøng minh. 16 Ch­¬ng 2 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 Trong ch­¬ng nµy t¸c gi¶ xin tr×nh bµy 10 vÊ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. 17 2.1. Chuyªn ®Ò 1: Quy t¾c céng vµ quy t¾c nh©n Môc ®Ých cña chuyªn ®Ò lµ dïng hai quy t¾c ®Õm c¬ b¶n t×m hiÓu mét sè tÝnh chÊt vÒ sè palindrome, chuçi nhÞ ph©n, hµm l«gic tù ®èi ngÉu; tõ ®ã dïng lµm c¬ së ®Ó gi¶i mét sè bµi to¸n tæ hîp kh¸c trong c¸c chuyªn ®Ò tiÕp theo. Ngoµi ra, cßn cã mét sè bµi to¸n kh¸c vËn dông hai quy t¾c nµy ®em ®Õn mét lêi gi¶i hay, ®éc ®¸o. Häc sinh cã thÓ t×m thÊy sù thó vÞ qua c¸ch viÕt c¸c sè ë bµi 2.1.5, hay trong c¸c bµi 2.1.9 vµ 2.1.10 thay v× t×m sè c¸ch ph©n tÝch sè nguyªn N c¸ch t×m ra mèi liªn hÖ gi÷a bµi 2.1.7 vµ bµi 2.1.8 thµnh tÝch cña hai sè nguyªn tè cïng nhau ta l¹i ®i t×m sè c¸ch ph©n chia mét tËp hîp t­¬ng øng thµnh hai tËp hîp kh¸c rçng kh«ng giao nhau... §Þnh nghÜa 2.1.1 Mét palindrome lµ mét d·y h÷u h¹n c¸c ký tù mµ ®äc xu«i vµ ®äc ng­îc nh­ nhau (VÝ dô: Bµi to¸n 2.1.2 ABEU EBA). Hái cã bao nhiªu palindrome cã 7 ch÷ sè hoÆc 8 ch÷ sè, biÕt r»ng trong sè ®ã kh«ng cã ch÷ sè nµo xuÊt hiÖn nhiÒu h¬n Gi¶i: Gi¶ sö mét sè palindrome cã ®é dµi quan t©p ®Õn t©m ®Õn 4 hn + 1i 2 4. Do tÝnh ®èi xøng, ta chØ cÇn vÞ trÝ ®Çu tiªn. Cô thÓ, trong bµi nµy ta chØ cÇn quan vÞ trÝ ®Çu. VÞ trÝ ®Çu tiªn ph¶i kh¸c c¸ch chän cho vÞ trÝ thø trÝ thø n. Do ®ã cã 2 lÇn. 2, 8 0 nªn cã c¸ch chän cho vÞ trÝ thø (9).(9).(8).(7) = 4536 9 3, 7 c¸ch chän. Cã 9 c¸ch chän cho vÞ sè palindrome tho¶ m·n yªu cÇu bµi to¸n. §Þnh lÝ 2.1.3 Chøng minh r»ng : "Mét sè palindrome cã ®é dµi ch½n th× chia hÕt cho 11". Chøng minh: (1) Ta thÊy nÕu bá ®i ch÷ sè ®Çu tiªn vµ ch÷ sè cuèi cïng cña mét sè palindrome th× ta l¹i ®­îc mét sè palindrome míi. Do ®ã ta chøng minh (1) theo ph­¬ng ph¸p quy n¹p. Gi¶ sö cho N lµ mét sè palindrome cã ®é dµi +) NÕu k = 1 th× (1) hiÓn nhiªn ®óng. +) NÕu k ≥ 2 ta cã: 18 2k . N = a2k−1 .102k−1 + a2k−2 .102k−2 + ... + ak .10k + ak .10k−1 + ... + a2k−2 .101 + a2k−1 .100 = a2k−1 (102k−1 + 100 ) + (a2k−2 .102k−2 + ... + a2k−2 .101 ) = a2k−1 .P + Q Trong ®ã: vµ P = 100...001 | {z } | {z } = 11. 9090...9091 2k ch÷ sè 2k−2 Q = a2k−2 .10 + ... + Theo gi¶ thiÕt quy n¹p Bµi to¸n 2.1.4 2k−2ch÷ sè a2k−2 .101 Q chia hÕt cho 11. VËy n chia hÕt cho 11. (®pcm) Trong mét sè palindrome nhÞ ph©n, ch÷ sè ®øng ®Çu lµ nh÷ng ch÷ sè tiÕp theo cã thÓ lµ nhÞ ph©n cã ®é dµi Gi¶i: Theo bµi 0 hoÆc 1. H·y ®Õm tÊt c¶ c¸c sè palindrome n. 2.1.2, chóng ta chØ cÇn quan t©m ®Õn vÞ trÝ, mçi vÞ trÝ nµy cã thÓ lÊp ®Çy b»ng ch÷ sè c¶ 2[ n−1 2 ] 1 hn + 1i 2 −1 = hoÆc ch÷ sè hn − 1i 0.VËy 2 cã tÊt sè tho¶ m·n yªu cÇu bµi to¸n. Bµi to¸n 2.1.5 Trong 100000 sè nguyªn d­¬ng ®Çu tiªn cã bao nhiªu sè mµ trong biÓu diÔn thËp ph©n cña nã chøa ®óng mét ch÷ sè mét ch÷ sè Gi¶i: 1 vµ 3, mét ch÷ sè 4 vµ 5. Ta viÕt 100000 sè nguyªn d­¬ng ®Çu tiªn theo c¸ch sau: +) Sè 0 viÕt lµ 00000. +) Sè 1 viÕt lµ 00001. +) Sè 2 viÕt lµ 00002. ................................. +) Sè 99999 viÕt lµ 99999. Theo c¸ch viÕt trªn, mçi sè cÇn t×m cã mét trong 5 vÞ trÝ. Ch÷ sè 3 cã thÓ chän bÊt kú 5 vÞ trÝ ®· cho, sau ®ã ch÷ sè 4 cã thÓ chän bÊt kú mét trong 4 vÞ trÝ cßn l¹i, ch÷ sè 5 cã thÓ chän bÊt kú mét trong 3 vÞ trÝ cßn l¹i, trÝ ta cã thÓ chän bÊt kú ch÷ sè nµo thuéc tËp hîp cßn hai vÞ {0, 1, 2, 6, 7, 8, 9}. VËy cã (5).(4).(3).(7).(7) = 2940 sè nguyªn tho¶ m·n yªu cÇu bµi to¸n. Bµi to¸n 2.1.6 T×m sè ­íc thùc sù cña sè sè nguyªn d­¬ng Gi¶i: 441000 (mét ­íc thùc sù cña mét n lµ bÊt kú ­íc nµo cña n kh¸c 1 vµ n). Mét sè nguyªn bÊt kú cã thÓ biÓu thÞ duy nhÊt b»ng tÝch cña luü thõa 19 c¸c sè nguyªn tè. Cô thÓ: 441000 = (23 ).(32 ).(53 ).(72 ). BÊt kú mét ­íc nµo thùc sù hay kh«ng thùc sù lµ sè cã d¹ng (2a ).(3b ).(5c ).(7d ), 0 ≤ a ≤ 3; 0 ≤ b ≤ 2; 0 ≤ c ≤ 3; 0 ≤ d ≤ 2. Trong c¸ch biÓu diÔn nµy, cã 4 c¸ch chän, b cã 3 c¸ch chän, c cã 4 c¸ch chän, d cã 3 c¸ch trong ®ã: a chän. VËy b»ng quy t¾c nh©n, tæng sè ­íc thùc sù tho¶ m·n sÏ lµ: (4).(3).(4).(3) − 2 = 142 Bµi to¸n 2.1.7 (sè) §Õm sè ­íc thùc sù cña mét sè nguyªn N biÕt N cã kÕt qu¶ ph©n tÝch ra thõa sè nguyªn tè nh­ sau: N = pn1 1 pn2 2 ...pnk k (trong ®ã Gi¶i: p1 , p2 , ..., pk Theo bµi lµ c¸c ­íc sè nguyªn tè) 2.1.6 sè c¸c ­íc thùc sù cña N lµ: (n1 + 1)(n2 + 1)...(nk + 1) − 2 Bµi to¸n 2.1.8 Mét tËp hîp gåm ni vËt ®ång nhÊt cã dÊu hiÖu i, trong ®ã i = 1, 2, ..., k . Cã bao nhiªu c¸ch lÊy ra Ýt nhÊt mét vËt tõ tËp hîp trªn. Gi¶i: Gi¶ sö nh÷ng vËt cã dÊu hiÖu tè cña sè nguyªn ­íc cña N trong bµi i lµ nh÷ng vËt pi (coi pi lµ nh©n tö nguyªn 2.1.7). Yªu cÇu bµi to¸n t­¬ng tù nh­ ®Õm sè N , kh«ng bao gåm sè 1. Theo bµi 2.1.7 kÕt qu¶ cÇn t×m lµ: (n1 + 1)(n2 + 1)...(nk + 1) − 1 Bµi to¸n 2.1.9 cho T×m sè c¸ch ph©n tÝch 441000 thµnh hai nh©n tö m vµ n sao m > 1, n > 1 vµ m, n chØ cã ­íc chung lµ 1. (Nãi c¸ch kh¸c m vµ n lµ hai sè nguyªn tè cïng nhau). Gi¶i: Ta xÐt tËp hîp sènguyªn tè cña X = {23 ; 32 ; 53 ; 72 } 441000. liªn quan ®Õn sù ph©n tÝch ra thõa Râ rµng r»ng mçi phÇn tö cña trong sù ph©n tÝch ra thõa sè nguyªn tè cña xuÊt hiÖn ®ång thêi ë c¶ thµnh X. X ph¶i xuÊt hiÖn m hoÆc cña n nh­ng kh«ng ®­îc 2 sè. H¬n n÷a, hai sù ph©n tÝch cña m vµ n ph¶i hîp Tøc lµ sè c¸ch ph©n tÝch 441000 thµnh cÆp m, n 20 b»ng víi sè c¸ch chia X n.m lµ sù ph©n tÝch gièng nhau). C¸c kÕt qu¶ ph©n chia tËp thµnh 2 tËp con kh«ng rçng (kh«ng quan t©m ®Õn thø tù v× X m.n vµ (kh«ng tÝnh thø tù) tho¶ m·n yªu cÇu lµ: X = {23 } + {32 , 53 , 72 } = {32 } + {23 , 53 , 72 } = {72 } + {23 , 32 , 53 } = {23 , 32 } + {53 , 72 } = {23 , 53 } + {32 , 72 } = {23 , 72 } + {32 , 53 } Do ®ã kÕt qu¶ cña bµi to¸n lµ: Bµi to¸n 2.1.10 Tæng qu¸t bµi lµ c¸c sè nguyªn tè (k ≥ 2). 4 + 3 = 7 = 24−1 − 1 2.1.9 ta cã: nÕu N = pn1 1 pn2 2 …pnk k , p1 , p2 , …, pk Th× sè c¸ch ph©n tÝch N = m.n sao cho m, n lµ hai sè nguyªn tè cïng nhau lµ: 2k−1 − 1 Gi¶i: (m > 1, n > 1) Chøng minh b»ng ph­¬ng ph¸p quy n¹p theo +) Cho +) Cho k. k = 2, kÕt qu¶ lµ dÔ thÊy. k ≥ 3, chóng ta chØ ra r»ng mét tËp hîp k phÇn tö ph©n biÖt Z = {a1 , a2 , …, ak−1 , ak } cã 2k−1 − 1 c¸ch ph©n chia thµnh hai phÇn kh«ng rçng (kh«ng tÝnh thø tù). Gi¶ thiÕt kÕt qu¶ ®óng víi nh÷ng tËp hîp cã phÇn tö ph©n biÖt. Mét sù ph©n chia cña (k − 1) Z lµ: Z = {ak } ∪ {a1 , a2 , …, ak−1 } ≡ {ak } ∪ W B©y giê gi¶ thiÕt quy n¹p W cã 2k−2 − 1 c¸ch ph©n chia tho¶ m·n yªu cÇu. øng víi mçi c¸ch ph©n chia ®ã ta thªm hai c¸ch ph©n chia cña ph©n chia Z. ak vµo mét trong hai phÇn th× ®­îc TÝnh thªm c¸ch ph©n chia ë trªn ta cã kÕt qu¶ sè Z thµnh hai phÇn tho¶ m·n yªu cÇu lµ: 1 + (2k−2 − 1).2 = 2k−1 − 1(®pcm). §Þnh nghÜa 2.1.11 1. Cho X Trong mét chuçi nhÞ ph©n c¸c phÇn tö b»ng lµ mét tËp hîp tÊt c¶ c¸c chuçi nhÞ ph©n cã ®é dµi 21 0 hoÆc b»ng n. Mét hµm l«gÝc cña n biÕn lµ mét hµm tõ X Bµi to¸n 2.1.12 Gi¶i: Lùc l­îng cña f Y = {0, 1}. T×m sè hµm l«gÝc ph©n biÖt cña X lµ: n biÕn. r = 2n . Do ®ã sè hµm l«gÝc tho¶ m·n lµ 2r . Mét hµm l«gÝc ®­îc gäi lµ tù ®èi ngÉu nÕu gi¸ trÞ cña §Þnh nghÜa 2.1.13 hµm tíi tËp hîp vÉn kh«ng thay ®æi nÕu mçi phÇn tö thuéc miÒn x¸c ®Þnh cña ®æi b»ng c¸ch: ch÷ sè VÝ dô 2.1.14 Khi f thay 0 ®æi thµnh sè 1 vµ ng­îc l¹i. n = 6, f (101101) = f (010010) nªn f lµ mét hµm l«gÝc tù ®èi ngÉu. Bµi to¸n 2.1.15 Gi¶i: Cã 4 H·y liÖt kª tÊt c¶ c¸c hµm l«gÝc tù ®èi ngÉu hai biÕn. hµm l«gÝc ®èi ngÉu tõ tËp hîp X = {00; 01; 10; 11} tíi tËp hîp Y = {0; 1} a)f1 (00) = f1 (11) = f1 (01) = f1 (10) = 0 b)f2 (00) = f2 (11) = f2 (01) = f2 (10) = 1 c)f3 (00) = f3 (11) = f3 (01) = f3 (10) = 1 d)f4 (00) = f4 (11) = f4 (01) = f4 (10) = 0 n biÕn. r Gi¶i: Theo bµi 2.1.12 X cã thÓ ph©n thµnh = 2n−1 cÆp (ς, ς 0 ) trong ®ã 2 0 chuçi ς cã ®­îc tõ ς b»ng c¸ch thay 0 thµnh 1 vµ ng­îc l¹i. §èi víi mçi cÆp r th× gi¸ trÞ cña hµm l«gÝc tù ®èi ngÉu cã thÓ nhËn lµ 0 hoÆc 1. Do ®ã cã 2 2 Bµi to¸n 2.1.16 T×m sè l­îng c¸c hµm l«gÝc tù ®èi ngÉu cña hµm nh­ vËy. §©y chÝnh lµ c¨n bËc hai cña tæng sè c¸c hµm l«gÝc. Bµi to¸n 2.1.17 ®Õn Cho mét l­íi gåm c¸c « vu«ng. C¸c nót ®­îc ®¸nh sè tõ 0 n theo chiÒu tõ tr¸i sang ph¶i vµ tõ 0 ®Õn m theo chiÒu tõ d­íi lªn trªn. Hái cã bao nhiªu ®­êng ®i kh¸c nhau tõ nót (0, 0) ®Õn nót (n, m) nÕu chØ cho phÐp ®i trªn c¹nh c¸c « vu«ng theo chiÒu sang ph¶i hoÆc lªn trªn. Gi¶i Mét ®­êng ®i nh­ thÕ ®­îc xem gåm n + m ®o¹n ( mçi ®o¹n lµ mét c¹nh « vu«ng ). T¹i mçi ®o¹n chØ ®­îc chän mét trong hai gi¸ trÞ : ®i lªn ( mµ ta m· lµ 1) hay sang ph¶i ( mµ ta m· lµ 0 ). Sè ®o¹n ®i lªn ®óng b»ng sang ph¶i ®óng b»ng m vµ sè ®o¹n n. Bµi to¸n dÉn ®Õn viÖc t×m xem cã bao nhiªu d·y nhÞ 22 ph©n ®é dµi n + m trong ®ã cã ®óng m thµnh phÇn b»ng 1. §©y còng chÝnh lµ sè tËp con ®Õm b»ng m phÇn tö cña mét tËp n phÇn tö, v× thÕ sè ®­êng ®i cÇn C(n + m, m). Bµi to¸n 2.1.18 cã n+m phÇn tö, Cho m, n lµ c¸c sè nguyªn lín h¬n 1. Cho S lµ mét tËp hîp A1 , A2 , …, Am lµ nh÷ng tËp con cña S. Gi¶ thiÕt r»ng bÊt kú Ai hai phÇn tö x vµ y trong S bao giê còng cã mét tËp hîp Ai vµ y kh«ng ë trong minh r»ng Gi¶i: hoÆc x kh«ng ë trong Ai vµ y ë trong Ai . Chøng n ≤ 2m . Chóng ta h·y liªn kÕt mçi phÇn tö ch÷ sè nÕu Ai sao cho x ë trong a(x) = (x1 , x2 , …, xm ) x trong S víi mét d·y nhÞ ph©n cã m tháa m·n xi = 1 nÕu x ë trong Ai vµ xi = 0 x kh«ng ë trong Ai . Ta x©y dùng mét hµm sè : f : S −→ T = {(x1 , x2 , …, xm ) | xi ∈ {0, 1}} . Tõ gi¶ thiÕt, nÕu x kh¸c y th× f (x) kh¸c f (y), hay f lµ mét hµm ®¬n ¸nh. V× vËy sè phÇn tö cña tËp hîp T ph¶i nhiÒu h¬n hoÆc b»ng sè phÇn tö cña tËp S. DÔ thÊy sè phÇn tö cña T b»ng (x1 , x2 , …, xm ) cã 2m ( bëi v× mçi thµnh phÇn chØ cã thÓ nhËn mét trong hai gi¸ trÞ lµ 0 hoÆc 1). xi cña Do ®ã ta n ≤ 2m . 2.2. Chuyªn ®Ò 2: Ho¸n vÞ vµ tæ hîp Cho f lµ mét ¸nh x¹ tõ tËp h÷u h¹n A vµo tËp h÷u h¹n B. Chóng ta ®Òu biÕt r»ng, nÕu f lµ ®¬n ¸nh th× n(A) ≤ n(B). NÕu f lµ toµn ¸nh th× n(A) ≥ n(B), cßn nÕu f lµ song ¸nh th× n(A) = n(B). §©y chÝnh lµ c¬ së cña ph­¬ng ph¸p thiÕt lËp song ¸nh ®Ó gi¶i mét sè bµi to¸n tæ hîp mµ mét sè s¸ch ®· nªu vµ còng lµ chñ ®Ò ®Çu tiªn t¸c gi¶ luËn v¨n ®­a ra trong vÊn ®Ò nµy. TiÕp ®Õn lµ mét sè bµi to¸n vÒ ho¸n vÞ vßng quanh. Häc sinh cã thÓ thÊy thÝch thó víi sù xuÊt hiÖn hîp lý cña nh÷ng chiÕc ghÕ trong nh÷ng bµi nµy. Chñ ®Ò thø ba 23 ®Ò cËp ®Õn ®ã lµ ph­¬ng ph¸p chøng minh b»ng lý luËn tæ hîp. C¸c em cã thÓ ¸p dông ph­¬ng ph¸p nµy vµo chøng minh mét sè c«ng thøc tæ hîp mµ kh«ng ph¶i dïng nhiÒu ®Õn c¸c c«ng thøc tÝnh to¸n. Do ®ã c¸c c«ng thøc vÒ tæ hîp trë nªn ®¬n gi¶n, dÔ nhí h¬n ®èi víi c¸c em. §Þnh nghÜa 2.2.1 Mét ¸nh x¹ – mét nÕu cø hai phÇn tö ph©n biÖt thuéc Bµi to¸n 2.2.2 cã x vµ f tõ tËp hîp A tíi tËp hîp B y ph©n biÖt cña A ®­îc gäi lµ mét f (x), f (y) th× cã hai ¶nh B. T×m sè ¸nh x¹ mét – mét tõ A tíi B , biÕt A cã m phÇn tö, B n phÇn tö (n ≥ m). Gi¶i: Cã P (n, m) sù lùa chän cho miÒn gi¸ trÞ cña hµm sè. Do ®ã cã P (n, m) hµm mét – mét ph©n biÖt tho¶ m·n yªu cÇu bµi to¸n. Bµi to¸n 2.2.3 M­êi bøc ho¹ kh¸c nhau ®­îc cÊp ph¸t cho n phßng lµm viÖc sao cho kh«ng cã phßng nµo ®­îc nhËn nhiÒu h¬n mét bøc ho¹. T×m sè c¸ch hoµn thµnh c«ng viÖc nµy biÕt: a)n = 14 b)n = 6 Gi¶i: a) P (14, 10) b) (theo bµi 2.2.1) Ta cã sè bøc ho¹ nhiÒu h¬n sè phßng, do ®ã chóng ta lËp ¸nh x¹ tõ tËp hîp c¸c phßng tíi tËp hîp c¸c bøc ho¹. KÕt qu¶ cÇn t×m lµ: §Þnh nghÜa 2.2.4 P (10, 6) Mét ho¸n vÞ vßng quanh lµ mét sù s¾p xÕp c¸c phÇn tö ph©n biÖt quanh mét vßng trßn (hoÆc ®¬n gi¶n chØ lµ mét ®­êng cong khÐp kÝn). Bµi to¸n 2.2.5 Gi¶i: T×m sè ho¸n vÞ vßng quanh cña §¸nh sè c¸c vÞ trÝ dµnh cho Nh­ th­êng lÖ ta sÏ cã n n phÇn tö ph©n biÖt. phÇn tö ph©n biÖt lÇn l­ît lµ 1, 2, …, n. n! c¸ch s¾p xÕp. Tuy nhiªn ®ã kh«ng ph¶i lµ kÕt qu¶ ®óng trong tr­êng hîp nµy v× thùc tÕ hai ho¸n vÞ tuyÕn tÝnh ®­îc coi nh­ lµ mét ho¸n vÞ vßng quanh. VÝ dô, ho¸n vÞ ABCD ho¸n vÞ vßng quanh. KÕt qu¶ cña bµi to¸n trªn lµ thËt ®¬n gi¶n. Mét phÇn tö A1 bÊt kú trong sè 24 vµ BCDA ®­îc coi lµ mét (n − 1)!. PhÐp chøng minh n phÇn tö ë trªn ®­îc ®Æt vµo n−1 mét vÞ trÝ nµo ®ã trªn vßng trßn. Cßn l¹i phÇn tö ®­îc s¾p xÕp vµo n − 1 vÞ trÝ cßn l¹i trªn vßng trßn. Do ®ã cã tÊt c¶ (n − 1)! c¸ch s¾p xÕp tho¶ m·n yªu cÇu bµi to¸n. §Þnh nghÜa 2.2.6 Hai ho¸n vÞ tuyÕn tÝnh cña ph¶n x¹ víi nhau nÕu phÇn tö thø nhÊt ë tö thø hai ë ®Çu tiªn ë p q. lµ phÇn tö thø n−1 ë p n p vµ q ®­îc gäi lµ lµ phÇn tö cuèi cïng ë q ,…,phÇn Mét ho¸n vÞ vßng quanh cña phÇn tö n tö cuèi cïng ë p lµ phÇn tö n−1 phÇn 2 ho¸n vÞ ph¶n x¹ th× kh«ng ®­îc coi lµ ph©n biÖt. T×m sè ho¸n vÞ vµnh kh¨n cña Bµi to¸n 2.2.7 Gi¶i: phÇn phÇn tö ®­îc gäi lµ mét ho¸n vÞ vµnh kh¨n nÕu ®­îc x¸c ®Þnh bëi mét ho¸n vÞ tuyÕn tÝnh cña tö vµ q, Mçi ho¸n vÞ vßng quanh x¸c ®Þnh vÞ vµnh kh¨n lµ: Bµi to¸n 2.2.8 n phÇn tö ph©n biÖt. 2 ho¸n vÞ vµnh kh¨n, do ®ã sè ho¸n (n − 1)! 2 Cã bao nhiªu c¸ch s¾p xÕp chç ngåi cho n häc sinh n÷ vµ n häc sinh nam quanh mét bµn trßn biÕt r»ng gi÷a hai häc sinh n÷ lµ mét häc sinh nam. Gi¶i: Cã (n − 1)! c¸ch s¾p xÕp chç ngåi cho n häc sinh n÷, b©y giê cø gi÷a hai häc sinh n÷ ®Æt mét cµi ghÕ ®Ó cho mét häc sinh nam ngåi vµo. VËy cã n! c¸ch s¾p xÕp chç ngåi cho n häc sinh nam. KÕt qu¶: n!(n − 1)! c¸ch s¾p xÕp tho¶ m·n yªu cÇu. Bµi to¸n 2.2.9 vµ 2 Cã n ng­êi tham dù mét cuéc häp trong ®ã cã 1 gi¸m ®èc phã gi¸m ®èc. Hái cã bao nhiªu c¸ch s¾p xÕp chç ngåi cho ®ã quanh mét bµn trßn sao cho gi¸m ®èc vµ n ng­êi 2 phã gi¸m ®èc lu«n ngåi c¹nh nhau, gi¸m ®èc ngåi ë gi÷a, hai phã gi¸m ®èc ngåi ë hai bªn. Gi¶i: Gi¸m ®èc ngåi vµo mét c¸i ghÕ, hai ghÕ ë hai bªn c¹nh dµnh cho hai phã gi¸m ®èc. Do ®ã cã hai c¸ch s¾p xÕp chç ngåi cho hai phã gi¸m ®èc. Cßn l¹i n − 3 ng­êi ngåi vµo n − 3 ghÕ. Do ®ã cã (n − 3)! c¸ch s¾p xÕp cho c¸c ng­êi cßn l¹i. KÕt qu¶ cã: Bµi to¸n 2.2.10 2.(n − 3)! c¸ch s¾p xÕp tho¶ m·n yªu cÇu. Hái cã bao nhiªu c¸ch s¾p xÕp chç ngåi cho 25 r ng­êi trong sè n ng­êi quanh mét bµn trßn vµ sè cßn l¹i ngåi quanh mét bµn trßn kh¸c. Gi¶i: Cã §Çu tiªn chän ra r ng­êi cho chiÕc bµn thø nhÊt. Cã C(n, r) c¸ch chän. (r − 1)! c¸ch s¾p xÕp chç ngåi ë bµn thø nhÊt. Cã (n − r − 1)! c¸ch s¾p xÕp chç ngåi ë bµn thø hai. KÕt qu¶ cÇn t×m lµ: C(n, r)(r − 1)!(n − r − 1)! Cã bao nhiªu c¸ch s¾p xÕp chç ngåi cho Bµi to¸n 2.2.11 n häc sinh nam (m < n) m häc sinh n÷ vµ xung quanh mét chiÕc bµn trßn sao cho kh«ng cã hai häc sinh n÷ nµo ngåi c¹nh nhau. Gi¶i: §Æt n chiÕc ghÕ xung quanh c¸i bµn, sau ®ã s¾p xÕp chç ngåi cho häc sinh nam. Cã n (n − 1)! c¸ch s¾p xÕp cho n häc sinh nam. TiÕp ®ã cø gi÷a hai häc sinh nam ta thªm vµo mét chiÕc ghÕ. Cã vµo. S¾p xÕp chç ngåi cho m häc sinh n÷ vµo n n chiÕc ghÕ míi cÇn thªm chiÕc ghÕ ®ã. Cã P (n, m) c¸ch s¾p xÕp tho¶ m·n. Sau khi c¸c häc sinh n÷ ®· ngåi hÕt th× nh÷ng ghÕ thõa l¹i bá ra. VËy cã tÊt c¶: (n − 1)!P (n, m) c¸ch s¾p xÕp tho¶ m·n yªu cÇu. Bµi to¸n 2.2.12 Mét phÐp chøng minh b»ng lý luËn tæ hîp lµ mét phÐp chøng minh sö dông nh÷ng lý luËn tæ hîp thay thÕ cho nh÷ng phÐp tÝnh to¸n. H·y dïng phÐp chøng minh b»ng lý luËn tæ hîp chøng minh c«ng thøc: C(m + n, 2) − C(m, 2) − C(n, 2) = m.n Gi¶i: Xem xÐt mét nhãm gåm t¾c nh©n cã m.n m häc sinh nam vµ n häc sinh n÷. B»ng quy c¸ch chän ra mét häc sinh nam vµ mét häc sinh n÷. Theo c¸ch kh¸c mµ còng ®­a ®Õn kÕt qu¶ t­¬ng tù lµ cã hai häc sinh bÊt kú sau ®ã trõ ®i C(m + n, 2) c¸ch chon C(m, 2)vµ C(n, 2) sè c¸ch chän ra hai häc sinh cïng lµ nam hoÆc cïng lµ n÷. Sau ®©y ta chøng minh mét sè c«ng thøc quen thuéc vÒ tæ hîp: Bµi to¸n 2.2.13 c«ng thøc Pascal Gi¶i: Sö dông phÐp chøng minh b»ng lý luËn tæ hîp, chøng minh C(n, r) = C(n − 1, r) + C(n − 1, r − 1) . Ta xem xÐt mét tËp X gåm n phÇn tö ph©n biÖt. LÊy Y 26 lµ mét tËp con bÊt kú cña X tËp con cña (n − 1) phÇn tö. gåm Y cã r Mçi tËp con cña X cã phÇn tö lµ mét phÇn tö hoÆc lµ hîp cña mét tËp con cña phÇn tö víi tËp hîp ®¬n lÎ gåm mét phÇn tö cßn l¹i cña thuéc r X Y cã (r − 1) nh­ng kh«ng Y . Cã C(n − 1, r) tËp con thuéc lo¹i tr­íc vµ C(n − 1, r − 1) tËp con thuéc lo¹i sau. Tæng cña hai kÕt qu¶ trªn lµ: Chøng minh c«ng thøc khai triÓn nhÞ thøc Newton. Bµi to¸n 2.2.14 n C(n, r) n (x+y) = x +C(n, 1)x n−1 y+...+C(n, r)x n−r r n y +...+y = n X C(n, r)xn−r y r r=0 Gi¶i: Sè h¹ng tæng qu¸t trong khai triÓn C(n, r). NÕu chóng ta viÕt (x + y)n (x + y)n nh­ sau:(x lµ xn−r y r nh©n víi hÖ sè + y)1 (x + y)2 ...(x + y)n , C(n, r) chÝnh lµ sè c¸ch chän ra r ngoÆc ®¬n tõ n ngoÆc chóng ta thÊy hÖ sè ®¬n ë trªn ®Ó cã ®­îc yr trong tÝch xn−r y r . Sè nguyªn C(n, r) ®­îc gäi lµ hÖ sè nhÞ thøc. Bµi to¸n 2.2.15 Chøng minh C«ng thøc Vandermonde: C(p + q, r) = r X C(p, j)C(q, r − j) j=0 Chøng minh: hÖ sè cña xr B»ng ®Þnh lý nhÞ thøc, vÕ tr¸i cña c«ng thøc Vandermonde lµ trong (1 + x)p+q ; vÕ ph¶i cña c«ng thøc ®ã lµ hÖ sè cña xr trong (1 + y)p (1 + y)q . Hai hÖ sè hiÓn nhiªn ph¶i b»ng nhau. Bµi to¸n 2.2.16 Chøng minh c«ng thøc Newton's: C(n, r)C(r, k) = C(n, k)C(n − k, r − k) Gi¶i: gåm Gi¶ thiÕt mét c©u l¹c bé cã r ng­êi. Trong sè l·nh ®¹o c©u l¹c bé r n thµnh viªn. CÇn bÇu ra mét ban ®¹i diÖn ng­êi thuéc ban ®¹i diÖn chän ra (n ≥ r ≥ k). k ng­êi lµm ban Sè c¸ch chän ra ban l·nh ®¹o cã thÓ t×m b»ng hai c¸ch. (i) §Çu tiªn chän r ng­êi tõ tËp hîp viÖc nµy cã thÓ thùc hiÖn theo C(n, r) 27 n thµnh viªn cña c©u l¹c bé, c«ng c¸ch. Sau ®ã, chän k ng­êi vµo ban l·nh ®¹o tõ r ng­êi ®¹i diÖn. C«ng viÖc thø hai cã thÓ thùc hiÖn theo C(r, k) c¸ch. KÕt qu¶ cã trong ®ã cã k C(n, r)C(r, k) c¸ch chän ra ban ®¹i diÖn gåm r ng­êi ng­êi trong ban l·nh ®¹o. §©y lµ vÕ tr¸i c«ng thøc. (ii) §Çu tiªn chän k ban l·nh ®¹o, cã thµnh viªn trong sè C(n, k) c¸ch chän. Sau ®ã chän thªm k trong sè nh÷ng ng­êi cßn l¹i ®Ó cïng víi thµnh ban ®¹i diÖn, cã n thµnh viªn cña c©u l¹c bé vµo (r − k) ng­êi n÷a ng­êi trong ban l·nh ®¹o lËp C(n − k, r − k)c¸ch chän. KÕt qu¶ cÇn t×m lµ: C(n, k)C(n − k, r − k) §©y chÝnh lµ vÕ ph¶i cña c«ng thøc. Bµi to¸n 2.2.17 Chøng minh c«ng thøc C(n + 1, r + 1) = C(n, r) + C(n − 1, r) + C(n − 2, r) + ... + C(r, r) Gi¶i: +) Víi (∗) n = 1 th× c«ng thøc hiÓn nhiªn ®óng. +) Víi n > 1, sö dông c«ng thøc Pascal ta thay thÕ vÕ tr¸i b»ng C(n, r + 1) + C(n, r). HiÓn nhiªn ®¼ng thøc ®óng theo ph­¬ng ph¸p quy n¹p to¸n häc. Bµi to¸n 2.2.18 Gi¶i: Ta cã: TÝnh S = 1.2 + 2.3 + 3.4 + … + n.(n + 1) k(k + 1) = C(k + 1, 2) S = 2[C(2, 2) + C(3, 2) + … + C(n + 1, 2)] (*) = 2C(n + 2, 3) = Bµi to¸n 2.2.19 Theo bµi ¸nh x¹ 1-1 tõ tËp X chóng P ◦Q P lµ P −1 n(n + 1)(n + 1) 3 2.2.2 mét ho¸n vÞ cña X = {1, 2, 3, …, n} lµ mét vµo chÝnh nã. NÕu P còng lµ mét ho¸n vÞ cña vµ X. còng lµ mét ho¸n vÞ cña X. Cho P = 12534. H·y t×m: a) P ◦ Q b) Q ◦ P 28 Q lµ hai ho¸n vÞ cña X , tÝch cña H¬n n÷a, ¸nh x¹ nghÞch ®¶o cña X = {1, 2, 3, 4, 5}; Q = 23415; c)Q−1 vµ P −1 Gi¶i: a) P ◦ Q = 25314 b) Q ◦ P = 23541 c)Q−1 = 41235 vµ P −1 = 12453 2.3. Chuyªn ®Ò 3: Nguyªn lý chuång chim bå c©u Cho Bµi to¸n 2.3.1 cña X cã lµ tËp con bÊt kú 7 phÇn tö. Chøng minh r»ng lu«n tån t¹i hai phÇn tö cña S cña chóng b»ng Gi¶i: X = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, S 10. Nh÷ng tËp con H1 = {0; 10}; H2 = {1; 9}; H3 = {2; 8}; H4 = {3; 7}; H5 = {4; 6}; H6 = {5} c¸c phÇn tö cña mµ tæng S coi nh­ cã thÓ coi nh­ 6 chuång chim bå c©u vµ 7 con chim bå c©u. Theo nguyªn lý chuång chim bå c©u ta cã ®iÒu ph¶i chøng minh. Cho Bµi to¸n 2.3.2 X lµ mét tËp hîp bÊt kú gåm H·y chØ ra r»ng cã hai sè nguyªn chia hÕt cho Gi¶i: x, y thuéc sè nguyªn ph©n biÖt. x+y tho¶ m·n hoÆc x−y 10. Gi¶ sö X = {x1 , x2 , x3 , x4 , x5 , x6 , x7 } ph©n biÖt. Gäi ri lµ sè d­ khi chia xi cho H1 = {xi | ri = 0} VËy cã X 7 7 lµ tËp hîp gåm sè nguyªn 10. Ta xÐt c¸c tËp con cña X : H2 = {xi | ri = 5} H3 = {xi | ri = 1 hoÆc 9} H4 = {xi | ri = 2 hoÆc 8} H5 = {xi | ri = 3 hoÆc 7} H6 = {xi | ri = 4 hoÆc 6} 6 chuång chim bå c©u cho 7 con chim. NÕu x vµ y cïng thuéc NÕu x thuéc mét trong vµ y H1 hoÆc 4 tËp 10 nh­ng kh«ng x¶y ra c¶ x + y Bµi to¸n 2.3.3 H2 th× c¶ x+y cßn l¹i th× hoÆc x−y hoÆc x+y x−y chia hÕt cho ®iÓm trong tam gi¸c ®ã. Chøng minh r»ng cã Ýt nhÊt 29 x−y hoÆc Cho mét tam gi¸c ®Òu cã ®é dµi b»ng chia hÕt cho 10. chia hÕt cho 10. 2cm. LÊy bÊt kú 5 2 ®iÓm cã kho¶ng c¸ch nhá h¬n Gi¶i: 1cm. Chia tam gi¸c ®· cho thµnh Chóng ta cã 4 tam gi¸c ®Òu cã kho¶ng c¸ch b»ng 1cm. 4 tam gi¸c vµ 5 ®iÓm do ®ã kÕt qu¶ lµ hiÓn nhiªn. Bµi to¸n 2.3.4 Cho mét tam gi¸c ®Òu cã ®é dµi c¹nh b»ng 3cm. LÊy 10 ®iÓm bÊt kú trong tam gi¸c ®ã. Chøng minh r»ng cã Ýt nhÊt hai ®iÓm cã kho¶ng c¸ch nhá h¬n 1cm. Gi¶i: Chia tam gi¸c ban ®Çu thµnh Ta cã 9 tam gi¸c vµ 10 ®iÓm do ®ã kÕt qu¶ lµ hiÓn nhiªn. Bµi to¸n 2.3.5 9 tam gi¸c ®Òu cã ®é dµi c¹nh b»ng 1cm. Cho h×nh vu«ng cã ®é dµi c¹nh b»ng 2cm. LÊy bÊt kú 5 ®iÓm n»m trong h×nh vu«ng ®ã. Chøng minh r»ng cã Ýt nhÊt c¸ch nhá h¬n Gi¶i: √ 2 ®iÓm cã kho¶ng 2cm. 4 h×nh vu«ng cã ®é dµi c¹nh b»ng 1cm. √ 2 vµ 5 ®iÓm do ®ã kÕt qu¶ Ta cã 4 h×nh vu«ng cã ®é dµi ®­êng chÐo b»ng Chia h×nh vu«ng ban ®Çu thµnh lµ hiÓn nhiªn. Bµi to¸n 2.3.6 Cã n ®éi bãng ®¸ tham gia thi ®Êu vßng trßn tÝnh ®iÓm. BiÕt r»ng ®éi nµo còng cã Ýt nhÊt mét trËn th¾ng (c¶ gi¶i kh«ng cã trËn nµo hoµ). H·y chøng minh r»ng cã Ýt nhÊt Gi¶i: Sè trËn th¾ng cña mét ®éi Ýt nhÊt lµ nh­ (n − 1) chuång chim bå n ®éi coi nh­ n con chim bå c©u. Do ®ã kÕt qu¶ lµ hiÓn nhiªn. Bµi to¸n 2.3.7 X 1 trËn vµ nhiÒu nhÊt lµ n − 1 trËn. 1, 2, 3, …, n − 1 Nh­ vËy ta coi sè trËn th¾ng c©u, 2 ®éi cã cïng sè trËn th¾ng. Cho tËp hîp X gåm n sè nguyªn bÊt kú. Chøng minh r»ng lu«n cã mét tËp con mµ tæng cña c¸c sè nguyªn cã trong tËp hîp ®ã chia hÕt cho Gi¶i: n. Gi¶ sö X = {x1 , x2 , …, xn } vµ Si = x1 + x2 + … + xi trong ®ã i = 1, 2, …, n. NÕu cã mét Si nµo ®ã chia hÕt cho n th× ta cã ®iÒu ph¶i chøng minh. Trong tr­êng hîp ng­îc l¹i, ta gäi nhÊt b»ng 1 vµ lín nhÊt b»ng ri lµ sè d­ khi chia (n − 1). 30 Si cho n th× ri nhá Do ®ã b»ng nguyªn lý chuång chim bå c©u, chóng ta ph¶i cã p, q nµo ®ã tho¶ m·n p 5 ta s¾p 5 ng­êi quanh mét bµn trßn sao cho mçi ng­êi chØ quen biÕt víi hai ng­êi ngåi ngay bªn c¹nh. Trong t×nh huèng nµy kh«ng 3 ng­êi nµo tho¶ m·n quen biÕt lÉn nhau tõng ®«i mét hoÆc kh«ng cã tËp hîp quen biÕt lÉn nhau tõng ®«i mét. VËy Bµi to¸n 2.4.6 R(3, 3) = 6. Chøng minh r»ng nÕu m, n lµ hai sè nguyªn lín h¬n 2 th×: R(m, n) ≤ R(m − 1, n) + R(m, n − 1) (BiÓu thøc nµy cho ta cËn trªn cña Gi¶i: LÊy p ≡ R(m − 1, n), q ≡ R(m, n − 1) vµ r ≡ p + q . Ta quan t©m ®Õn mét nhãm 1 vµ M R(m, n)) r ng­êi lµ {1, 2, …, r}. Gäi L lµ tËp hîp nh÷ng ng­êi biÕt ng­êi lµ tËp hîp nh÷ng ng­êi kh«ng biÕt ng­êi 1. C¶ hai tËp hîp nµy cã r − 1 ng­êi. Do ®ã hoÆc L cã Ýt nhÊt p ng­êi hoÆc M a) NÕu L cã Ýt nhÊt mét tËp con cña cña p = R(m − 1, n) ng­êi (m − 1) cã Ýt nhÊt q ng­êi th× b»ng ®Þnh nghÜa, L chøa ng­êi quen biÕt lÉn nhau hoÆc chøa mét tËp con n ng­êi kh«ng quen biÕt lÉn nhau. Trong tr­êng hîp nµy (m − 1) ng­êi nµy vµ ng­êi 1 t¹o thµnh nhãm m ng­êi quen biÕt lÉn nhau. Do ®ã, trong tr­êng hîp nµy nhãm cña lu«n cã R(m − 1, n) + R(m, n − 1) ng­êi m ng­êi quen biÕt lÉn nhau hoÆc n ng­êi kh«ng quen biÕt lÉn nhau. VËy: R(m, n) ≤ R(m − 1, n) + R(m, n − 1) 35 b) Lý luËn t­¬ng tù nÕu M Tõ cã Ýt nhÊt q ng­êi a) vµ b) suy ra ®iÒu ph¶i chøng minh. NÕu Bµi to¸n 2.4.7 R(m − 1, n) vµ R(m, n − 1) lµ 2 2. sè ch½n lín h¬n Chøng minh r»ng: R(m, n) ≤ R(m − 1, n) + R(m, n − 1) − 1 Gi¶i: T­¬ng tù nh­ r ≡ p + q. kú 2.4.6, lÊy p ≡ R(m − 1, n), q ≡ R(m, n − 1) Nh­ thÕ ®ñ ®Ó chØ ra r»ng trong mét nhãm ng­êi bÊt X = {1, 2, …, r − 1} lu«n cã hoÆc mét nhãm con m ng­êi quen biÕt lÉn n nhau hoÆc mét nhãm con ng­êi quen biÕt ng­êi sè ch½n. Nh­ng cã thÓ chän r−1 i = 1. ng­êi kh«ng quen biÕt lÉn nhau. Goi i lµ sè lÎ, do ®ã tån t¹i Ýt nhÊt mét sè Gäi L ®Ó di lµ tËp hîp nh÷ng ng­êi quen biÕt ng­êi sè ch½n ng­êi. B©y giê, hoÆc ng­êi. Nh­ng di lµ sè i víi i = 1, 2, …, r − 1. Ta cã: d1 + d2 + … + dr−1 lµ tËp hîp nh÷ng ng­êi kh«ng quen biÕt ng­êi q (r − 1) vµ L cã Ýt nhÊt 1. Tõ ®ã, L, M p−1 ng­êi hoÆc lµ ch½n, ta 1 vµ M cïng ph¶i cã M cã Ýt nhÊt p − 1 lµ lÎ. Do ®ã hoÆc L cã Ýt nhÊt p ng­êi hoÆc M q cã Ýt nhÊt ng­êi. a) Gi¶ sö L cã Ýt nhÊt p ng­êi lý luËn t­¬ng tù bµi trªn suy ra bÊt ®¼ng thøc cÇn chøng minh. b) Gi¶ sö M cã Ýt nhÊt q ng­êi lý luËn t­¬ng tù suy ra ®iÒu ph¶i chøng minh. Bµi to¸n 2.4.8 Chøng minh r»ng: R(4, 3) = 9 Gi¶i: Theo bµi trªn ta cã: R(4, 3) ≤ R(3, 3) + R(4, 2) − 1 = 6 + 4 − 1 = 9 §Ó chøng minh R(4, 3) = R(3, 4) > 8 chóng ta ®­a ra mét nhãm nh­ng trong nhãm ®ã kh«ng t×m ra mét nhãm con gåm lÉn nhau vµ kh«ng cã nhãm con gåm 3 8 ng­êi ng­êi quen biÕt 4 ng­êi kh«ng quen biÕt lÉn nhau. 36 Ta xÕp 2 8 ng­êi quanh mét bµn trßn. Mçi ng­êi chØ biÕt chÝnh x¸c 3 ng­êi kh¸c: ng­êi ngåi ngay bªn c¹nh anh ta vµ mét ng­êi ngåi xa anh ta nhÊt. VËy R(4, 3) = 9 Chøng minh r»ng: Bµi to¸n 2.4.9 R(5, 3) = 14 Gi¶i: R(5, 3) ≤ R(4, 3) + R(5, 2) = 9 + 5 = 14. §Ó chøng minh R(5, 3) = R(3, 5) > 13 ta s¾p xÕp 13 ng­êi ngåi quanh mét bµn trßn sao cho mçi ng­êi chØ quen biÕt víi ng­êi thø 5 ë bªn tr¸i anh ta vµ ng­êi thø 5 ë bªn ph¶i anh ta. Trong t×nh huèng nµy sÏ kh«ng cã mét nhãm con nµo gåm 5 biÕt lÉn nhau vµ kh«ng cã nhãm con nµo gåm nhau. VËy Mét cÊp sè céng cã ®é dµi d; a + 2d; …; a + (n − 1)d >. X = {1, 2, …, 9} thµnh 2 Q vµ lÊy 5 P P. DÜ nhiªn 1 vµ 9 X thµnh 2 tËp hîp P kh«ng cïng ë trong P do P do 3 tr­êng hîp x¶y ra: ë trong suy ra trong 3. lµ phÇn tö cña 1: Tr­êng hîp 3 ChØ ra r»ng bÊt kú sù ph©n chia nµo cña Gi¶ sö kÕt luËn cña bµi to¸n lµ sai. Ta ph©n chia ®ã cã ®ã n lµ mét d·y cã d¹ng < a; a + tËp con th× Ýt nhÊt mét trong hai tËp con ®ã chøa mét cÊp sè céng cã ®é dµi vµ ng­êi kh«ng quen biÕt lÉn R(5, 3) = 14. Bµi to¸n 2.4.10 Gi¶i: 3 ng­êi quen P nh­ thÕ 4 Q. Tõ ë trong 1 3 vµ Q. P ë trong 9 Tõ ë trong 3 vµ 4 vµ 9 Q suy ra ë trong chøa mét cÊp sè céng lµ Tr­êng hîp 2: Sè 9 ë trong P khi thay mäi phÇn tö nh­ tr­êng hîp Tr­êng hîp ë trong Q 6 Q. Tõ ë trong suy ra 2 1 5 vµ P. Tõ ë trong ë trong 5 P. vµ 6 Tõ ë trong 5 vµ 6 ë 7 ë trong Q. Tõ 7 vµ 9 ë trong Q suy ra 8 ë trong P . Nh­ng suy ra P Sè vµ 2, 5, 8, m©u thuÉn. 1 ë trong Q. V× tËp X lµ kh«ng thay ®æi i trong ®ã b»ng phÇn tö 10 − i. Do ®ã lý luËn t­¬ng tù 1 suy ra ®iÒu m©u thuÉn. 3: Sè 1 vµ 9 ë trong Q. Sè 7 hoÆc ë trong P Gi¶ sö nã ë trong P. Tõ 5 vµ 7 ë trong 37 P suy ra c¶ 3 vµ 6 hoÆc ë trong ë trong Q. Q. §iÒu ®ã cã nghÜa Do ®ã Q cã mét cÊp sè céng 3, 6, 9. NÕu 7 ë trong Q th× 8 ë trong P . 1 vµ 7 ë trong Q, 4 ë trong P . Tõ 4 vµ 5 ë trong P 1 vµ 3 ë trong Q th× 2 ë trong P . VËy P Bµi to¸n 2.4.11 cã cÊp sè céng th× 3 ë trong Q. Tõ 2, 5, 8, m©u thuÉn. (V« ®Þch Liªn X«) Cã mét nhãm ng­êi mµ trong ®ã, mçi cÆp kh«ng quen nhau cã ®óng hai ng­êi quen chung, cßn mçi cÆp quen nhau th× kh«ng cã ng­êi quen chung. Chøng minh r»ng sè ng­êi quen cña mçi ng­êi lµ nh­ nhau. Gi¶i: Gi¶ sö A vµ B. vµ b kh«ng quen nhau, h¬n n÷a hä ®· cã mét ng­êi quen chung lµ a). T­¬ng a quen b vµ tËp c¸c ng­êi quen cña a vµ b (kh«ng kÓ a vµ b) lµ Mèi ng­êi tù, mçi ng­êi thuéc song ¸nh ®i tõ NÕu a0 B thuéc A sÏ quen duy nhÊt mét ng­êi thuéc sÏ quen duy nhÊt mét ng­êi thuéc B (do a0 A. VËy tån t¹i mét A tíi B , tøc a vµ b cã sè ng­êi quen b»ng nhau. a kh«ng quen b th× tån t¹i c quen c¶ a vµ b. Do ®ã sèng­êi quen cña a vµ b b»ng nhau do cïng b»ng sè ng­êi quen cña c. 2.5. Chuyªn ®Ò 5: C¸c sè Catalan Bµi to¸n 2.5.1 Mét ®­êng ®i tõ ®iÓm P0 tíi ®iÓm Pm trong hÖ trôc to¹ ®é cã thÓ coi nh­ lµ mét d·y ®iÓm cã to¹ ®é nguyªn < P0 , P1 , ...Pm >; Pi (xi , yi ) sao cho i = 0, 1, …., m − 1 xi+1 = xi + 1; yi+1 = yi yi + 1. §­êng ®i nµy lµ ®Ñp nÕu hoÆc xi+1 = xi ; yi+1 = yi < xi (i = 0, 1, ..., m) nÕu kh«ng tho¶ m·n nh­ vËy ta nãi lµ ®­êng ®i xÊu. a) T×m ra sè ®­êng ®i tõ P0 tíi Pm . b) §Õm sè ®­êng ®i ®Ñp tõ (x0 , y0 ) tíi (xm , ym ). Gi¶i: a) lµ Theo bµi 2.1.17 ®Æt m = xm − x0 C(xm − x0 + ym − y0 ; xm − x0 ). b) 38 vµ n = ym − y0 th× ta cã kÕt qu¶ S¬ ®å S¬ ®å 2.1 minh ho¹ ®­êng ®i xÊu tõ (x0 , y0 ) tíi (xm , ym ). ®­êng th¼ng Q lµ 2.1 A1 , tõ y =x Q tíi t¹i ®iÓm ®Çu tiªn (xm , ym ) lµ A2 . Q. §­êng ®i nµy c¾t Gäi ®o¹n ®­êng ®i tõ LÊy ®èi xøng víi A1 (x0 , y0 ) tíi qua ®­êng th¼ng y = x ta ®­îc ®­êng th¼ng A01 . Ta cã A01 + A2 lµ mét ®­êng ®i tõ (y0 , x0 ) tíi (xm , ym ). (TÊt c¶ c¸c ®­êng ®i tõ (y0 , x0 ) ®Òu lµ xÊu nh­ng ®iÒu ®ã kh«ng quan träng ë d©y). VËy, bÊt kú mét ®­êng ®i tõ (y0 , x0 ) ®Þnh mét ®èi xøng tõng phÇn cña mét ®­êng ®i xÊu tõ Theo bµi tíi (xm , ym ) x¸c (x0 , y0 ) tíi (xm , ym ). 2.1.13 cã C(xm − y0 + ym − x0 ; xm − y0 ) ®­êng ®i xÊu. Do ®ã cã: C(xm − x0 + ym − y0 ; xm − x0 ) − C(xm − x0 + ym − y0 ; xm − y0 ) ®­êng ®i ®Ñp tõ (x0 , y0 ) tíi (xm , ym ). §Þnh nghÜa 2.5.2 Sè Catalan thø n, ®­êng ®i ®Ñp tõ (1; 0) tíi (n; n − 1). Bµi to¸n 2.5.3 Chøng minh r»ng: kÝ hiÖu lµ Cn , ®­îc x¸c ®Þnh b»ng sè 1 C(2n − 2, n − 1) n Gi¶i: Theo bµi trªn thay x0 b»ng 1, y0 = 0, xm = m, ym = n − 1 ta cã: Cn = Cn = C(2n − 2; n − 1) − C(2n − 2; n) h n − 1i = C(2n − 2; n − 1) 1 − n 1 = C(2n − 2, n − 1) n 39 a) x > y (0, 0) tíi (n, n) tho¶ m·n: T×m sè ®­êng ®i tõ Bµi to¸n 2.5.4 t¹i tÊt c¶ c¸c ®iÓm nguyªn n»m trong ®­êng ®i hoÆc y>x t¹i tÊt c¶ c¸c ®iÓm nguyªn n»m trong ®­êng ®i . b) x ≥ y) t¹i tÊt c¶ c¸c ®iÓm nguyªn cã trªn ®­êng ®i. c) §­êng ®i kh«ng bao giê c¾t ngang qua ®­êng y = x. Gi¶i: a) Sè ®­êng ®i trong tr­êng hîp nµy b»ng hai lÇn sè ®­êng ®i ®Ñp tõ (1; 0) tíi (n; n − 1) do ®ã kÕt qu¶ lµ 2Cn b) Gäi A lµ ®iÓm (n, n). Gi¶ sö ®iÓm gèc O(0; 0) chuyÓn tíi ®iÓm O0 (−1; 0). Trong hÖ trôc to¹ ®é míi (trong hÖ trôc míi) tõ cò) tõ c) O tíi O0 (0; 0), O(1; 0) vµ A(n + 1, n). O tíi A chÝnh lµ Cn+1 b»ng sè ®­êng ®i (trong hÖ trôc A trong ®ã y ≤ x t¹i tÊt c¶ c¸c ®iÓm nguyªn cã trªn ®­êng ®i. B»ng phÐp ®èi xøng qua ®­êng y = x, Bµi to¸n 2.5.5 Gi¶ sö P vµ Q lµ hai øng cö viªn cña mét v¨n phßng. Gäi t­¬ng øng lµ sè phiÕu bÇu cña lu«n dÉn tr­íc Gi¶i: P vµ Q. P NÕu p > q, t×m x¸c suÊt ®Ó P Q trong suèt qu¸ tr×nh ®Õm phiÕu bÇu cö. Trong hÖ trôc to¹ ®é ®Ò c¸c, kÝ hiÖu tÝch luü cña c©u tr¶ lêi lµ sè l­îng ®­êng ®i b) tøc lµ 2Cn+1 tho¶ m·n gÊp ®«i sè l­îng ®­êng ®i ë ý p, q Sè ®­êng ®i ®Ñp vµ Q x vµ y t­¬ng øng lµ sè phiÕu bÇu t¹i giai ®o¹n nµo ®ã. Mäi ®­êng ®i tõ (0; 0) tíi (p, q) ®¹i diÖn cho tiÕn tr×nh cã thÓ cã cña qu¸ tr×nh bÇu cö vµ ng­îc l¹i. Ta cã sè ®­êng ®i cã thÓ cã lµ C(p + q, p). Sè ®­êng ®i thÓ hiÖn C(p + q − 1; p − 1) − C(p + q − 1, p) P lu«n dÉn ®Çu lµ (b»ng sè ®­êng ®i ®Ñp tõ (1, 0) tíi (p, q)) VËy x¸c xuÊt cÇn t×m lµ: C(p + q − 1; p − 1) − C(p + q − 1, p) p − q = C(p + q, p) p+q Bµi to¸n 2.5.6 (i) ui b»ng T×m sè d·y cã d¹ng < u1 , u2 , ..., u2n > tho¶ m·n: −1 hoÆc b»ng 1 víi mäi i. (ii) u1 + u2 + … + uk ≥ 0, víi 1 ≤ k ≤ 2n − 1 (iii) u1 + u2 + … + u2n = 0. Gi¶i: Ta quan t©m tíi mét ®­êng ®i tõ 40 (0; 0) tíi (n; n). §Æt ui ≡ (xi − xi−1 ) − (yi − yi−1 ), (i = 1, 2, …, 2n). NÕu ®­êng ®i nµy kh«ng bao giê v­ît lªn trªn ®­êng (i) ui b»ng y = x th× c¸c sè nguyªn ui tho¶ m·n: −1 hoÆc b»ng 1 víi mäi i = 1, 2, …, 2n. (ii) u1 + u2 + … + uk = xk − yk ≥ 0, víi 1 ≤ k ≤ 2n − 1 (iii) u1 + u2 + … + u2n = x2n − y2n = n − n = 0. VËy d·y ui (0; 0) (n; n) tíi tho¶ m·n 3 ®iÒu kiÖn (i) Mçi ai X¸c ®Þnh mét ®­êng ®i tõ tho¶ m·n kh«ng bao giê v­ît qu¸ ®­êng d·y tho¶ m·n yªu cÇu bµi to¸n lµ Bµi to¸n 2.5.7 (i), (ii), (iii). y = x. Do ®ã sè Cn+1 . T×m sè d·y cã d¹ng < a1 , a2 , ..., a2n+1 > tho¶ m·n: lµ mét sè nguyªn kh«ng ©m. (ii) a1 = a2n+1 = 0. (iii) ai+1 − ai Gi¶i: b»ng X©y dùng d·y k P −1 hoÆc b»ng 1 víi mäi i. ui tho¶ m·n: ui = ai+1 − ai (i = 1, 2, …, 2n). Ta ui (k = 0, 1, 2, …, 2n). Khi ®ã d·y ai tho¶ m·n 3 ®iÒu kiÖn i=1 (i), (ii), (iii) ë trªn th× ui tho¶ m·n 3 ®iÒu kiÖn (i), (ii), (iii) ë bµi 2.5.6. Do ak+1 = cã: ®ã kÕt qu¶ cÇn t×m lµ 2.6. Cn+1 . Chuyªn ®Ò 6: C¸c sè Stirling Trong tr­êng hîp nµy chóng ta lµm quen víi sè Stirling lo¹i lo¹i 2. 1, sè Stirling Nªu ®­îc vai trß cña sè Stirling trong c¸c bµi to¸n vÒ sù ph©n chia mét tËp hîp cho tr­íc thµnh hîp cña c¸c tËp con. §ång thêi chóng ta sÏ ®i t×m sè l­îng nghiÖm cña ph­¬ng tr×nh “x1 m, n nguyªn d­¬ng, xk + x2 + … + xm = n. lµ sè nguyªn kh«ng ©m, k = 1, 2, …m” Trong ®ã vµ mét sè bµi to¸n ph¸t triÓn tõ bµi to¸n nµy. Tr­íc hÕt ta lµm quen víi mét sè kh¸i niÖm. ∗) KÝ hiÖu [x]0 ≡ 1 vµ [x]n ≡ x(x − 1)(x − 2)…(x − n + 1) víi (i) (n = 1, 2, …) §Þnh nghÜa 2.6.1 HÖ sè cña xr trong [x]n 41 ®­îc hiÓu lµ sè Stirling lo¹i mét, s(n, r). ∞ P [x]n = s(n, r)xr , ký hiÖu Ta cã: s(n, r) = 0 nÕu r > n (ii) n=0 0 ∗) KÝ hiÖu [x] ≡ 1 vµ [x]n ≡ x(x+1)(x+2)…(x+n−1) víi (n = 1, 2, …) ∗) Sè c¸ch ph©n chia mét tËp hîp cã rçng ký hiÖu lµ S(n, m) n phÇn tö thµnh m tËp con kh«ng vµ ®­îc gäi lµ sè Stirling lo¹i hai. (S(0; 0) = 1; S(n; m) = 0 nÕu m > n) Ta cã thÓ chøng minh ®¼ng thøc truy håi sau: §Þnh lý 2.6.2 Chøng minh r»ng s(n + 1, r) = s(n, r − 1) − ns(n, r) Chøng minh: Theo ∞ X = r=0 ∞ X (iii) (i); [x]n+1 = (x − n)[x]n . Do ®ã tõ (ii) ta cã: r s(n + 1, r)x = x ∞ X r s(n, r)x − n ∞ X r=0 s(n, r)xr r=0 [s(n, r − 1) − ns(n, r)]xr r=0 B»ng ph­¬ng ph¸p c©n b»ng hÖ sè ta cã ngay ®iÒu ph¶i chøng minh. Bµi to¸n 2.6.3 T×m sè c¸ch ®Æt n vËt ph©n biÖt vµo m hép ph©n biÖt, theo thø tù tõ tr¸i qua ph¶i biÕt r»ng cã thÓ cho phÐp mét sè hép ®Ó trèng. ( Chó ý r»ng nÕu Gi¶i: m > n, Ýt nhÊt m − n hép ph¶i bá trèng). Gi¶ sö sè cÇn t×m lµ sù ph©n phèi vËt vµo hép VËt thø trÝ thø n f (n, m). Gi¶ thiÕt r»ng ®· cã f (n − 1, m) vµ mét n − 1 vËt ®ã lµ: mang i1 vËt vµo hép 1, i2 vËt vµo hép 2,…, im m sao cho ik ≥ 0 k = 1, 2, .., m) vµ i1 + i2 + … + im = n − 1. cã thÓ vµo hép k theo ik +1 c¸ch. (VÞ trÝ ®Çu tiªn vÒ bªn tr¸i, vÞ 2 tõ tr¸i qua ph¶i,…, vÞ trÝ thø ik + 1 tÝnh tõ tr¸i qua ph¶i). Do ®ã cã: (i1 + 1) + (i2 + 1) + … + (im + 1) = n − 1 + m c¸ch s¾p xÕp cho vËt thø n. VËy ta cã quan hÖ: f (n, m) = (n − 1 + m)f (n − 1, m) = (n + m − 1)(n + m − 2)…m = [m]n Bµi to¸n 2.6.4 Yªu cÇu t­¬ng tù bµi 2.6.3 tuy nhiªn thªm ®iÒu kiÖn m ≤ n vµ nh÷ng tr­êng hîp ®Ó trèng lµ kh«ng ®­îc phÐp. 42 Gi¶i: B©y giê mçi hép ®­îc ®Æt vµo ®ã mét vËt ®Çu tiªn ë phÝa bªn tr¸i. C«ng viÖc nµy cã thÓ lµm theo P (n, m) c¸ch. Do ®ã kÕt qu¶ cÇn t×m lµ: P (n, m).[m]n−m = n! m(m + 1)(m + 2)…(n − 1) (n − m)! = n!C(n − 1; m − 1) Tõ c¸c bµi to¸n 2.6.3 vµ 2.6.4 ta cã thÓ tÝnh ®­îc sè nghiÖm nguyªn cña mét ph­¬ng tr×nh tuyÕn tÝnh. NÕu Bµi to¸n 2.6.5 m vµ n lµ c¸c sè nguyªn d­¬ng. Chøng minh r»ng n [m] nghiÖm. n! c¸c sè nguyªn kh«ng ©m (kÕt qu¶ còng ®óng khi n = 0). x1 + x2 + … + xm = n cã ®óng Trong ®ã Bµi to¸n t­¬ng ®­¬ng víi cã bao nhiªu c¸ch ®Æt n vËt gièng nhau vµo ph­¬ng tr×nh Gi¶i: m hép ph©n biÖt (mét hép cã x1 vËt, mét hép cã x2 vËt,…, mét hép cã xk lµ xm ), vËt), cã thÓ cã hép kh«ng cã vËt nµo. NÕu chóng ta t¹m thêi lµm cho c¸c vËt trë nªn ph©n biÖt b»ng c¸ch gi¸n nh·n cho chóng lµ l1 , l2 , …, lm th× theo bµi 2.6.3 cã [m]n c¸ch s¾p xÕp. Tuy nhiªn trë l¹i bµi to¸n nµy, nh÷ng sù s¾p xÕp mµ chØ kh¸c nhau bëi nh÷ng nh·n d¸n trªn n vËt th× ®­îc coi lµ mét nghiÖm cña ph­¬ng tr×nh trªn. Do ®ã c©u tr¶ lêi lµ: [m]n = C(n + m − 1, m − 1) n! nghiÖm tho¶ m·n. Tõ kÕt qu¶ cña bµi to¸n 2.6.3 ta nhËn ®­îc kÕt qu¶ sau: Bµi to¸n 2.6.6 m gåm A = {ai : i = 1, 2, …, m} ch÷ c¸i ®­îc s¾p xÕp thø tù nh­ sau: θ1 θ2 …θm nÕu Gi¶ sö lµ mét b¶ng ch÷ c¸i bao a1 < a2 < ... < am . Mét tõ t¹o ra tõ b¶ng ch÷ c¸i nµy ®­îc gäi lµ mét tõ t¨ng (cã ®é dµi θ1 ≤ θ2 ≤ ... ≤ θn . H·y chøng minh sè c¸c tõ t¨ng cã ®é dµi n n) lµ C(n + m − 1, m − 1). Gi¶i: Mét tõ t¨ng cã ®é dµi ch÷ c¸i a2 ,..., xm n sÏ bao gåm sau ®ã lµ ch÷ c¸i am x1 tho¶ m·n sau ®ã lµ x2 xk ≥ 0(k = 1, 2, ..., m) vµ ch÷ c¸i a1 , x1 +x2 +...+xm = n. VËy theo bµi 2.6.4 sè c¸c tõ t¨ng lµ C(n+m−1, m−1). 43 §Þnh nghÜa 2.6.7 f Mét hµm cã tËp x¸c ®Þnh lµ M = {β1 , β2 , ..., βm }, f tËp gi¸ trÞ lµ: N = {α1 , α2 , ..., αn } lµ mét hµm t¨ng (tõ N tíi M) vµ nÕu f (αi ) ≤ f (αj ) nÕu αi < αj Bµi to¸n 2.6.8 Gi¶i: X¸c ®Þnh sè l­îng hµm t¨ng nh­ trong ®Þnh nghÜa trªn. Chóng ta cã thÓ gi¶ thiÕt r»ng α1 < α2 < ... < αn N Khi ®ã, mét hµm t¨ng tõ β1 , x2 sè α tiÕp theo thµnh x1 + x2 + ... + xm = n bÊt kú mét tËp hîp t¨ng tõ N tíi xk vµ tíi M sÏ biÕn β2 ,..., xm xk β1 ≤ β2 ≤ ... ≤ βm sè α x1 sè α ®Çu tiªn ë trªn thµnh cuèi cïng thµnh lµ sè nguyªn kh«ng ©m, βm trong ®ã k = 1, 2, ..., m. VËy, tho¶ m·n nh÷ng ®iÒu kiÖn trªn ®Òu x¸c ®Þnh mét hµm M . Theo bµi trªn, kÕt qu¶ cÇn t×m lµ C(n + m − 1, m − 1). Bµi to¸n 2.6.9 Cho tr­íc λ1 , λ2 , ..., λm nghiÖm nguyªn cña ph­¬ng tr×nh: víi vµ lµ c¸c sè nguyªn kh«ng ©m. T×m sè x1 + x2 + ... + xm = n sao cho x i ≥ λi , i = 1, 2, ..., m. Gi¶i: Víi mçi tr×nh y1 + y2 + ... + ym = n − λ; yi ≥ 0 (i = 1, 2, ..., m). i lÊy xi = λi + yi vµ viÕt λ = λ1 + λ2 + ... + λm . Ta cã ph­¬ng ∗) NÕu λ < n th× kÕt qu¶ cÇn t×m lµ: C(n − λ + m − 1, m − 1) ∗) NÕu λ = n th× ta cã ph­¬ng tr×nh: y1 + y2 + ... + ym = 0, yi ≥ 0 (i = 1, 2, ..., m) cã nghiÖm duy nhÊt(0, 0, ..., 0) do ®ã ph­¬ng tr×nh ban ®Çu cã nghiÖm duy nhÊt λ1 , λ2 , ..., λm . ∗) NÕu λ > n hiÓn nhiªn ph­¬ng tr×nh ®· cho kh«ng cã nghiÖm nµo tho¶ m·n. Bµi to¸n 2.6.10 T×m sè c¸ch chän ra r sè nguyªn ph©n biÖt tõ n sè nguyªn d­¬ng ®Çu tiªn sao cho trong sù lùa chän ®ã kh«ng cã chøa hai sè nguyªn liªn tiÕp. Gi¶i: S¾p xÕp n sè nguyªn d­¬ng ®Çu tiªn thµnh mét hµng theo thø tù t¨ng b¾t ®Çu tõ 1. NÕu mét sè ®­îc chän th× ®Æt biÓu t­îng Y 44 d­íi sè ®ã, nÕu kh«ng chän th× ®Æt biÓu t­îng N N Y ®øng tr­íc biÓu t­îng biÓu t­îng t­îng N Y d­íi sè ®ã. Gäi ®Çu tiªn; ®Çu tiªn vµ biÓu t­îng Y gi÷a biÓu t­îng sè ®øng sau biÓu t­îng Y x1 lµ sè l­îng sè cã biÓu t­îng x2 lµ sè l­îng sè cã biÓu t­îng N Y thø hai,…, xr gi÷a lµ sè l­îng sè cã biÓu thø r − 1 vµ biÓu t­îng thø r; vµ xr+1 lµ sè l­îng thø r. Khi ®ã cã mét t­¬ng øng mét – mét gi÷a nh÷ng sù lùa chän chÊp nhËn ®­îc víi nh÷ng nghiÖm nguyªn cña ph­¬ng tr×nh: x1 + x2 + … + xr+1 = n − r Do ®ã theo bµi víi x1 ≥ 0, x2 ≥ 1, …, xr ≥ 1, xr+1 ≥ 0. 2.6.9 kÕt qu¶ cÇn t×m lµ C(n − r + 1, r). T×m sè c¸ch chän ra Bµi to¸n 2.6.11 r sè nguyªn d­¬ng tõ n sè nguyªn d­¬ng ®Çu tiªn sao cho kh«ng cã hai sè nguyªn liªn tiÕp nµo xuÊt hiÖn trong sù lùa chän vµ sù lùa chän kh«ng cã ®ång thêi c¶ hai sè Gi¶i: Tr­êng hîp mét biÓu t­îng Y 1 vµ n. 1: Sù lùa chän cã sè 1. Theo ký hiÖu bµi 2.6.8, x1 = 0 (cã d­íi sè 1) vµ xr+1 ≥ 1, (cã mét biÓu t­îng N d­íi sè n). Do ®ã chóng ta cã ph­¬ng tr×nh: x2 + x3 + … + xr+1 = n − r Suy ra ta cã N 2: d­íi sè Sù lùa chän kh«ng cã sè 1. Ta cã x1 ≥ 1 (cã mét biÓu 1). Do ®ã chóng ta cã ph­¬ng tr×nh: x1 + x2 + … + xr+1 = n − r Suy ra ta cã x2 ≥ 1, x3 ≥ 1, …, xr+1 ≥ 1. C(n − r − 1, r − 1) c¸ch lùa chän. Tr­êng hîp t­îng víi C(n − r, r) víi x1 ≥ 1, x2 ≥ 1, …, xr+1 ≥ 0. c¸ch lùa chän. VËy tæng sè sù lùa chän tho¶ m·n lµ: n C(n − r − 1, r − 1) r ¸nh tõ tËp n phÇn tö tíi C(n − r − 1, r − 1) + C(n − r, r) = Bµi to¸n 2.6.12 phÇn tö b»ng Gi¶i: Chøng minh r»ng sè toµn m m!S(n, m). LÊy c¸c tËp hîp X = {x1 , x2 , …, xm } X = X1 ∪ X2 ∪ … ∪ Xm vµ Y = {y1 , y2 , …, ym }. lµ mét sù ph©n chia bÊt kú cña X thµnh kh«ng rçng. Khi ®ã, bÊt kú mét t­¬ng øng mét – mét nµo gi÷a x¸c ®Þnh mét t­¬ng øng tõ vËy. Cã tËp S(n, m) X tíi yi Gäi m tËp con vµ Xj ®Òu Y , cã chÝnh x¸c m! toµn ¸nh mét – mét nh­ c¸ch ph©n chia cña tËp 45 X. VËy chóng ta cã: m!S(n, m) toµn ¸nh tho¶ m·n. Bµi to¸n 2.6.13 §Õm sè c¸ch ph©n phèi n vËt ph©n biÖt vµo m hép nÕu tho¶ m·n: a) m hép gièng nhau vµ mçi hép ph¶i cã Ýt nhÊt mét vËt. b) m hép gièng nhau vµ cho phÐp cã hép trèng. c) C¸c hép ®Òu ph©n biÖt vµ mçi hép ph¶i cã Ýt nhÊt mét vËt. Gi¶i: a) S(n, m). b) S(n, 1) + S(n, 2) + … + S(n, m). c) m!S(n, m). Bµi to¸n 2.6.14 Chøng minh r»ng: a)S(n, 2) = 2n−1 − 1 b)S(n, n − 1) = C(n, 2). Gi¶i: a) theo bµi 2.1.10 b) XÐt mét sù ph©n chia tËp X chøa thµnh n − 1 tËp con trong ®ã cã mét tËp con 2 phÇn tö vµ n−2 tËp con cßn l¹i mçi tËp chøa 1 phÇn tö. Cã S(n, n−1) c¸ch ph©n chia nh­ thÕ. Tuy nhiªn ta cã thÓ nh×n theo c¸ch kh¸c, tËp hîp gåm 2 phÇn tö cã thÓ t¹o ra theo C(n, 2) c¸ch. Do ®ã ta cã ®iÒu ph¶i chøng minh. Bµi to¸n 2.6.15 Chøng minh r»ng: S(n + 1, m) = S(n, m − 1) + mS(n, m) Gi¶i: Gäi X ≡ {x1 , x2 , …, xn } vµ S(n + 1, m) c¸ch ph©n chia tËp X 0 A ≡ {xn+1 }, X 0 ≡ X ∪ A. thµnh Khi ®ã cã m tËp con kh«ng rçng. §Ó cã mét sù ph©n chia nh­ vËy ta cã thÓ lµm theo mét trong hai c¸ch. C¸ch ®ã vµ 1: Ph©n chia X thµnh m−1 tËp con kh«ng rçng. (m−1) tËp con nµo A t¹o thµnh mét sù ph©n chia cña X 0 thµnh m tËp con. Cã S(n, m − 1) c¸ch ph©n chia. C¸ch 2: Ph©n chia X thµnh m tËp con kh«ng rçng. Sau ®ã thªm xn+1 bÊt kú tËp con nµo trong sè c¸c tËp con ®ã. Ta cã ®­îc sù ph©n chia cña 46 vµo X0 tho¶ m·n. Cã cã S(n, m) c¸ch ph©n chia cña X vµ m c¸ch thªmxn+1 vµo do ®ã mS(n, m) c¸ch ph©n chia lo¹i nµy. VËy ta cã S(n + 1, m) = S(n, m − 1) + mS(n, m). Tõ kÕt qu¶ bµi HÖ qu¶ 2.6.16 1; S(n, m) = 0 víi m > n. 2.6.14 vµ ®iÒu kiÖn S(n, 1) = S(n, n) = Ta nhËn ®­îc tam gi¸c c¸c sè Stirling lo¹i hai nh­ sau: 2.7. n, m 1 2 3 4 5 6 1 1 2 1 1 3 1 3 1 4 1 7 6 1 5 1 15 25 10 1 6 1 31 90 65 15 1 7 1 63 301 350 140 21 8 … … … … … … 7 1 Chuyªn ®Ò 7: Ho¸n vÞ vµ tæ hîp tæng qu¸t Ho¸n vÞ tæng qu¸t th­êng ¸p dông vµo bµi to¸n s¾p xÕp c¸c vËt trong ®ã cã thÓ cã sù lÆp l¹i. Cßn tæ hîp tæng qu¸t lµ c«ng cô m¹nh trong bµi to¸n vÒ sù ph©n phèi c¸c vËt vµo c¸c “hép ” mµ sè l­îng vËt trong mçi ” hép ” cã thÓ qui ®Þnh tr­íc. Sau ®©y lµ mét bµi to¸n dïng ho¸n vÞ vµ tæ hîp tæng qu¸t. §Þnh lý 2.7.1 (§Þnh lý ®a thøc) Sè h¹ng tæng qu¸t trong khai triÓn (x1 + x2 + … + xk )n lµ: C(n; n1 , n2 , …nk )xn1 1 xn2 2 …xnk k Chøng minh: (n1 + n2 + … + nk = n) Ta cã, sè c¸ch ph©n chia cã thø tù cña tËp hîp 47 S = {(x1 + x2 + … + xk )1 , (x1 + … + xk )2 , …, (x1 + … + xk )n } vµo mét ng¨n cã n1 phÇn x1 ,…, mét ng¨n cã nk tö, mçi lÇn mét phÇn tö xk phÇn tö, mçi lÇn mét phÇn tö lµ: C(n; n1 , n2 , …, nk ) Tõ ®ã nhËn ®­îc ®iÒu ph¶i chøng minh. §Æt HÖ qu¶ 2.7.2 Chøng n1 +n2 +…+nk =n minh: Theo ®Þnh lý 2.7.1 ta cã Bµi to¸n 2.7.3 2 n©u, 3 tr¾ng, thµnh hµng Gi¶i: i) C(n; n1 , n2 , …, nk ) khi ®ã S = k n P S= Cã Cã 3 S = (1 + 1 + … + 1)n = k n 20 viªn bi cïng cì nh­ng kh¸c mµu nhau. (1 ®á, 2 xanh, vµng, 4 cam, 5 ®en) trong mét b×nh. T×m sè c¸ch s¾p xÕp 5 viªn bi lÊy ra tõ b×nh ®· cho. 7 tr­êng hîp ph©n biÖt x¶y ra: TÊt c¶ 5 viªn lÊy ra cïng mµu. Cã mét kh¶ n¨ng x¶y ra lµ cïng mµu ®en suy ra cã 5 viªn Êy 1 c¸ch s¾p xÕp chóng. ii) ChÝnh x¸c cã 4 viªn cïng mµu. Sè c¸ch lÊy ra mét mÉu 5 viªn bi lo¹i nµy lµ C(2, 1).C(6, 1) = 21. øng víi mçi mÉu cã P (5; 4, 1) = 5 sù s¾p xÕp. Do ®ã tæng sè c¸ch s¾p xÕp lµ: (21).(5) = 60. iii) 3 viªn cïng mµu vµ 2 viªn cïng mét mµu kh¸c. Cã C(4, 1).C(5, 1) = 20 mÉu thuéc lo¹i nµy. Mçi mÉu cã tæng sè c¸ch s¾p xÕp lµ: P (5; 3, 2) = 10 c¸ch s¾p xÕp. Do ®ã 20.10 = 200 c¸ch. iv) 3 viªn cïng mµu cßn hai viªn cßn l¹i thuéc 2 mµu kh¸c nhau vµ kh¸c mµu 3 viªn kia. Sè mÉu thuéc lo¹i nµy lµ: C(4; 1).C(6; 2) = 60 mçi mÉu cã P (5; 3, 1, 1) = 20 c¸ch s¾p xÕp. Suy ra cã tÊt c¶: 60.20 = 1200 c¸ch s¾p xÕp lo¹i nµy. v) Hai viªn cïng mµu, hai viªn cïng mét mµu kh¸c vµ mét viªn thuéc lo¹i mµu thø mÉu cã 3. Sè mÉu thuéc lo¹i nµy lµ P (5; 2, 2, 1) = 30 sù s¾p xÕp. C(6; 2).C(5; 1) = 75 vµ mçi Tæng sè c¸ch s¾p xÕp ë ®©y lµ: (75).(30) = 2250 c¸ch. vi) 2 viªn cïng mét mµu vµ 3 viªn cßn l¹i cã 3 mµu kh¸c nhau vµ kh¸c mµu 2 viªn kia. Sè mÉu lµ: C(6; 1).C(6; 3) = 120. Mèi mÉu cã P (5; 2, 1, 1, 1) = 48 60 sù s¾p xÕp. VËy cã (120).(60) = 7200 sù s¾p xÕp. vii) 5 viªn cã 5 mµu kh¸c nhau. Cã C(7; 5) = 21 mÉu, mçi mÉu cã P (5; 1, 1, 1, 1, 1) = 120 sù s¾p xÕp. VËy cã: (21).(120) = 2520 c¸ch s¾p xÕp thuéc lo¹i nµy. Tãm l¹i, sè c¸ch s¾p xÕp tho¶ m·n yªu cÇu lµ: 1 + 60 + … + 2520 = 13431 c¸ch Bµi to¸n 2.7.4 Chøng minh r»ng nÕu m vµ n lµ c¸c sè nguyªn d­¬ng th× (mn)! chia hÕt cho (m!)n Gi¶i: Ta cã (mn)! P (mn; m, m, …, m) = | {z } (m!)n lµ mét sè nguyªn. Suy ra (mn)! n−sè h¹ng chia hÕt cho (m!)n Bµi to¸n 2.7.5 Mét h¹t trong hÖ trôc to¹ ®é §Ò c¸c ®­îc tù do di chuyÓn tõ bÊt kú ®iÓm cã to¹ ®é nguyªn nµy tíi ®iÓm cã to¹ ®é nguyªn l©n cËn bÊt kú. T×m sè c¸ch mµ h¹t ®ã b¾t ®Çu xuÊt ph¸t tõ ®iÓm gèc vµ quay trë vÒ ®iÓm 2n ®¬n vÞ. gèc sau khi ®i mét ®­êng ®i cã ®é dµi Gi¶i: Mét ®­êng ®i cã ®é dµi p b­íc sang ph¶i, q 2n cña ®iÓm ®ã ph¶i bao gåm p b­íc sang tr¸i, b­íc lªn trªn vµ q b­íc xuèng d­íi (2p + 2q = 2n). Do ®ã kÕt qu¶ mong muèn lµ: X P (2n; p, p, q, q) p+q=n Bµi to¸n 2.7.6 Gi¶i: ChØ ra r»ng (n!)! chia hÕt cho (n!)(n−1)! . Chóng ta quan t©m tíi mét ®a tËp cña dÊu hiÖu, cø n! phÇn tö. Trong ®ã cã (n − 1)! n phÇn tö thuéc mét dÊu hiÖu. §a tËp nµy cã thÓ s¾p xÕp theo: (n!)! P (n!; n, n, …, n ) = | {z } (n!)(n−1)! (n−1)!−sè h¹ng c¸ch. Râ rµng P (n!; n, n, …, n ) lµ mét sè nguyªn nªn ta cã ®iÒu ph¶i chøng | {z } (n−1)!−sè h¹ng minh. 49 2.8. Chuyªn ®Ò 8: Nguyªn lý bao hµm vµ lo¹i trõ Nguyªn lý bao hµm vµ lo¹i trõ cã øng dông nhiÒu trong chøng minh c¸c c«ng thøc cña tæ hîp, ®¹i sè. Ngoµi ra ta th­êng dïng nguyªn lý nµy trong c¸c bµi to¸n ®Þnh l­îng t­¬ng tù nh­ bµi Trong mét ký tóc x¸ cã Bµi to¸n 2.8.1 (A); 2.8.1 , 2.8.2, 2.8.9… 12 sinh viªn tham gia häc héi ho¹ 20 sinh viªn tham gia häc sinh häc (B ), 20 sinh viªn tham gia häc ho¸ häc (C ), 8 sinh viªn tham gia häc kÞch (D). Cã 5 sinh viªn tham gia c¶ A vµ B ; 7 sinh viªn tham gia c¶ A vµ C ; 4 sinh viªn tham gia c¶ A vµ D; 16 sinh viªn tham gia c¶ gia c¶ C vµ vµ C ; 4 sinh viªn tham gia c¶ B vµ D; 3 sinh viªn tham D. Cã 3 sinh viªn tham gia c¶ A, B, C ; 2 sinh viªn tham gia c¶ vµ A, B, D; 2 B sinh viªn tham gia c¶ B, C vµ D; 3 sinh viªn tham gia c¶ A, C D. Cuèi cïng 2 sinh viªn tham gia c¶ 4 líp häc. BiÕt r»ng cã71 sinh viªn trong ký tóc x¸ kh«ng tham gia bÊt kú mét kho¸ häc nµo. T×m tæng sè sinh viªn trong ký tóc x¸. Gi¶i: Gäi N lµ tæng sè sinh viªn trong ký tóc x¸ th×: 71 = N − S1 + S2 − S3 + S4 trong ®ã: S1 = 12 + 20 + 20 + 8 = 60 S2 = 5 + 7 + 4 + 16 + 4 + 3 = 39 S3 = 3 + 2 + 2 + 3 = 10 S4 = 2 Suy ra N = 100 Bµi to¸n 2.8.2 trong ®ã Gi¶i: T×m sè nghiÖm nguyªn cña ph­¬ng tr×nh: a + b + c + d = 17 1 ≤ a ≤ 3; 2 ≤ b ≤ 4; 3 ≤ c ≤ 5; 4 ≤ d ≤ 6 §Æt a = 1 + α; b = 2 + β; c = 3 + γ; d = 4 + δ . Ph­¬ng tr×nh ®· cho trë thµnh ph­¬ng tr×nh: 0 ≤ α, β, γ, δ ≤ 2 α + β + γ + δ = 7, 50 Gäi X lµ tËp hîp tÊt c¶ c¸c nghiÖm nguyªn kh«ng ©m cña ph­¬ng tr×nh: α + β + γ + δ = 7 vµ gäi A lµ tËp con cña X tho¶ m·n β ≥ 3, C lµ tËp con tho¶ m·n tho¶ m·n α ≥ 3, B lµ tËp con γ ≥ 3, D lµ tËp con tho¶ m·n δ ≥ 3. Theo c«ng thøc Sieve: n(A0 ∩ B 0 ∩ C 0 ∩ D0 ) = n(X) − S1 + S2 − S3 + S4 Theo bµi 2.6.9 ta cã: n(X) = C(10, 3); n(A) = n(B) = n(C) = n(D) = C(7, 3) n(A ∩ B) = n(A ∩ C) = · · · = n(C ∩ D) = C(4, 3) n(A ∩ B ∩ C) = n(A ∩ B ∩ D) = · · · = n(B ∩ C ∩ D) = 0 n(A ∩ B ∩ C ∩ D) = 0 Do ®ã n(X) = 120 S1 = C(4, 1).C(7, 3) = 140 S2 = C(4, 2).C(4, 3) = 24 S3 = 0; S4 = 0 KÕt qu¶ cÇn t×m lµ: n(A0 ∩ B 0 ∩ C 0 ∩ D0 ) = 120 − 140 + 24 = 4 Bµi to¸n 2.8.3 Chøng minh r»ng sè Stirling lo¹i hai cã thÓ ®­îc ®¸nh gi¸ tõ c«ng thøc bao hµm vµ lo¹i trõ sau: m!S(n, m) = mn −C(m, 1)(m−1)n +C(m, 2)(m−2)n −…+(−1)m−1 C(m, m− 1).1n Gi¶i: Gäi M Goi Ai lµ tËp hîp c¸c ¸nh x¹ tõ X lµ tËp con cña yi , (i = 1, 2, …, m). M bao gåm c¸c ¸nh x¹ mµ trong tËp gi¸ trrÞ kh«ng cã Chóng ta cã: (k = 1, 2, …, m − 1). = {x! , x2 , …, xn } tíi Y = {y1 , y2 , …, ym }. n(M ) = mn vµ Sk = C(m, k).(m − k)n Theo c«ng thøc Sieve ta cã: Sè ¸nh x¹ thuéc tËp gi¸ trÞ cña nã chÝnh b»ng Y lµ: mn − C(m, 1)(m − 1)n + … + (−1)m−1 C(m; m − 1).1n 51 M mµ MÆt kh¸c, kÕt qu¶ nµy chÝnh b»ng sè toµn ¸nh tõ bµi X vµo Y b»ng m!S(n, m) (2.6.10). Suy ra ®iÒu ph¶i chøng minh. Bµi to¸n 2.8.4 T×m c¸c ho¸n vÞ cña c¸c ch÷ sè tõ 1 ®Õn 9 mµ trong ®ã: a) Kh«ng chøa c¸c “khèi” 23; 45 vµ 678; b) Kh«ng chøa c¸c “khèi” 34; 45 vµ 738. Gi¶i: Gäi X lµ tËp hîp tÊt c¶ c¸c ho¸n vÞ cña 9 ch÷ sè tõ 1 ®Õn 9. Khi ®ã n(X) = 9! a) Gäi A, B, C vµ lµ c¸c tËp con cña tËp X t­¬ng øng chøa c¸c khèi 23; 45; 678. Ta cã: n(A) = n(B) = 8! n(C) = n(A ∩ B) = 7! n(A ∩ C) = n(B ∩ C) = 6! n(A ∩ B ∩ C) = 5! KÕt qu¶ cÇn t×m lµ: 9! − (8! + 8! + 7!) + (7! + 6! + 6!) − 5! = 283560 b) Gäi A, B, C vµ lµ c¸c tËp con cña tËp X t­¬ng øng chøa c¸c khèi 34; 45; 738. Khi ®ã: n(A) = n(B) = 8! n(C) = n(A ∩ B) = 7! n(B ∩ C) = 6! n(A ∩ C) = n(A ∩ B ∩ C) = 0 KÕt qu¶ cÇn t×m lµ 9! − (8! + 8! + 7!) + (7! + 0 + 6!) − 0 = 282960 Bµi to¸n 2.8.5 cã ­íc lµ T×m sè c¸c sè nguyªn d­¬ng nhá h¬n 3 hoÆc 5 hoÆc 7. 52 601 tho¶ m·n kh«ng Gi¶i: Gäi vµ C lµ c¸c tËp con 3, 5 vµ 7. Ta cã:  600   600  h 600 i S1 = n(A) + n(B) + n(C) = + + = 405. 3 5 7 600  h 600 i h 600 i + + = 85. S2 = n(A ∩ B) + n(A ∩ C) + n(B ∩ C) = 15 21 35 600 =5 S3 = n(A ∩ B ∩ C) = 105 cña VËy X X = {1, 2, …, 600} th× n(X) = 600. Gäi A, B t­¬ng øng chøa c¸c sè chia hÕt cho n(A0 ∩ B 0 ∩ C 0 ) = 600 − 405 + 85 − 5 = 275 π(n) ≡ §Þnh nghÜa 2.8.6 d­¬ng sè c¸c sè nguyªn tè kh«ng v­ît qu¸ sè nguyªn n. §Þnh lý 2.8.7 Chøng minh π(n) = n − 1 + r − S1 + S2 + … + (−1)r Sr , trong ®ã r lµ sè c¸c sè nguyªn tè kh«ng v­ît qu¸ Chøng minh: qu¸ √ n. X n. X = {2, 3, …, n} vµ r lµ sè c¸c sè nguyªn tè kh«ng v­ît √ 2 = p1 < p2 < · · · < pr ≤ n < pr+1 . Khi ®ã, gäi Ai lµ Gäi Tøc lµ: tËp con cña √ chøa c¸c sè chia hÕt cho S1 = hni p1 + hni p2 pi (i = 1, 2, .., r). Ta cã + ... + hni pr = r h i X n i=1 pi Vµ tæng qu¸t Si = h X 1≤i1 . 2 A = {a1 , a2 , …, an } ∈ N ∗ vµ sè nguyªn d­¬ng m sao BiÕt r»ng sè d­ trong phÐp chia c¸c phÇn tö cña A cho m lµ kh¸c nhau ®«i mét. Chøng minh r»ng víi mçi k ∈ Z, thiÕt kh¸c nhau) sao cho sè tån t¹i ai + aj − k i, j ∈ {1, 2, …, n} chia hÕt cho (i, j kh«ng nhÊt m. H­íng gi¶i: Sö dông nguyªn lý Dirichlet. n ∈ N ∗ , chøng minh ®¼ng thøc: n P P 2k 1 n + 1 n+1 = n+1 . . C(n, k) 2 k k=1 k=0 Bµi 3.10 Cho H­íng gi¶i: Quy n¹p vµ biÕn ®æi tæ hîp. Bµi 3.11 Cho k ∈ [−n, n] P (x) ∈ R[x] th× cã bËc | P (x) |≤ 1.Chøng ≤ 2n. BiÕt r»ng víi mçi sè nguyªn minh r»ng víi mäi x ∈ [−n, n] th× | P (x) |≤ 22n H­íng gi¶i: Dïng ®a thøc néi suy Lagrange vµ biÕn ®æi tæ hîp. Bµi 3.12 Cho c¸c sè nguyªn : xn + a1 xn−1 + … + an . x0 < x1 < ... < xn vµ cho ®a thøc P (x) = P (xj ), j = 0, 1, .., n n! lu«n tån t¹i Ýt nhÊt mét sè cã gi¸ trÞ tuyÖt ®èi kh«ng nhá h¬n . 2n Chøng minh r»ng trong c¸c sè H­íng gi¶i : Gièng bµi 3.11. 61 T×m tÊt c¶ c¸c sè nguyªn d­¬ng k tháa m·n ®iÒu kiÖn : NÕu Bµi 3.13 F (x) ∈ Z(x) sao cho 0 ≤ F (c) ≤ k víi mäi c ∈ {0, 1, .., k + 1} th× F (0) = F (1) = ... = F (k + 1). H­íng gi¶i: Sö dông nguyªn lý Dirichlet. (1.x + 2.x2 + ... + n.xn )2 = a0 + a1 x + ...a2n x2n . Chøng n(n + 1)(5n2 + 5n + 2) minh r»ng an+1 + an+2 + ... + a2n = . 24 Bµi 3.14 Gi¶ sö : H­íng gi¶i : BiÕn ®æi tæ hîp. Bµi 3.15 (bn ) Cho P (x) ∈ Z[x] x¸c ®Þnh nh­ sau: d ∈ N∗ sao cho víi mçi x ∈ N∗ b1 = 1, bk+1 = P (bk ), ∀k ≥ 1. lu«n tån t¹i Ýt nhÊt mét sè h¹ng cña d·y minh r»ng: ta cã P (x) > x. D·y BiÕt r»ng víi mçi (bn ) chia hÕt cho d. Chøng P (x) = x + 1, ∀x ∈ N ∗ . H­íng gi¶i: Ph¶n chøng vµ dïng nguyªn lý Dirichlet. p1 , p2 , …, pn ∈ [0, 1]. Chøng minh r»ng bÊt ph­¬ng tr×nh: 1 1 1 1 ≤ 8n(1 + + + … + ) cã nghiÖm thuéc [0, 1]. 3 5 2n − 1 i=0 | x − pi | Bµi 3.16 n P Cho n sè H­íng gi¶i: Sö dông nguyªn lý Dirichlet. [n/2] P ∗ (C(n, k) − C(n, k − 1))2 . Chøng minh Bµi 3.17 Cho n ∈ N , ®Æt Sn = k=0 r»ng Sn = 1 .C(2n, n). n+1 H­íng gi¶i : BiÕn ®æi tæ hîp. Bµi 3.18 thuéc vµo mµ Cho c¸c sè thùc α1 , α2 , …, αn α1 , α2 , …, αn . Chøng minh r»ng tån t¹i sè c phô sao cho cã v« sè bé c¸c sè | α1 m1 + … + αn mn |< c . | m1 | +...+ | mn |n−1 (m1 , m2 , ..., mn ) ∈ Z n H­íng gi¶i : Dïng qui t¾c nh©n vµ nguyªn lý Dirichlet. Bµi 3.19 Cho c¸c tËp hîp {1, 2, ..., 14}. M = {1, 2, ..., 27} vµ A = {a1 , ..., ak } ⊂ Cã tÝnh chÊt sau: Mçi phÇn tö cña M lµ mét phÇn tö cña A hoÆc lµ tæng cña hai phÇn tö (kh«ng nhÊt thiÕt ph©n biÖt) cña A. T×m gi¸ trÞ nhá nhÊt cña k. H­íng gi¶i : Dïng tæ hîp vµ chøng minh ph¶n chøng ®Ó cã kÕt qu¶ gi¸ trÞ nhá nhÊt cña k b»ng 8. 62 Bµi 3.20 Cho hÖ ph­¬ng tr×nh gåm q = 2p Èn:    a11 x1 + ... + a1q xq = 0.    ..............................     ap1 x1 + ... + apq xq = 0. trong ®ã aij ∈ {−1, 0, 1}. Chøng minh r»ng tån t¹i nghiÖm (x1 , ..., xq ) kh¸c (0, 0, ..., 0), xj ∈ Z vµ | xj |≤ q, ∀j = 1, 2, ..., q . H­íng gi¶i : Dïng qui t¾c nh©n vµ nguyªn lý Dirichlet. Bµi 3.21 Cho tËp hîp M gåm 2002 sè nguyªn d­¬ng, mçi sè chØ cã ­íc nguyªn tè kh«ng v­ît qu¸ 23. Chøng minh r»ng tån t¹i 4 sè ph©n biÖt trong M cã tÝch lµ lòy thõa bËc 4 cña mét sè nguyªn. H­íng gi¶i: Nguyªn lý Dirichlet. Bµi 3.22 Cho tËp hîp A gåm n nguyªn tè ph©n biÖt vµ M lµ tËp gåm n+1 sè tù nhiªn ph©n biÖt sao cho mçi sè trong M ®Òu kh«ng lµ sè chÝnh ph­¬ng vµ chØ cã ­íc nguyªn tè thuéc A. Chøng minh r»ng cã thÓ chän ra trong M mét sè cã tÝch lµ mét sè chÝnh ph­¬ng. H­íng gi¶i: Nguyªn lý Dirichlet. Bµi 3.23 Cho S = {1, 2, 3, ..., 100} vµ P lµ tËp c¸c tËp con cña S mµ |T | = 49. Víi mçi T ∈ P , ta ®¸nh sè mét c¸ch ngÉu nhiªn, c¸c sè lÊy tõ tËp S . Chøng minh r»ng tån t¹i tËp con M cña S cã sè phÇn tö lµ 50 vµ víi mçi x ∈ M , tËp M {x} kh«ng ®­îc ®¸nh sè bëi x. H­íng gi¶i: Nguyªn lý Dirichlet. Bµi 3.24 T« mµu c¸c « cña b¶ng 4 x 7 bëi hai mµu: ®en, tr¾ng. Chøng minh r»ng víi mäi c¸ch t« lu«n tån t¹i mét h×nh ch÷ nhËt cã c¸c c¹nh n»m trªn ®­êng l­íi sao cho 4 « ë 4 gãc cïng mµu. H­íng gi¶i: Nguyªn lý Dirichlet. Bµi 3.25 XÐt b¶ng « vu«ng 4 x 4. §iÒn vµo mçi « mét sè 1 hoÆc -1 sao cho tæng c¸c sè trong mçi hµng vµ tæng c¸c sè trong mçi cét b»ng 0. Hái cã bao nhiªu c¸ch? 63 §¸p ¸n: 90 c¸ch. Bµi 3.26 L­íi « vu«ng n x n, trong ®ã n lµ sè nguyªn d­¬ng. Mçi nót l­íi ta t« mét trong hai mµu: xanh hoÆc ®á sao cho mçi h×nh vu«ng ®¬n vÞ cã hai ®Ønh mµu ®á vµ hai ®Ønh mµu xanh. Hái cã bao nhiªu c¸ch? 2n+2 − 2 c¸ch. §¸p ¸n: Bµi 3.27 Cho n lµ sè nguyªn d­¬ng. KÝ hiÖu Zn = {0, 1, 2, ..., n − 1}. XÐt c¸c tËp: An = {(a, b, c) : a, b, c ∈ Zn , a < b < c, a + b + c ≡ 0(modn)} , Bn = {(a, b, c) : a, b, c ∈ Zn , a ≤ b ≤ c, a + b + c ≡ 0(modn)} a) Chøng minh r»ng b) TÝnh |Bn | = |An | + n. |An |. H­íng gi¶i: b) Dïng so s¸nh ®Ó chøng minh |An+3 | = |Bn |. Suy ra |An+3 | = |An | + n. Tõ ®ã tÝnh ®­îc |An |. Bµi 3.28 Cho tËp X = {1, 2, ..., 2000}. mµ tæng c¸c phÇn tö cña T m vµ cét thø LÇn thø nhÊt t« ba « 1 ≤ s ≤ 1990. cña X 1 402 (2 + 22000 ) 5 Cho b¶ng « vu«ng 1991 x 1992. KÝ hiÖu « cña hµng thø T chia hÕt cho 5. §¸p sè: Sè tËp con cÇn t×m lµ Bµi 3.29 Hái cã bao nhiªu tËp con n. (m, n) lµ n»m ë giao T« mµu c¸c « cña b¶ng theo quy t¾c sau: (r, s), (r + 1, s + 1), (r + 2, s + 2) víi 1 ≤ r ≤ 1989, Tõ lÇn thø hai, mçi lÇn t« ba « ch­a cã mµu n»m bªn c¹nh nhau trong cïng mét hµng hoÆc trong cïng mét cét. Hái ta cã thÓ t« mµu hÕt tÊt c¶ c¸c « cña b¶ng ®­îc kh«ng? §¸p sè: Kh«ng ( Sö dông bÊt biÕn) . Bµi 3.30 Cho gãc vu«ng Oxy. Chia gãc ®ã thµnh c¸c h×nh vu«ng ®¬n vÞ bëi 64 c¸c ®­êng th¼ng song song víi Ox vµ Oy. KÝ hiÖu « cña dßng thø i vµ cét thø j (i, j) lµ « n»m ë giao (thø tù c¸c dßng vµ cét ®­îc tÝnh tõ d­íi lªn vµ tõ tr¸i sang ph¶i). Thùc hiÖn thuËt to¸n sau: Mçi lÇn lÊy ra khái gãc xOy viªn bi ë « (i, j) nµo ®ã mµ t¹i c¸c « (i + 1, j) vµ (i, j + 1) ®Òu kh«ng cã bi, ®ång thêi thªm vµo hai « nµy mçi « mét viªn bi. Hái sau mét sè lÇn thùc hiÖn thuËt to¸n ta cã thÓ nhËn ®­îc tr¹ng th¸i mµ: a) C¸c « (1,1),(1,2),(2,1),(2,2) ®Òu kh«ng cã bi? b) C¸c « (1,1),(1,2),(2,1),(2,2), (1,3) vµ (3,2) ®Òu kh«ng cã bi? §¸p sè: a) Cã b) Kh«ng ( Sö dông bÊt biÕn) . Bµi 3.31 Hai ng­êi lu©n phiªn viÕt c¸c sè 0 hoÆc 1 vµo c¸c « cña b¶ng 1993 x 1994. Gäi An vµ Bn t­¬ng øng lµ gi¸ trÞ lín nhÊt cña tæng c¸c sè thuéc cïng mét hµng vµ tæng c¸c sè thuéc cïng mét cét. Ng­êi thø nhÊt th¾ng nÕu An > Bn , ng­îc l¹i th× ng­êi thø hai th¾ng. Hái cã chiÕn l­îc th¾ng. §¸p sè: Ng­êi thø hai cã chiÕn l­îc th¾ng. Bµi 3.32 Trªn b¶ng cho tr­íc sè nguyªn d­¬ng n0 ≥ 2. ch¬i sau: Ng­êi thø nhÊt ®­îc phÐp viÕt lªn b¶ng sè n0 2 , ng­êi thø hai ®­îc phÐp viÕt sè n2 sao cho n1 n2 n1 Hai ng­êi ch¬i trß sao cho n0 ≤ n1 ≤ ps , trong ®ã p cã d¹ng lµ sè nguyªn tè vµ s lµ sè nguyªn d­¬ng. Sau ®ã thay gi¸ trÞ cña trÞ cña n2 n0 bëi gi¸ vµ tiÕp tôc ch¬i. Ng­êi thø nhÊt sÏ th¾ng nÕu viÕt ®­îc sè 2001 vµ ng­êi thø hai sÏ th¾ng nÕu viÕt ®­îc sè 1. Gi¶ thiÕt r»ng, hai ng­êi ch¬i ®Òu rÊt th«ng minh. Hái ai lµ ng­êi chiÕn th¾ng. §¸p sè: NÕu n0 ∈ {2, 3, 4, 5} th× ng­êi thø hai sÏ th¾ng. NÕu n0 ∈ {6, 7} th× hai ng­êi hßa. C¸c tr­êng hîp cßn l¹i th× ng­êi thø nhÊt sÏ th¾ng. Bµi 3.33 Trong mét cuéc thi hoa hËu, mçi gi¸m kh¶o ®­îc ®Ò nghÞ 10 thÝ sinh vµo vßng chung kÕt. Mét nhãm thÝ sinh gäi lµ chÊp nhËn ®­îc ®èi víi gi¸m kh¶o A nÕu trong nhãm ®ã cã Ýt nhÊt mét thÝ sinh do A ®Ò nghÞ. BiÕt 65 r»ng, víi 6 gi¸m kh¶o bÊt k× ®Òu tån t¹i mét nhãm gåm ®óng 2 thÝ sinh lµ nhãm chÊp nhËn ®­îc ®èi víi c¶ 6 gi¸m kh¶o ®ã. Chøng minh r»ng tån t¹i mét nhãm gåm 10 thÝ sinh lµ nhãm chÊp nhËn ®­îc ®èi víi mäi thµnh viªn cña ban gi¸m kh¶o. H­íng dÉn: Ph¶n chøng. Cho Bµi 3.34 §Æt 3k x k, n lµ c¸c sè nguyªn d­¬ng vµ mét b¶ng « vu«ng v« h¹n. n qu©n cê trong h×nh ch÷ nhËt 3k x n. XÐt c¸ch ch¬i sau ®©y: mçi qu©n cê sÏ nh¶y ngang hoÆc nh¶y däc qua mét « kÒ nã chøa qu©n cê ®Ó ®Õn « tiÕp theo nÕu « nµy cßn trèng. Sau khi lµm nh­ vËy th× lo¹i bá qu©n cê võa bÞ nh¶y qua.Hái cã khi nµo trªn b¶ng « vu«ng ®· cho chØ cßn l¹i ®óng mét qu©n cê?. H­íng gi¶i: Sö dông bÊt biÕn. Bµi 3.35 Trong h×nh trßn ®¬n vÞ cho 2000 ®iÓm t¹o thµnh ®a gi¸c låi A1 A2 …A2 000. Chøng minh r»ng tån t¹i 3 ®iÓm trong sè ®ã t¹o thµnh tam gi¸c cã diÖn tÝch kh«ng v­ît qu¸ 1 . 31250000 H­íng gi¶i: Ph­¬ng ph¸p cùc h¹n. Bµi 3.36 Trªn mÆt ph¼ng cho mét sè ®iÓm ®á vµ mét sè ®iÓm xanh. Mét sè cÆp ®iÓm ®­îc nèi víi nhau . Mét ®iÓm ®­îc gäi lµ k× dÞ nÕu qu¸ nöa sè ®o¹n th¼ng xuÊt ph¸t tõ ®iÓm nµy cã ®Çu mót cßn l¹i lµ kh¸c mµu víi nã. Thùc hiÖn thuËt to¸n sau: Mçi lÇn chän tra mét ®iÓm k× dÞ vµ ®æi mµu nã. Chøng minh r»ng sau h÷u h¹n b­íc, tÊt c¶ c¸c ®iÓm k× dÞ ®Òu bÞ xãa. H­íng gi¶i: Ph­¬ng ph¸p cùc h¹n. Bµi 3.37 Xem kÕt qu¶ häc tËp cña mét líp häc, ng­êi ta thÊy h¬n 2/3 sè häc sinh ®¹t ®iÓm giái ë m«n To¸n còng ®ång thêi ®¹t ®iÓm giái ë m«n VËt Lý; h¬n 2/3 sè häc sinh ®¹t ®iÓm giái ë m«n VËt Lý còng ®ång thêi ®¹t ®iÓm giái ë m«n Ng÷ v¨n; h¬n 2/3 sè häc sinh ®¹t ®iÓm giái ë m«n Ng÷ v¨n còng ®ång thêi ®¹t ®iÓm giái ë m«n LÞch sö; h¬n 2/3 sè häc sinh ®¹t ®iÓm giái ë m«n LÞch sö còng ®ång thêi ®¹t ®iÓm giái ë m«n To¸n. Chøng minh r»ng tån t¹i Ýt nhÊt mét häc sinh ®¹t ®iÓm giái ë c¶ bèn m«n nªu trªn. 66 H­íng dÉn: Nguyªn lý bï trõ. Bµi 3.38 Cho tr­íc n lµ sè tù nhiªn lÎ lín h¬n 1, víi mçi ho¸n vÞ a = (a1 , a2 , …, an ) trong sè n! ho¸n vÞ cña 1, 2, …, n, ta ®Æt S(a) = n X 2i ai i=1 Chøng minh r»ng tån t¹i 2 ho¸n vÞ cña b vµ c, b kh¸c c sao cho n! lµ mét ­íc sè S(b) − S(c). H­íng dÉn: Ph­¬ng ph¸p ph¶n chøng. Bµi 3.39 Mét h×nh trßn ®­îc chia thµnh 6 h×nh qu¹t b»ng nhau, trong mçi h×nh qu¹t ®Æt mét qu©n cê. Mçi lÇn cho phÐp chuyÓn mét qu©n cê ë mét h×nh qu¹t sang mét trong hai h×nh qu¹t bªn c¹nh. Chøng minh r»ng kh«ng thÓ dån c¸c qu©n cê vµo mét h×nh qu¹t sau 2006 lÇn thùc hiÖn. H­íng dÉn : X©y dùng hÖ thøc truy håi. Bµi 3.40 Cho P1 , P2 , …, Pn N, 2 ≤ p ≤ n. lµ n ®iÓm trªn cïng mét ®­êng trßn. Cho Cã bao nhiªu c¸ch t« mµu n diÓm ®· cho b»ng cho hai ®iÓm kÒ nhau ®­îc t« bëi hai mµu kh¸c nhau. §¸p sè: a1 = p, a2 = p(p − 1), an = (p − 1)an−2 + (p − 2)an−1 . 67 p p∈ mµu sao Tµi liÖu tham kh¶o TiÕng ViÖt 1. NguyÔn H÷u §iÓn (2004), Gi¶i to¸n b»ng ph­¬ng ph¸p ®¹i l­îng bÊt biÕn, Nxb Gi¸o dôc, Hµ Néi. 2. NguyÔn §øc NghÜa, NguyÔn T« Thµnh (2004), To¸n rêi r¹c, Nxb §¹i häc Quèc gia Hµ Néi, Hµ Néi. 3. NguyÔn V¨n MËu, TrÇn Nam Dòng, Vò §×nh Hßa, §Æng Huy RuËn, §Æng Hïng Th¾ng (2008), Chuyªn ®Ò chän läc tæ hîp vµ to¸n rêi r¹c, Nxb Gi¸o dôc, Hµ Néi. 4. Ng« §¾c T©n (2004), Lý thuyÕt tæ hîp vµ ®å thÞ, Nxb §¹i häc Quèc gia Hµ Néi, Hµ Néi. TiÕng Anh 5. V.K. Balakrishnan, Ph.D (1995), Theory and problems of combinatorics, McGraw-Hill, INC, Singapore. 6. Titu Andreescu Zuming Feng (2004), A Path to Combinatoricts for Undergraduates ( Counting Strategies), Birkhauser Boston, United states of America. 68