Tartalomjegyzék
Vissza 44
Számlálási feladatok, a kombinatorika elemei
II. FEJEZET SZÁMLÁLÁSI FELADATOK, A KOMBINATORIKA ELEMEI II.2.1. Gyakorlatok és feladatok (42. oldal) 1. Hány darab legfeljebb hatjegyű természetes szám létezik? 1. megoldás. Minden, legfeljebb hatjegyű természetes szám felírható hat számjegy segítségével, ha az elejére 0-kat írunk. Így a 33 felírható 000033 alakban, tehát minden, legfeljebb hatjegyű szám azonosítható az A × A × A × A × A × A Descartes
{
}
szorzat pontosan egy elemével, ahol A = 0,1, 2, 3, 4, 5, 6, 7, 8, 9 . Ebből következik, hogy 106 ilyen szám létezik. 2. megoldás. A legnagyobb legfeljebb hatjegyű szám a 999999 és a legkisebb a 000000, tehát összesen 106 ilyen szám létezik. 2. Hány darab olyan természetes szám létezik, amelynek a hetes számrendszerbeli reprezentációja pontosan hét számjegyet tartalmaz?
{
}
1. megoldás. Az első számjegynek az A = 1, 2, 3, 4, 5, 6 halmazban kell lennie,
{
}
míg az összes többi számjegy a B = 0,1, 2, 3, 4, 5, 6 halmaz bármelyik eleme lehet. Így az A × B × B × B × B × B × B halmaz elemeinek számát kell meghatározni. Ez 6 ⋅ 7 6 , tehát a hetes számrendszerben 705894 hétjegyű szám létezik. 2. megoldás. A legkisebb hétjegyű szám az 1000000(7) és a legnagyobb a
6666666(7) , tehát összesen 6666666(7) − 1000000(7) = 705894(10) ilyen szám létezik. 3. Egy helyőrség 200 közkatonája, 10 altisztje, négy rádiósa és három tisztje közül ki kell választani egy négytagú különítményt, és ki kell jelölni a különítmény vezetőjét. A különítmény kell tartalmazzon egy közkatonát, egy rádióst, egy altisztet és egy tisztet, és a vezetője csak a rádiós vagy a tiszt lehet. Hány különböző módon választható ki egy ilyen különítmény? Megoldás. A négytagú különítmény (vezető nélkül) 200 ⋅ 10 ⋅ 4 ⋅ 3 módon választható ki. Minden ilyen négytagú csapatban a vezetőt két különböző módon választhatjuk ki, tehát a különítmények száma 2 ⋅ 200 ⋅ 10 ⋅ 4 ⋅ 3 = 48000 . 4. Vizsgáld meg a következő egyenlőségek helyességét: a) (A ∪ B ) ×C = (A ×C ) ∪ (B ×C ) ; b) (A \ B ) ×C = (A ×C ) \ (B ×C ) ; c) (A ∩ B ) ×C = (A ×C ) ∩ (B ×C ) .
{
}
Megoldás. a) (A ∪ B ) ×C = (x , c ) / x ∈ A vagy x ∈ B =
= {(x , c ) / x ∈ A} ∪ {(x , c ) / x ∈ B } = (A ×C ) ∪ (B ×C ) . b) (A \ B ) ×C = {(x , c ) / x ∈ A és x ∉ B } =
= {(x , c ) / x ∈ A} \ {(x , c ) / x ∈ B } = (A ×C ) \ (B ×C ) .
Tartalomjegyzék Számlálási feladatok, a kombinatorika elemei
{
45
}
c) (A ∩ B ) ×C = (x , c ) / x ∈ A és x ∈ B =
= {(x , c ) / x ∈ A} ∩ {(x , c ) / x ∈ B } = (A ×C ) ∩ (B ×C ) . 5. Írd egyszerűbb alakba az (A × A) ∩ (A ×C ) ∩ (B × A) ∩ (B ×C ) kifejezést (csak egy direkt szorzat szerepeljen benne). Megoldás. Az előbbi feladat c) pontjához hasonlóan (A × A) ∩ (A ×C ) = A × (A ∩ C ) és (B × A) ∩ (B ×C ) = B × (A ∩ C ) , tehát
(A × A) ∩ (A ×C ) ∩ (B × A) ∩ (B ×C ) = = (A × (A ∩ C )) ∩ (B × (A ∩ C )) = (A ∩ B ) × (A ∩ C ) . 6. Egyszerre dobunk három különböző színű dobókockával. Mi a valószínűsége annak, hogy a három szám közül az egyik a másik kettő összege? Megoldás. Az összes lehetőségek száma 63 , mert a dobókockák különböznek. A kedvező esetekben a következő számok jelenhetnek meg:
{1,1, 2} , {1, 2, 3} , {1, 3, 4} , {1, 4, 5} , {1, 5, 6} , {2, 2, 4} , {2, 3, 5} , {2, 4, 6} , {3, 3, 6} .
A színeloszlás szerint az első, a hatodik és a kilencedik számhármas 3 kedvező esetet származtat, míg a többi számhármas mindegyike 6 kedvező esetet. Így a kedvező 45 5 . esetek száma 6 × 6 + 3 × 3 = 45 , tehát a keresett valószínűség 3 = 6 24 7. Egy Las Vegas-i kaszinó egyik játékgépén három korong forog. Mindegyik korong oldalát 24 egyforma részre osztották, és minden részre ráfestették a következő hat rajz valamelyikét, oly módon, hogy mindegyik pontosan négyszer szerepeljen mindegyik korongon:
A korongok egymástól függetlenül forognak és a játékos mindig egy-egy ábrát láthat minden korongról. A játékos akkor nyer, ha mindhárom korongon ugyanazt az alakzatot látja. Mennyi a valószínűsége annak, hogy már az első játéknál nyerünk? Ha 10 cent egy játék, megéri-e a kaszinónak, ha négy dollárt fizet egy nyereségért? Megoldás. Az összes esetek száma 24 3 . Ebből 6 ⋅ 4 3 kedvező, tehát a keresett 6 ⋅ 43 1 . valószínűség 3 3 = 6 ⋅4 36 Ez azt jelenti, hogy hosszú távon 36 játszmára jut egy nyereség. A kaszinónak tehát, hosszú távon 36 ⋅ 10 = 360 cent bevétel után 400 centet kell fizetnie. Ez nem nyereséges számára. 8. a) Egy n elemű számhalmaz elemeiből hány különböző módon állíthatunk össze egy olyan számpárt, amelynek az elemei különböznek?
Tartalomjegyzék
46
Számlálási feladatok, a kombinatorika elemei
b) Egy n elemű számhalmaz elemei közül hány különböző módon állíthatunk össze egy olyan számpárt, amelynek az elemei egyenlők is lehetnek? Megoldás. a) Minden szám (n − 1) más számmal alkothat ilyen számpárt. Ez összesen n (n − 1) párt jelent, de így minden lehetséges számpárt kétszer számoltunk, n (n − 1) tehát számpár létezik. 2
{
b) Itt az A = x 1, x 2 , x 3 ,..., x n
}
halmaznak önmagával való Descartes szorzatának
számosságát kell meghatároznunk, tehát a válasz n 2 . 9. Egy tíz nőt és harminc férfit tartalmazó űrhajós csoportból hányféleképpen lehet kiválasztani egy olyan öttagú csapatot, amelyben két nő és három férfi van? 10 ⋅ 9 különböző módon lehet (lásd Megoldás. A tíz nő közül kettőt kiválasztani 2 30 ⋅ 29 ⋅ 28 8/a)-t). A harminc férfi közül a három férfit módon választhatjuk ki, tehát 6 az öttagú csoportok száma 45 ⋅ 4060 = 182700 . 10. Igaz-e, hogy ha az n1 természetes számnak d1 természetes osztója van és az n2 természetes számnak d2 , akkor az n1 ⋅ n2 számnak d1 ⋅ d2 osztója van? Milyen feltételre van szükség ahhoz, hogy az állítás igaz legyen? Megoldás. Az állítás nem igaz, mert az n1 = 12 természetes számnak 6 osztója, az n2 = 6 természetes számnak 4 osztója és az n1n2 = 72 számnak 12 osztója van. A tankönyv 2.10. és 2.11. feladata alapján az n = p1α1 p1α2 ...pkαk számnak
(α1 + 1) (α2 + 1) ... (αk + 1) darab osztója van. Így az állítás csakis akkor igaz, ha n1 nek és n2 -nek nincs közös prím osztója, azaz ha relatív prímek. 11. Egy börtönben 1000 cella van 1-től 1000-ig számozva, és minden cellának az ajtaján egy olyan zár, amelyen három betű látható (lásd a mellékelt ábrát). Az ajtó akkor nyílik ki, ha az a betű van legfelül. Miután a rabok elalszanak, a börtönőr 1000szer körbejárja a cellákat A k-adik körútja alkalmával minden kadik cella zárján fordít egyet (trigonometriai irányban 120°-ot). Reggel hány zár lesz nyitva? Melyek ezek? Megoldás. A börtönőr az n-edik cella zárján pontosan akkor fordít, ha a körútjának sorszáma osztója n-nek. Az ábra alapján minden ajtó nyitva van az első körút előtt. Eszerint azok a cellák lesznek reggel is nyitva, amelyekre a sorszámuk osztóinak száma osztható 3-mal. Az előbbi feladatban említett összefüggés alapján ez pontosan akkor következik be, ha az n prímtényezős felbontásában van legalább egy (3k + 2) alakú kitevő. Az ilyen számok
prímtényezős felbontásában a következő számok valamelyike kell szerepeljen: 22 , 25 , 28 , 32 , 35 , 52 , 7 2 , 112 , 132 , 172 , 192 , 232 , 292 , 312 . Az előbbiek alapján a következő számokat kapjuk (az aláhúzott számokat már egyszer megkaptuk, így nem kell őket számításba venni):
Tartalomjegyzék
47
Számlálási feladatok, a kombinatorika elemei 22 ⋅ 1 , 22 ⋅ 3 , 22 ⋅ 5 , … , 22 ⋅ 249 25 ⋅ 1 , 25 ⋅ 3 , 25 ⋅ 5 , … , 25 ⋅ 31 28 ⋅ 1 , 28 ⋅ 3 32 ⋅ 1 , 32 ⋅ 2 , 32 ⋅ 4 , 32 ⋅ 5 32 ⋅ 7 , 32 ⋅ 8 , 32 ⋅ 10 , … ,
(125 darab) (16 darab) (2 darab)
32 ⋅ 32 , 32 ⋅ 34 , … , 32 ⋅ 110 35 ⋅ 1 , 35 ⋅ 2 , 35 ⋅ 4
(72 darab) (2 darab)
52 ⋅ 1 , 52 ⋅ 2 , 52 ⋅ 3 , 52 ⋅ 4 , 52 ⋅ 6, , 52 ⋅ 7 , 52 ⋅ 8 , 52 ⋅ 9 , 52 ⋅ 11 , … , 52 ⋅ 31 , 52 ⋅ 32 , 52 ⋅ 33 , 52 ⋅ 39 2
2
2
2
2
2
(29 darab)
2
7 ⋅1, 7 ⋅ 2, 7 ⋅ 3 , 7 ⋅ 4 , 7 ⋅ 5 , 7 ⋅ 6 , 7 ⋅ 8 , 72 ⋅ 9 , … , 72 ⋅ 19 2
2
2
2
(15 darab) 2
2
2
2
11 ⋅ 1 , 11 ⋅ 2 , 11 ⋅ 3 , 11 ⋅ 4 , 11 ⋅ 5 , 11 ⋅ 6 , 11 ⋅ 7 , 11 ⋅ 8 (7 darab)
132 ⋅ 1 , 132 ⋅ 2 , 132 ⋅ 3 , 132 ⋅ 4 , 132 ⋅ 5 2
2
(4 darab)
2
17 ⋅ 1 , 17 ⋅ 2 , 17 ⋅ 3 (3 darab) 2 2 19 ⋅ 1 , 19 ⋅ 2 (2 darab) 2 23 ⋅ 1 (1 darab) 292 ⋅ 1 (1 darab) 2 31 ⋅ 1 (1 darab). Ez összesen 280 szám, tehát 280 cellának lesz ismét nyitva az ajtaja.
II.4. Gyakorlatok és feladatok (62. oldal) 1. Egy akadályversenyen résztvevő csapatok a mellékelt térképvázlatot kapták. Feladatuk, hogy A-ból a B, C és D pontok érintésével visszajussanak A-ba. Melyik a legrövidebb útvonal? Megoldás. A következő hat útvonal lehetséges: 1. A – B – D – C – A 2. A – B – C – D – A 3. A – D – C – B – A 4. A – D – B – C – A 5. A – C – B – D – A 6. A – C – D – B – A. Ezek kettesével csoportosíthatóak, hisz az 1) és 6) ugyanolyan hosszú (egyik a másiknak fordítottja). Hasonlóan a 2) és 3) illetve a 4) és 5) ugyanolyan hosszúságú, tehát elégséges az 1), 2) és 4) hosszát kiszámolni. A megfelelő úthosszak a következők: 1. 1700 + 1400 + 1500 + 1450 = 6050 2. 1700 + 2000 + 1500 + 2100 = 7300 4. 2100 + 1400 + 2000 + 1450 = 6950. A legrövidebb útvonal tehát az 1)-es és a 6)os.
Tartalomjegyzék
48
Számlálási feladatok, a kombinatorika elemei
2. Egy osztályban 13 lány és 12 fiú tanul. Találomra kiválasztunk versmondásra, színházjegyvásárlásra és tűzoltósági felkészítőre két-két lányt és egy-egy fiút. Hányféle lehet az így összeállított kilencfős csapat? Megoldás. Versmondásra a két lányt C 132 , az egy fiút C 121 módon választhatjuk ki,
tehát C 132 ⋅ C 121 különböző versmondó-csapatot tudunk összeállítani. A megmaradt 11 lány és 11 fiú közül C 112 ⋅ C 111 jegyvásárló-csapat és a többiekből C 92 ⋅ C 110 tűzoltóbrigád állítható össze. Így a kilencfős csapat C 132 ⋅ C 121 ⋅ C 112 ⋅ C 111 ⋅ C 92 ⋅ C 110 különböző összetétellel rendelkezhet. 3. Két egyforma kockával egyszerre dobunk. Mennyi a valószínűsége annak, hogy a két megjelenő szám összege 7? Megoldás. A mellékelt táblázatban feltüntettük az összes lehetséges esetet és szürkére színeztük a kedvező eseteknek megfelelő mezőket. {1, 1} {1, 2} {1, 3} {1, 4} {1, 5} {1, 6} {2, 2} {2, 3} {2, 4} {2, 5} {2, 6} {3, 3} {3, 4} {3, 5} {3, 6} {4, 4} {4, 5} {4, 6} {5, 5} {5, 6} {6, 6} A táblázat alapján a lehetséges esetek száma 21, és a kedvező esetek száma 3, tehát a 1 keresett valószínűség . 7 4. Változik-e az előbbi kérdésre adott válasz, ha nem egyforma kockákkal dobunk? Megoldás. Ha nem egyforma kockákkal dobunk, akkor az alábbi táblázathoz jutunk: {1, 1} {1, 2} {1, 3} {1, 4} {1, 5} {1, 6} {2, 1} {2, 2} {2, 3} {2, 4} {2, 5} {2, 6} {3, 1} {3, 2} {3, 3} {3, 4} {3, 5} {3, 6} {4, 1} {4, 2} {4, 3} {4, 4} {4, 5} {4, 6} {5, 1} {5, 2} {5, 3} {5, 4} {5, 5} {5, 6} {6, 1} {6, 2} {6, 3} {6, 4} {6, 5} {6, 6}
Tartalomjegyzék Számlálási feladatok, a kombinatorika elemei
49
Itt a lehetséges esetek száma 36 és a kedvező esetek száma 6, tehát a valószínűség
1 . 6
5. Hány különböző módon lehet 10 embert egy kerek asztal köré leültetni? Megoldás. Az asztal körül csak az számít, hogy ki kinek a szomszédja, tehát ha a helyeket és az embereket megszámozzuk, akkor minden lehetséges ülésrend 10 darab P permutációt származtat. Így az ülésrendek száma 10 = 9! . 10 6. Hány háromszög látható a mellékelt ábrán:
Hány háromszöget fogsz látni, ha az alapot n egyenlő részre osztjuk? Megoldás. Az alapon megjelenő 7 pont közül ki kell választani kettőt. Ez a kettő és a felső csúcs meghatároz egy háromszöget, tehát C 72 = 21 háromszög látható az ábrán. Ha az alapot n egyenlő részre osztjuk, C n2+1 háromszög lesz látható. 7. Hány téglalap látható a mellékelt ábrán?
Megoldás. Az ábrán látható minden téglalapot egyértelműen meghatároz az oldalainak az AB-re és BC-re eső vetülete. A
D
II. 1. ábra B
C
Eszerint az AB-n is és a BC-n is ki kell választani két-két pontot. Ezt C 52 ⋅ C 92 módon tehetjük meg, tehát 360 téglalap látható az ábrán. Általában egy m × n -es négyzethálón C m2 +1 ⋅ C n2+1 téglalap látható. 8. Az 1, 2, 3, 4, 5, 6, 7, 8 és 9 számjegyekből hány darab olyan kilencjegyű szám készíthető, amelynek számjegyei egymástól különbözőek és a) az 1-es közvetlenül a 2-es előtt áll? b) az 1-es előbb áll, mint a 2-es? Megoldás. a) Minden ilyen szám tekinthető a 12, 3, 4, 5, 6, 7, 8 és 9 számok permutációjának, tehát 8! ilyen szám létezik. b) Minden ϕ permutációhoz hozzárendeljük azt, amelyiket a ϕ -ből úgy kapunk, hogy az 1-est és a 2-est felcseréljük. Így az 1, 2, 3, 4, 5, 6, 7, 8 és 9 számok
Tartalomjegyzék
50
Számlálási feladatok, a kombinatorika elemei
permutációit kettesével csoportosítottuk. Mivel minden csoportból pontosan egy 9! származtat nekünk megfelelő számot, a kívánt számok száma . 2 9. Egy pénzérmét n-szer feldobunk. Hány különböző, pontosan k darab fejet tartalmazó fej-írás dobássorozat lehetséges? Megoldás. Az n hosszúságú sorozatban pontosan k darab fej kell legyen. Ezek helyét C nk módon választhatjuk ki, tehát C nk darab, pontosan k fejet tartalmazó, dobássorozat létezik. 10. A {0,1, 2, 3,..., 2n − 1} halmaz elemei közül találomra kiválasztunk egyet. Mennyi a valószínűsége annak, hogy a kiválasztott szám b) bináris számjegyeinek1 összege pontosan k? a) 2-nek hatványa? Megoldás. a) A lehetséges esetek száma 2n , a kettő-hatványok száma n – 1, tehát a n −1 keresett valószínűség . 2n b) Az adott halmaz minden eleme a kettes számrendszerben egy n hosszúságú n jelsorozattal írható le. Például 2 = 00...0 N 10 , 2 − 1 = 11.. N1 . A számjegyek összege n
n−2
pontosan akkor k, ha ebben a jelsorozatban k darab egyes szerepel, tehát a kedvező Ck esetek száma C nk , a keresett valószínűség pedig nn . 2 11. Határozd meg az
{
A = (X ,Y ) X ,Y ⊂ {1, 2, 3,..., n } , X ∩ Y = ∅, X ∪ Y = {1, 2, 3,..., n }
{
} és
}
B = (X ,Y ) X , Y ⊂ {1, 2, 3,..., n } , X ∪ Y = {1, 2, 3,..., n }
halmazok elemeinek számát! Az A számosságának meghatározása 1. megoldás. Az A halmaz azokat az (X, Y) halmaz-párokat tartalmazza, amelyek
{
} halmaznak egy partícióját alkotják. Egy ilyen (X, Y) halmazpárt úgy is leírhatunk, hogy az {1, 2,..., n } minden eleméről megmondjuk, hogy X-ben vagy Yaz 1, 2,..., n
ban van. Az A minden elemének feleltessünk meg 0-t, ha X-ben van és 1-et, ha Y-ban
(
van. Így minden n hosszúságú 0–1 jelsorozat egy ilyen X ,Y
) halmazpárt ír le, tehát
a halmaz-párok száma 2n . 2. megoldás. Vizsgáljuk meg, hány olyan halmaz-pár létezik, amelyben X-nek k
{
}
eleme van. A feltételek alapján Y = 1, 2,..., n \ X , tehát minden X-hez pontosan egy Y tartozik. Így pontosan C nk darab olyan halmaz-pár létezik, amelynek első tagja k 1
Egy szám bináris számjegyei az illető szám kettes számrendszerbeli felírásában megjelenő számjegyek.
Tartalomjegyzék
51
Számlálási feladatok, a kombinatorika elemei
elemű. Az A elemeinek számát megkapjuk, ha az előbbi eredményt összegezzük a n
k = 0, n értékekre. Így A = ∑ C nk = 2n . k =0
A B számosságának meghatározása
{
}
{
1. megoldás. Az (X ∪ Y ) = 1, 2,..., n egyenlőség alapján az 1, 2,..., n
} halmaz
minden eleme vagy csak X-hez, vagy csak Y-hoz, vagy mindkettőhöz tartozik. Minden elemhez 0-t rendelünk, ha az csak X-hez, 1-et, ha csak Y-hoz és 2-t, ha X-hez is és Y-
(
) halmaz-pár leírható egy n hosszúságú 0–1–2 jelsorozattal és minden jelsorozathoz tartozik egy (X ,Y ) halmaz-pár. Így a halmaz-
hoz is hozzátartozik. Így minden X ,Y
párok száma 3n .
{
}
2. megoldás. Ha X = k , akkor Y felbontható az 1, 2,..., n \ X -re és, az X egy
részhalmazára. X rögzítése C nk módon lehetséges, az X részhalmazának kiválasztására
(
2k lehetőség van, tehát az X ,Y
)
pár rögzítésére 2k C nk mód van. A B elemeinek
számát megkapjuk, ha a 2k C nk számokat összeadjuk k = 0, n esetén. n
B = ∑ 2k C nk = 3n .
(Newton binomiális tételéből)
k =0
12. A sík n pontja legfeljebb hány különböző egyenest határoz meg? A sík négy pontja hány különböző egyenest határozhat meg? Megoldás. A sík n pontja akkor határoz meg a legtöbb egyenest, ha a pontok közt nincs három egy egyenesen. Ebben az esetben minden pontpár meghatároz egy n (n + 1) egyenest, tehát C n2 = az egyenesek száma. A sík négy pontja legtöbb 2 4⋅3 = 6 egyenest határozhat meg, ha nincs három kollineáris köztük (II.2. ábra). Ha 2 három pont kollineáris, és a negyedik nincs az általuk meghatározott egyenesen, akkor 4 egyenest határoznak meg (lásd II.3. ábra). Ha mind a négy pont egy egyenesre esik, akkor csak egy egyenest határoznak meg, tehát négy pont 1, 4 vagy 6 egyenest határozhat meg. II. 2. ábra
II. 3. ábra
Tartalomjegyzék
52
Számlálási feladatok, a kombinatorika elemei
13. Oldd meg az alábbi egyenleteket! a) n ! = 110 ; c)
n !+ (n − 1)! (n + 1) ⋅ (n − 2)!
b) n !+ (n + 1)! = 134 ;
= 12 ;
d)
n! (n − 1)!
=6;
e)
1 1 1 − = ; n ! (n + 1)! 30
f) Vn5 = 18 ⋅Vn1−2 ;
g)
1 1 1 − k = k ; k C4 C5 C6
h) C nn++31 = n 2 − 4 ;
2
i) C 3nn +−n6 +1 = 220 ; j) C n2 + C n2−3 + C n2−2 = 19 . Megoldás. a) n ! = 110 = 2 ⋅ 5 ⋅ 11 , tehát nincs megoldás. b) n ! + (n + 1) ! = 134
⇔ n !(1 + n + 1) = 134 ⇔ n !(n + 2) = 134 = 2 ⋅ 67 ,
tehát nincs megoldás. n ! + (n − 1) ! (n − 1) !(n + 1) = 12 ⇔ = 12 ⇔ n − 1 = 12 ⇔ n = 13 . c) (n + 1) ⋅ (n − 2) ! (n + 1)(n − 2) ! d) e)
n! (n − 1) !
= 6 ⇔ n = 6.
1 1 1 − = n ! (n + 1) ! 30
⇔
1 1 1 = 1 − n! n + 1 30
⇔
n 1 = (n + 1)! 30
⇔
30n = (n + 1)! ⇔ 30 = 2 ⋅ 3 ⋅ 5 = (n − 1) !(n + 1) , tehát n = 4 . f) Vn5 = 18 ⋅Vn1−2 ,
Vn1−2 =
(n − 2) ! (n − 3) !
n ≥ 3 . Vn5 =
n! (n − 5) !
= (n − 4)(n − 3)(n − 2)(n − 1) n
= (n − 2) , tehát (n − 4) (n − 3)(n − 2)(n − 1) n = 18 (n − 2) ⇒
(n − 4)(n − 3)(n − 1) n = 2 ⋅ 3 ⋅ 3 , tehát nincs megoldás. g) A létezési feltétel k ≤ 4 . 1 1 1 1 1 1 ⇒ − k = k ⇔ − = k ! ! ! 4 5 6 C4 C5 C6 k !(4 − k )! k !(5 − k )! k !(6 − k )! ⇒
és
(4 − k ) !
−
(5 − k )!
=
(6 − k )!
⇒ (4 − k ) ! −
(5 − k )!
=
(6 − k )!
⇒ 4! 5! 6! 5 30 (5 − k )(6 − k ) 5 −k ⇒ 1− ⇒ 30 − 6 (5 − k ) = (5 − k )(6 − k ) ⇒ = 5 30 ⇒ 30 − 30 + 6k = 30 − 5k − 6k + k 2 ⇒ k 2 − 17k + 30 = 0 ⇒
Tartalomjegyzék
53
Számlálási feladatok, a kombinatorika elemei
17 ± 172 − 120 17 ± 13 = ⇒ k1 = 15 és k2 = 2 . 2 2 Viszont k ≤ 4 , tehát k = 2 . (n + 3) ! (n + 2)(n + 3) h) C nn++31 = n 2 − 4 ⇒ C nn++31 = = ⇒ n 2 − 5n − 14 = 0 (n + 1) ! ⋅ 2 2 ⇒ k1,2 =
5 ± 25 + 56 5±9 = ⇒ n 1 = −2 2 2 következik, hogy n = 7 . 2 i) C 3nn +−n6 +1 = 220 ⇒ 3n + 6 ≥ 0 ⇒ n ≥ −2 ⇒
n1,2 =
és n2 = 7 . Mivel n ≥ −1 ,
n 2 − n + 1 ≤ 3n + 6 ⇒ n 2 − 4n − 5 ≤ 0 ⇒ (n − 5) (n + 1) ≤ 0 ⇒ n ∈ −1, 5 ∩ ] .
{
}
Az előbbiek alapján n ∈ −1, 0,1, 2, 3, 4, 5 . n = −1 esetén C 33 = 1 , n = 0 -ra C 61 =
6! = 6, 5!
n = 1 -re
C 91 = 9 ,
n = 2 -re
C 123 =
12! 10 ⋅ 11 ⋅ 12 = = 220 , 9! ⋅ 6 6
15! 9 ⋅ 10 ⋅ 11 ⋅ 12 ⋅ 13 ⋅ 14 ⋅ 15 = = 6435 , n = 4 -re C 1813 = 8568 és 7! ⋅ 8! 2⋅3⋅4⋅5⋅6⋅7 n = 5 esetén C 2121 = 1 , tehát az egyetlen megoldás az n = 2 . j) A feltételek alapján n ≥ 5 . (n − 3) ! (n − 2) ! n! C n2 + C n2−3 + C n2−2 = 19 ⇒ + + = 19 ⇒ (n − 2) ! ⋅ 2 (n − 5) ! ⋅ 2 (n − 4) ! ⋅ 2 ⇒ (n − 1) n + (n − 4)(n − 3) + (n − 3)(n − 2) = 38 ⇒ n = 3 -ra C 157 =
2
⇒ n (n − 1) + (n − 3)(2n − 6) = 38 ⇒ n (n − 1) + 2 (n − 3) = 38 ⇒ ⇒ n 2 − n + 2n 2 − 12n + 18 = 38 ⇒ 3n 2 − 13n − 20 = 0 ⇒ 13 ± 169 + 240 13 ± 409 = ∉`. ⇒ n1,2 = 6 2 Tehát nincs megoldás. Megjegyzés. Aszerint, hogy a C nk , illetve Vnk számot milyen n és k értékekre tekintjük értelmezettnek, más megoldásokat is kaphatunk. A tankönyv 3.2.4. és 3.3.3. értelmezése szerint előfordulhat, hogy k > n . Ebben az esetben C nk = 0 . Például a g) pontban a k ≤ 4 azért szükséges, mert ellenkező esetben valamelyik tört nevezője 0 1 lenne. Tehát a k ≤ 4 feltétel nem a C 4k létezési feltétele, hanem az k törtnek. Az f) C4 pontban, ha nem feltételezzük, hogy n − 2 ≥ 1 , akkor az n = 2 is megoldás, mert 2
V25 = 18V01 = 0 . Az i) pontban az n 2 − n + 1 ≤ 3n + 6 feltétel nem a C 3nn +−n6 +1 létezéséhez szükséges, hanem ahhoz, hogy ez a kifejezés 0-tól különbözzön. A j)
Tartalomjegyzék
54
Számlálási feladatok, a kombinatorika elemei
pontban n ∈ {3, 4} esetén is értelmezhető a bal oldali kifejezés. Ezekre az értékekre sem kapunk 19-cet. 14. Oldd meg a következő egyenletrendszereket! n −1 k x ⋅ C nk−−21 + ⋅y = k −1 n −1 . b) n 1 k −1 − k − 2 x ⋅ C n −1 − ⋅y = k n −1
V2nm−2 = 8 ⋅V2nm−3 ; a) 3 ⋅ C 2nm−2 = 8 ⋅ C 2nm−3
V2nm−2 = 8 ⋅V2nm−3 ⇒ n ≥ 3 , m ≥ 0 és 2m ≥ n − 2 . Megoldás. a) 3 ⋅ C 2nm−2 = 8 ⋅ C 2nm−3 ( 2 ) ! (2m ) ! m =8 2m − n + 3 = 8 (2m − n + 2) ! (2m − n + 3) ! ⇒ ⇒ 3 8 (2m ) ! (2m ) ! = 3 =8 n − 2 2m − n + 3 (n − 3) !(2m − n + 3) ! (n − 2) !(2m − n + 2) ! 3 = 1 ⇒ n = 5. ⇒ n −2
(
) ( )
Mivel 2m = n + 5 ⇒ m = 5 , tehát m, n = 5, 5 . b) Ha k > n , akkor C nk−−22 = C nk−−21 = 0 és a rendszer összeférhetetlen, tehát feltételezhetjük, hogy k ≤ n . A törtek létezéséhez szükséges, hogy n ≠ 1 , 1 1 k ∉ 0,1 . Az első egyenletet -val, a másodikat -gyel szorozzuk, majd k k −1 összeadjuk a két egyenletet: 1 1 2 x ⋅ C nk−−21 + C nk−−22 = . k n −1 k −1 (n − 2) ! (n − 2) ! 1 1 1 1 De C nk−−21 + C nk−−22 = ⋅ + ⋅ = k k −1 k (k − 1)!(n − k − 1)! k − 1 (k − 2)!(n − k )!
{ }
(n − 1) ! (n − 1) ! Ck 1 1 1 ⋅ + ⋅ = ⋅ (C nk−1 + C nk−−11 ) = n , k!(n − k − 1)! n − 1 (k − 1)!(n − k )! n − 1 n − 1 n −1 k (k − 1)(k − n ) 2 tehát x = k . Ezt visszahelyettesítjük és kifejezzük y-t: y = . 2 Cn n (n − 1) 15. Oldd meg az alábbi egyenlőtlenségeket! a) C 10n −1 > 2 ⋅ C 10n ; b) 5 ⋅ C n3 > C n4+2 .
=
Megoldás. a) Ahhoz, hogy a C 10n−1 > 2C 10n egyenlőtlenség teljesülhessen C 10n−1 nem
lehet 0, tehát 0 ≤ n − 1 ≤ 10 . n = 11 esetén 1 = C 1010 > 2C 1011 = 0 , míg 0 ≤ n ≤ 10 esetén az egyenlőtlenség a következőképpen alakítható:
Tartalomjegyzék
55
Számlálási feladatok, a kombinatorika elemei
10! 10! > 2⋅ (n − 1) !(10 − n + 1) ! n !(10 − n ) !
⇔
1 2 > 11 − n n
⇔
n > 22 − 2n
⇔
22 , tehát n ∈ 8, 9,10 . Ha C nk -t k ≥ n -re is értelmezettnek tekintjük, akkor az 3 n = 11 is megoldás. b) Ha n ≥ 3 , akkor az egyenlőtlenség a következőképpen alakítható: n! (n + 2) ! 5 (n + 1) (n + 2) 5⋅ > ⇔ > ⇔ 1 4 (n − 2) 3 !(n − 3) ! 4!(n − 2) !
{
n>
}
20 (n − 2) > (n + 1)(n + 2) ⇔ ⇔ 20n − 40 > n 2 + 3n + 2 ⇔ n 2 − 17n + 43 < 0 . 17 ± 17 2 − 4 ⋅ 43 17 ± 117 = . 2 2 17 − 117 17 + 117 ∩ 3, ∞ ∩ ` , tehát A fentiek alapján n ∈ , 2 2 n1,2 =
{
}
n ∈ 4, 5, 6, 7, 8, 9,10,11,12,13 . Cp C p +i C p C p +i m − p + 1 16. Bizonyítsd be, hogy pm−1 − pm++i −i 1 : pn−1 − pn++i −i 1 = , ha p ≤ m C m C m +i C n C n +i n − p + 1 és p ≤ n !
a! (a − b )!b! a −b + 1 Megoldás. Általában , tehát = a! b (a − b + 1)!(b − 1)! bizonyítandó egyenlőség ekvivalens a következőképpen alakítható: m − p + 1 m + i − (p + i ) + 1 n − p + 1 (n + i ) − (p + i ) + 1 − − : = p p +i p p +i C ab = C ab −1
m + 1 n + 1 n + i + 1 m +i +1 = −1− + 1 : − + 1 − 1 = p p +i p +i p (m + 1) (p + i ) − p (m + i + 1) p (p + i ) = ⋅ = p (p + i ) (n + 1) (p + i ) − p (n + i + 1) mp + mi + p + i − pm − pi − p i (m + 1 − p ) m − p + 1 . = = = np + ni + p + i − pn − pi − p i (n + 1 − p ) n − p +1 17. Számítsd ki a következő összegeket: a)
n
∑k ⋅k ! ; k =1
b)
n
∑ (k + 1) k =1
2
⋅ k !;
a
Tartalomjegyzék
56
Számlálási feladatok, a kombinatorika elemei c) e)
n
k ; ∑ k =1 (k + 1) !
d)
∑ k 2 ⋅ C nk ;
f)
C nk ; ∑ k =1 (k + 1) ⋅ (k + 2) ⋅ (k + 3) Megoldás. a) n
n
∑ k !+ (k + 1)!+ (k + 2)! ; k =1
n
k =1
g)
k +2
n
h)
C nk ; ∑ k =1 k + 1 n
n
∑ (−1)k k =1
C nk . (k + 1) ⋅ (k + 2)
n
∑ k ⋅ k ! = ∑ ((k + 1)! − k !) = 2 ! − 1! + 3 ! − 2 ! + ... + (n + 1)! − n ! = (n + 1)! − 1 . k =1
b)
k =1
n
∑ (k + 1)
2
k =1
n
n
k =1
k =1
(
)
k! = ∑ (k + 1) ⋅ (k + 1)! = ∑ (k + 2)!− (k + 1)! =
(
) (
)
(
1
1
)
= 3 !− 2 ! + 4 !− 3 ! + ... + (n + 2) !− (n + 1) ! = (n + 2) !− 2 . c)
n
n
k
∑ (k + 1)! = ∑ k ! − (k + 1)! =
1 1 1 1 1 1 1 . = − + − + ... + − = 1 − (n + 1) ! 1 ! 2 ! 2 ! 3 ! n ! (n + 1) ! k +2 k +2 1 = = = d) k ! + (k + 1)! + (k + 2)! k !(1 + k + 1 + (k + 1)(k + 2)) k !(k + 2) k =1
k =1
=
k +1 1 1 = − , tehát (k + 2)! (k + 1)! (k + 2)!
n k +2 1 1 = − = ∑ ∑ k =1 k ! + (k + 1) ! + (k + 2) ! k =1 (k + 1)! (k + 2)! 1 1 1 1 1 1 1 1 . = − + − + ... + − = − 2 ! 3 ! 3 ! 4 ! (n + 1) ! (n + 2) ! 2 (n + 2) ! n
e)
n
n
n!
k =1
k =1
k !(n − k )!
∑ k 2C nk = ∑ k 2 ⋅
n
=∑ k 2 ⋅ k =1
n
n n ⋅ C nk−−11 = n ⋅ ∑ kC nk−−11 = k k =1 n
n
k =1
k =1
= n ∑ ((k − 1) + 1)C nk−−11 = n ∑ C nk−−11 + n ∑ (k − 1)C nk−−11 = k =1
n
(n − 1) !
k =1
(k − 1)!(n − k )!
= n ⋅ 2n −1 + n ⋅ ∑ (k − 1) n −1
= n2
n −2
+ n (n − 1) 2
n −2
= n2
n
= n 2n −1 + n ∑ (n − 1)C nk−−22 = k =2
(2 + n − 1) = n (n + 1) 2n −2 .
Tartalomjegyzék
57
Számlálási feladatok, a kombinatorika elemei f)
n n n! C nk 1 1 1 C nk ++11 = = ⋅ = (C n2+1 + ... + C nn++11 ) = ∑ ∑ ∑ k k k ! n k ! n n + + − + + 1 1 1 1 ) ( k =1 k =1 k =1 n
1 1 1 (2n +1 − C n0+1 − C n1+1 ) = (2n +1 − 1 − (n + 1)) = (2n +1 − n − 2) . n +1 n +1 n +1 k n n n! Cn 1 g) ∑ =∑ ⋅ = k =1 (k + 1)(k + 2)(k + 3) k =1 (k + 1)(k + 2)(k + 3) k !(n − k ) ! =
n (n + 3) ! 1 1 ⋅ = C nk ++33 = ∑ n + 1 n + 2 n + 3 k + 3 ! n − k ! n + 1 n + 2 n + 3 ( )( )( ) ( )( )( ) ( ) ( ) k =1 k =1 1 = ⋅ (C n4+3 + C n5+3 + ... + C nn++33 ) = (n + 1)(n + 2)(n + 3) 1 = ⋅ (2n +3 − C n0+3 − C n1+3 − C n2+3 − C n3+3 ) = (n + 1)(n + 2)(n + 3) 1 n +3 2 = ⋅ 2n +3 − 1 − (n + 6n + 14) . (n + 1)(n + 2)(n + 3) 6 n
=∑
n C nk n! 1 k = ∑ (−1) ⋅ = (k + 1)(k + 2) k =1 (k + 1)(k + 2) k!(n − k )! k =1 n 1 k = ∑ (−1) C nk ++22 = (n + 1)(n + 2) k =1 1 n +2 = −C n3+2 + C n4+2 − ... + (−1) C nn++22 ) = ( (n + 1)(n + 2) 1 = (0 − C n0+2 + C n1+2 − C n2+2 ) = (n + 1)(n + 2) 1 1 = ⋅ (−2 + 2n + 4 − n 2 − 3n − 2) = (−n 2 − n ) = 2 (n + 1) (n + 2) 2 (n + 1)(n + 2) −n (n + 1) −n = = . 2 (n + 1)(n + 2) 2 (n + 2) 18. Bizonyítsd be legalább két különböző módszer segítségével a
h)
n
n
∑ (−1)
∑C
k
k a
⋅ C bn −k = C an+b (Vandermonde féle) azonosságot!
k =0
1. megoldás. Két cserkészcsapat tagjai közül válasszunk ki egy n tagú csapatot. Ha az első csapatban a, a másodikban b tag van, akkor ezt C an+b módon tehetjük meg.
Másrészt C akC bn −k azoknak az n tagú csapatoknak a száma, amelyek az első n
cserkészcsapatból pontosan k tagot tartalmaznak. Így a
∑C C k a
n −k b
összeg ugyancsak
k =0
n
az összes n tagú csapatoknak a számát adja, tehát
∑C C k =0
k a
n −k b
= C an+b .
Tartalomjegyzék
58
Számlálási feladatok, a kombinatorika elemei
2. megoldás. Newton binomiális tétele alapján a (1 + x ) = 1 + C a1x + C a2x 2 + ... + C aa x a és b
(1 + x ) = 1 + C b1x + C b2x 2 + ... + C bb x b .
Az (1 + C a1x + C a2x 2 + ... + C aa x a ) (1 + C b1x + C b2x 2 + ... + C bb x b ) szorzat n-ed fokú n
∑C C
tagjának együtthatója éppen
k a
n −k b
.
k =0
a
a +b
b
(1 + x ) (1 + x ) = (1 + x )
Másrészt
a +b
= ∑ C ak+b x k , tehát az n-ed fokú tag k =0
C an+b .
együtthatója n
∑C C k a
n −k b
A
két
polinom
azonosságából
következik,
hogy
= C an+b .
k =0
19. Számítsd ki az alábbi összegeket! a) c)
n
2
∑ (C nk ) k =0 n
;
n
k 2 n
∑ k ⋅ (C )
;
b) c)
n
k 2 n
∑ k (C ) k =0 n
2
k 2 n
∑ k ⋅ (C ) k =0
2
k =0 n
; k 2 n
∑ (−1) ⋅ (C )
d)
k =0
Megoldás. a)
k 2 n
∑ k ⋅ (C )
b)
k
.
k =0
n
n
2
∑ (C nk ) k =0 n
= ∑ C nkC nn −k = C 2nn ; k =0
= ∑ (kC
k 2 n
)
k =0 n
n
n
2
2
= ∑ (nC nk−−11 ) = n 2 ⋅ ∑ (C nk−−11 ) = n 2 ⋅ C 2nn−−12 ; k =1
k =1
n
= ∑ kC nkC nn −k = ∑ C nk−−11C nn −k = n ⋅ C 2nn−−11 ; k =1
k =1
d) Az n
(1 + x ) = 1 + C n1x + C n2x 2 + C n3x 3 ... + C nn x n és n
n
(1 − x ) = 1 − C n1x + C n2x 2 − C n3x 3 ... + (−1) C nn x n kifejezések összeszorzásánál az n-ed fokú tag együtthatója n
∑ C nk (−1)
n −k
k =0
n
2
C nn −k = ∑ (C nn −k ) ⋅ (−1)
n −k
k =0
Másrészt (1 + x ) (1 − x ) = (1 − x n
n
2 n
)
n
n
2
= ∑ (−1) (C nk ) . k
k =0
= ∑ (−1) C nk x 2k , tehát k
k =0
0, n (−1) (C ) = n ∑ (−1) 2 ⋅ C 2 , k =0 n 20. Bizonyítsd be a következő azonosságokat: n
k
ha n páratlan;
k 2 n
a) C nn + C nn+1 + C nn+2 + ... + C mn = C mn ++11 ;
ha n páros. n
b) ∑ (−1)k −1 ⋅ k =1
1 k 1 1 ⋅ C n = 1 + + ... + ; k n 2
Tartalomjegyzék
59
Számlálási feladatok, a kombinatorika elemei m −2
n
d) 2 ⋅ ∑ C mk −1 ⋅ C mk +−11 =
2 c) C p1 + ∑ C p2++kk = C nn++p+ 1;
k =0
k =0
m −1
m −1 ⋅ C 2mm ; 2m − 1
e) 2 ⋅ (−1)m +1 ⋅ ∑ (−1)k ⋅ C nk ⋅ C n2m −k = (C nm ) − C nm . 2
k =0
Megoldás. a) Írjuk fel a C nk ++11 = C nk +1 + C nk egyenlőséget a következő értékekre:
C mn ++11 = C mn +1 + C mn C mn +1 = C mn +−11 + C mn −1 n C mn +−11 = C mn +−12 + C m− 2 ……………………. C nn++21 = C nn++11 + C nn+1
C nn++11 = C nn C mn ++11 = C mn + C mn −1 + C mn −2 + ... + C nn+1 + C nn . b) A matematikai indukció módszerét használjuk: 1 0 1 k −1 1 n = 1 -re ∑ (−1) ⋅ C 1k = (−1) ⋅ ⋅ C 11 = 1 . k 1 k =1 2 1 3 1 0 1 1 1 k −1 1 n = 2 -re ∑ (−1) ⋅ ⋅ C 2k = (−1) ⋅ ⋅ C 21 + (−1) ⋅ ⋅ C 22 = 2 − = = 1 + . 1 2 2 2 2 k k =1 n n 1 k −1 1 Feltételezzük, hogy ∑ (−1) ⋅ C nk = ∑ . k k =1 k =1 k n +1 n +1 k −1 1 k −1 1 (−1) C nk +1 = ∑ (−1) (C nk + C nk −1 ) = ∑ k k k =1 k =1 n n +1 n 1 1 1 1 n +1 k −1 k −1 k −1 = ∑ (−1) ⋅ C nk + ∑ (−1) C nk −1 = ∑ + (−1) ⋅ C nk +1 = ∑ k k k n + 1 k =1 k =1 k =1 k =1 n n +1 n n +1 1 1 1 1 1 k =∑ + ⋅ 1 − ∑ (−1) C nk +1 = ∑ + =∑ + + k n k n k 1 1 k =1 k =0 k =1 k =1 n
tehát a matematikai indukció elve szerint
∑ (−1) k =1
k −1
⋅
n 1 k 1 ⋅Cn = ∑ k k =1 k
bármely
n ∈ `* esetén. c) A matematikai indukció módszerét használjuk: n = 0 -ra C p1 + C p2 = C p2+1 igaz. Ha az összefüggés igaz n-re, akkor n +1
n
k =0
k =0
1)+2 C p1 + ∑ C p2++kk = C p1 + ∑ C p2++kk + C p3++nn+1 = C pn++n2+1 + C pn++n3+1 = C pn++n3+2 = C p(n+ +(n +1)+1 ,
tehát a matematikai indukció alapján az egyenlőség minden n ∈ ` esetén teljesül. d)
m −2
m −2
k =0
k =0
∑ C mk −1C mk +−11 = ∑ C mk −1C mm−−1k −2 = C 2mm−−22 .
Tartalomjegyzék
60
Számlálási feladatok, a kombinatorika elemei
Másrészt 2 ⋅ e)
m −1
2m − 1 m −2 ⋅ C 2m −2 = 2C 2mm −1 = C 2mm −1 + C 2mm−−11 = C 2mm . m −1
∑ (−1) C C k
k n
m −1
2m −k n
= C n0C n2m − C n1C n2m −1 + ... + (−1)
C nm −1C nm +1 =
k =0
m +1
= (−1)
m +2
C nm +1C nm −1 + (−1)
2m −1
C nm +2C nm −2 + ... + (−1)
2m
2m
C n2m −1C n1 + (−1) C n2mC n0 ,
tehát 2S + (−1) (C nm ) = ∑ (−1) C nkC n2m −k . A 19/d) feladathoz hasonlóan 2
m
k
k =0
2m
∑ (−1) C C k
k n
2m −k n
m
= (−1) ⋅ C nm , tehát
k =0
2
2S = (−1) C nm − (−1) (C nm ) és így m
m +1
2 (−1)
m
m −1
⋅ ∑ (−1) C nkC n2m −k = (C nm ) − C nm . 2
k
k =0
21. Határozd meg a) a (3x + y − 3)10 kifejtés együtthatóinak összegét! 9
1 b) a 3 x + 3 kifejtés hatodik tagját! x n T 1 1 c) az n értékét, ha a 3 2 + 3 kifejtésében 7 = ! 6 Tn −5 3 120
1 2 d) az + 3 3
kifejtés legnagyobb tagját! 2001
e) az (1 + 3 5 )
kifejtés racionális tagjait!
f) az x 6 együtthatóját az (1 + x )n + (1 + x )n −1 kifejtésében (a tagok összevonása után), ha a kifejtésben megjelenő binomiális együtthatók összege 1536 g) az m értékét ha a (2 + m )m kifejtés legnagyobb tagja a tizedik tag! 2001
h) az (2x + x 2 )
kifejtés hányadik tagjának a legnagyobb az együtthatója?
Megoldás 10 a) Az együtthatók összege (3 − 1 − 3) = 1 . 9
9 1 9−k b) 3 x + 3 = ∑ C 9k ⋅ ( 3 x ) x k =0
k
1 9−k ⋅ 3 . Tk +1 = C 9k ( 3 x ) x
5
k
1 ⋅ 3 , tehát x
4 5 1 − − 1 4 1 T6 = C 95 ( 3 x ) ⋅ 3 = C 95 ⋅ x 3 ⋅ x 3 = C 95 ⋅ x 3 = C 95 ⋅ 3 . x x n −6
c) T7 = C ⋅ ( 2 ) 6 n
3
6
n −6
6 1 1 ⋅ 3 , Tn −5 = C nn −6 ⋅ ( 3 2 ) ⋅ 3 3 3
Mivel C n6 = C nn −6 , következik, hogy
.
Tartalomjegyzék
61
Számlálási feladatok, a kombinatorika elemei −(n −12)
n −12 1 T7 = ( 3 2) ⋅ 3 3 Tn −5 így n = 9 . n −k 1 k d) Tk +1 = C 120 ⋅ 3
=2
n −12 3
⋅3
n −12 3
=6
n −12 3
n −k
k
= 6−1 , tehát k
n − 12 = −1 , és 3 n
2 1 1 1 k k ⋅ = C 120 ⋅ ⋅ ⋅ 2k = C 120 ⋅ ⋅ 2k = 3 3 3 3 n 1 k = ⋅ C 120 ⋅ 2k , ahol n = 120 . 3
Tk +1 2 ⋅ (120 − k + 1) C k ⋅ 2k = k −1201 k −1 = . Ebből következik, hogy k ≥ 81 -re Tk +1 < Tk Tk C 120 ⋅ 2 k és k ≤ 81 -re Tk +1 > Tk , tehát a legnagyobb tag T81 . k
k
k k e) Tk +1 = C 2001 ⋅ 5 3 . Ez pontosan akkor racionális, ha k # 3 , tehát a ( 3 5 ) = C 2001
(3k + 1) -edik tag racionális k = 0, 667 -re. n −1
n
f) (1 + x ) + (1 + x )
n
n
n −1
k =0 n−1
k =0 n
n −1
= ∑ C nk ⋅ x k + ∑ C nk−1 ⋅ x k = ∑ (C nk + C nk−1 ) x k + x n . k =0
n−1
Az együtthatók összege 2 + 2 , tehát a 2 + 2 = 1536 = 3 ⋅ 29 egyenletet kell megoldanunk. Az egyenlet egyetlen megoldása az n = 10 . Ebben az esetben x 6 10! 9! 7 ⋅ 8 ⋅ 9 ⋅ 10 7 ⋅ 8 ⋅ 9 együtthatója: C 106 + C 96 = + = + = 210 + 84 = 294 . 64! 63! 2⋅3⋅4 2⋅3 T m (m − k + 1) g) Tk +1 = C mk ⋅ 2m −k ⋅ m k , tehát k +1 = . Tk 2k T Látható, hogy rögzített m-re k-ban elsőfokú egyenlőtlenséghez vezet a k +1 ≥ 1 Tk egyenlőtlenség, tehát a tagok egy ideig növekednek, majd csökkennek. Így elégséges a T10 ≥ T9 és T10 ≥ T11 egyenlőtlenségeket megoldani. Az egyetlen természetes szám, amely teljesíti az m (m − 9) ≤ 20 és m (m − 8) ≥ 18 egyenlőtlenségeket az m = 10 . k h) Ha Ek a k-adik tag együtthatója, akkor Ek +1 = C 2001 ⋅ 22001−k , tehát Ek +1 2002 − k . Ebből következik, hogy k ≤ 667 -re Ek +1 ≥ Ek és k ≥ 668 -ra = Ek 2k Ek +1 ≤ Ek , tehát a legnagyobb együttható a 668-adik tag együtthatója.
22. Bizonyítsd be, hogy a (2 + 3 )
2001
hogy a (2 + 3 )
2001
+ (2 − 3 )
2001
kifejezés értéke egész szám és,
szám egészrésze páratlan!
Megoldás. Matematikai indukcióval igazoljuk, hogy létezik olyan An , Bn ∈ ` ,
amelyre
Tartalomjegyzék
62
Számlálási feladatok, a kombinatorika elemei
(2 + 3 ) = An + Bn n (2 − 3 ) = An − Bn n
3 és 3.
n = 1 -re A1 = 2 és B1 = 1 , n = 2 -re A2 = 7 és B2 = 4 .
Ha (2 + 3 ) = (An + Bn 3 ) és (2 − 3 ) = An − Bn 3 , akkor n
(2 + (2 −
n
n +1
3)
n +1
3)
= (An + Bn 3 )(2 + 3 ) = (2An + 3Bn ) + (An + 2Bn ) 3 , és
= (An − Bn 3 )(2 − 3 ) = (2An + 3Bn ) − (An + 2Bn ) 3 , tehát
An +1 = 2An + 3Bn (∈ ` ) és Bn +1 = An + 2Bn (∈ ` ) . Az előbbiek alapján n n (2 + 3 ) + (2 − 3 ) = 2An ∈ ` bármely n ∈ ` esetén,
( )
tehát n = 2001 -re is. 2 − 3 ∈ 0, 1 tehát (2 − 3 )
2001
( )
∈ 0, 1 . Így (2 + 3 ) egész n
része 2An − 1 és ez páratlan. 2001
23. Legalább hány irracionális tagja van a ( n + 4 n ) kifejtésnek ha n természetes szám és nem írható fel egyetlen természetes szám negyedik hatványaként sem? 2001−k
k Megoldás. Tk +1 = C 2001 ⋅( n)
k
k ⋅ ( 4 n ) = C 2001 ⋅n
2001−k 2
k k ⋅ n 4 = C 2001 ⋅n
{
4002−k 4
.
}
Ha n nem teljes négyzet, akkor meg kell vizsgálni, hogy milyen k ∈ 0,1, 2,..., 2001 4002 − k . 4002 − k akkor osztható 4-gyel, ha k = 4 p + 2 4 4002 − k ∈ ` . Ebből következik, hogy alakú, tehát k-nak 500 különböző értékére 4 2002 − 500 = 1502 irracionális tagja van a kifejtésnek. Ha n teljes négyzet, akkor 4002 − k kell természetes szám legyen, és így csak 1000 irracionális tag létezik. 2
re természetes szám a
24. Egy n oldalú konvex sokszögben meghúzzuk az átlókat. Legtöbb hány belső metszéspont keletkezhet? Megoldás. A sokszögnek bármely négy csúcsa pontosan egy belső metszéspontot határoz meg, tehát C n4 a belső metszéspontok maximális száma. 25. A hadsereg fegyverraktára a mellékelt ábrán az R-el jelölt mezőn található, míg a hadtest a H-val jelölt mezőn állomásozik. A raktárból egy fegyverszállítmányt kell eljuttatni a hadtesthez. A szállítmány minden mezőről a jobboldali vagy az alatta elhelyezkedő szomszédos mezőre juthat át. Néhány gerilla aláaknázta a szürkével befestett mezőket. Ha a szállítmány egy ilyen mezőre kerül, akkor felrobban. Mennyi a valószínűsége annak, hogy a hadtest megkapja a szállítmányt?
Tartalomjegyzék
63
Számlálási feladatok, a kombinatorika elemei R
H Ha csak egy mezőt tudnának aláaknázni a gerillák, és ez nem lehet a vastag vonalakkal bekerített részen, melyik mezőt érdemes aláaknázni ahhoz, hogy a szállítmány felrobbanásának valószínűsége a lehető legnagyobb legyen? Megoldás. Az R-ből H-ba vezető utak száma C 157 . A hadtest akkor kapja meg a szállítmányt, ha az olyan úton halad, amely nem érinti az egyik befestett mezőt sem. Az alábbi ábrán az ilyen utakat számoltuk össze:
1 1 1 1 1 1 1 1 1
1 2 3 4 5 1 2 3
1 3 6 10 15 15 16 18 21
1 4 10 20 35 50 66 84 105
1 5 15 35 70 120 186 270 375
1 6 21 70 190 376 646 1021
1 7 28 28 98 288 664 1310 2331
1 8 36 64 162 450 1114 2424 4755
4755 317 = ≈ 74% . 6435 429 Ha csak egy mezőt aknáznak alá, akkor megszámoljuk azokat az utakat, amelyek áthaladnak e mezőn. Ha az m-edik sor és n-edik oszlopban levő, A-val jelölt, mezőt aknázzák alá, akkor az R-ből A-ba vezető utak száma C nn+−m1 −2 és az A-ból H-ba vezető
A keresett valószínűség
utak száma C 178−−nm −n . Így az A-n áthaladó utak száma C nn+−m1 −2 ⋅ C 178−−nm −n , és annak a valószínűsége, hogy a szállítmány felrobban
C nn+−m1 −2 ⋅ C 178−−nm −n . A mellékelt C 157
táblázatban minden mezőre ráírtuk a C nn+−m1 −2 ⋅ C 178−−nm −n szorzat értékét. A táblázatban szürkére festettük azokat a mezőket, amelyeket a legérdemesebb aláaknázni. Abban az esetben, ha a kijelölt négy mező egyikét aknázzuk alá, a keresett valószínűség értéke 2520 2520 = ≈ 39% . C 157 6435
Tartalomjegyzék
64
Számlálási feladatok, a kombinatorika elemei
495
165
45
9
1
1320
600
216
56
8
2100
1260
588
196
36
792
1848
2520
2520
1960
1176
504
120
330
1050
1890
2450
2450
1890
1050
330
120
504
1176
1960
2520
2520
1848
792
36
196
588
1260
2100
8
56
216
600
1320
1
9
45
165
495
26. Egy csomag francia kártyát megkevertünk majd egyesével kihúzzuk a lapokat. Hányadik helyen a legvalószínűbb a második ász kihúzása? Megoldás. Annak valószínűsége, hogy a második ászt az n-edik helyen húzzuk ki 4 ⋅ C n1−1 ⋅V48n −2 ⋅ 3 12 = ⋅ (n − 1) ⋅ (52 − n ) ⋅ (51 − n ) . Ez a valószínűség n V52 49 ⋅ 50 ⋅ 51 ⋅ 52 akkor a legnagyobb, ha a (2n − 2) (52 − n )(51 − n ) szorzat a legnagyobb. Mivel a tényezők összege 101, a szorzat akkor maximális, ha a tényezők a lehető legközelebb vannak egymáshoz. Ez akkor teljesül, ha n = 18 , tehát a 18-ik helyen a legvalószínűbb a második ász kihúzása. 27. Lehetséges-e két kockát úgy cinkelni, hogy a feldobásuk után a kapott számokat összeadva azonos valószínűséggel jelenjen meg minden lehetséges összeg? Megoldás. Tegyük fel, hogy a kockákat cinkeltük és az egyik kockával való dobásnál az 1, 2, 3, 4, 5 és 6-os valószínűsége rendre p1 , p2 , p3 , p4 , p5 illetve p6 , a másik kockánál pedig q1 , q2 , q 3 , q 4 , q 5 és q 6 . A
(p1 + p2x + p3x 2 + p4x 3 + p5x 4 + p6x 5 )(q1 + q2x + q 3x 2 + q 4x 3 + q 5x 4 + q 6x 5 ) szorzatban x k együtthatója éppen annak a valószínűsége, hogy az összeg k + 2 . Ha a kívánt cinkelés lehetséges volna, akkor ez a szorzat egyenlő kellene legyen 1 x 11 − 1 ⋅ (1 + x + x 2 + x 3 + x 4 + x 5 + ... + x 10 ) -nel, azaz -gyel. Mivel a 11 11 (x − 1) baloldalon található ötödfokú polinomoknak van legalább egy valós gyöke, és a jobb oldalon álló polinomnak nincs, a kívánt cinkelés lehetetlen. 28. Mennyi a valószínűsége annak, hogy két egyforma kockával dobva 24 dobásból lesz egy dupla hatosunk?
Tartalomjegyzék
65
Számlálási feladatok, a kombinatorika elemei
Megoldás. Annak a valószínűsége, hogy egy dobásból nem lesz dupla hatosunk 24 20 20 . Annak a valószínűsége, hogy 24 dobás után nincs dupla hatosunk , tehát 21 21 annak a valószínűsége, hogy 24 dobásból lesz legalább egy dupla hatosunk 24 20 1 − ≈ 0, 68 . Ha a kockákat nem tekintjük egyformáknak, akkor az esemény 21 24
35 valószínűsége 1 − ≈ 0, 491 . 36 29. Bizonyítsd be, hogy ha egy pénzérmét 200-szor feldobunk, akkor 95%-nál nagyobb annak a valószínűsége, hogy lesz legalább hat egymás utáni fej vagy hat egymás utáni írás! Megoldás. Jelöljük x n -nel az n hosszúságú dobássorozatok közül azoknak a számát, amelyek tartalmaznak legalább 6 hosszúságú csupa fej vagy csupa írás sorozatot. Az ilyen sorozatokat nevezzük „jó sorozat”-nak. A „jó sorozat”-okat az első legalább 6-os fej vagy írássorozat első elemének sorszáma szerint számoljuk és célunk egy rekurziót felírni az x n sorozat elemeire. Az ötlet a következő: a 6-os fej vagy írássorozat vagy már az első n – 1 dobásban bekövetkezett, vagy az utolsó 6 dobás egyforma és hátulról a 7-ik dobás ezektől eltér, valamint az első n – 7 dobásban nincs 6-os fej vagy írássorozat. Ha n ≤ 12 , akkor a dobássorozatban nem lehet két különböző és diszjunkt legalább 6-os fej vagy írássorozat, tehát a 6-os fej vagy írássorozat vagy már az első n–1 dobásban bekövetkezett, vagy az utolsó 6 dobás egyforma és hátulról a 7-ik dobás ezektől eltér. Az első esetben 2x n −1 dobás lehetséges, míg a másodikban 2n −6 dobás, tehát érvényes a következő összefüggés: x n = 2x n −1 + 2n −6 , ha n ≤ 12 .
Ha n ≥ 12 , akkor a második esetben 2 ⋅ (2n −7 − x n −7 ) „jó sorozat” létezik, tehát x n = 2x n −1 + 2 ⋅ (2n −7 − x n −7 ) , ha n ≥ 12 .
b xn sorozatra átírva a kapott relációt, a bn = bn −1 − n −6 összefüggéshez n 64 2 jutunk ( bn annak a valószínűsége, hogy a sorozat nem „jó sorozat”). A bn sorozat
A bn = 1 −
179
63 1 bn −1 és így b200 < b21 1 − < 0, 75 ⋅ 0, 06 = 0, 045 . 64 64 Ebből következik, hogy egy 200 hosszúságú fej / írás dobássorozat több mint 95%-os valószínűséggel tartalmaz legalább 6 hosszúságú csupa fej vagy csupa írás sorozatot.
csökkenő, tehát a bn <
n
30. Számítsd ki az S n = ∑ (−1)k ⋅ C nk ⋅ C 3nn −k összeget! k =0
(Megyei olimpia, 1997, Maros megye)
Tartalomjegyzék
66
Számlálási feladatok, a kombinatorika elemei 3n −k
Megoldás. C 3nn −k az együtthatója x n -nek az (1 + x ) k
k n
(−1) C C
n 3n −k
az x
n
k
3n −k
k n
együtthatója (−1) C (1 + x )
összeg az x n együtthatója a
n
∑ (−1) C k
k n
3n −k
(1 + x )
kifejtésében, tehát
kifejtésében. Így az Sn
összegben. Másrészt
k =0
n
∑ (−1) C nk (1 + x ) k
3n −k
2n
= (1 + x )
k =0
n
∑ (−1) C k
k n
n −k
(1 + x )
=
k =0
n
= (1 + x ) ⋅ ((1 + x ) − 1) = x n (1 + x ) , tehát x n együtthatója 1. 31. Bizonyítsd be, hogy a C n1 , C n2 ,..., C nn −2 és C nn −1 számok legnagyobb közös osztója 2n
2n
pontosan akkor kettő, ha az n kettőnek hatványa! Megoldás. A Pascal háromszögben a páros számok helyére írjunk 0-t és a páratlanok helyére 1-et. Így minden számot a 2-vel való osztási maradékával helyettesítünk, tehát a 0 ⊕ 0 = 0 , 0 ⊕ 1 = 1 ⊕ 0 = 1 és 1 ⊕ 1 = 0 szabályok szerint a háromszög képzési szabálya megmarad. A mellékelt ábra alapján látható, hogy az 5. és 8. sor közt a széleken megismétlődik az első négy sor (lásd a bekeretezett háromszögeket) és a középső háromszögben csupa 0 áll. A 9. és 16. sor közt a széleken megismétlődik az első nyolc sor és középen csupa nulla áll. Hasonló módon a 2n + 1 . és 2n +1 . sorok közt a széleken megismétlődik az első 2n sor és közepében csupa nulla lesz. (ha ez így működik n-ig, akkor a 2n . sorban a két szélső szám kivételével csupa 0 áll, tehát a következő 2n − 1 sorban középen csupa 0
fog állni és így a két szélen ugyanaz történik, mint az első 2n sorban, hisz talál a kezdőérték és a képzési szabály). Ez alapján a két szélső szám kivételével akkor kapunk csupa 0-t, ha a sor száma 2n + 1 , tehát a C nj j = 1, n − 1 számok csakis akkor k −1
mind párosak, ha n = 2k . Ebben az esetben a C 22k
szám nem osztható néggyel és a
C 21k = 2k , tehát a legnagyobb közös osztó 2. k −1
A bizonyítás teljességéhez elégséges igazolni, hogy C 22k
nem osztható 4-gyel.
Tartalomjegyzék
67
Számlálási feladatok, a kombinatorika elemei
C
(2k ) !
2k −1 2k
(2k ) ! = 2 . ((2k −1 ) !)
prímtényezős felbontásában 2 hatványkitevője 2k + 2k −1 + 2k −2 + ... + 2 + 1 , k −1
tehát C 22k -ben a 2 hatványkitevője 1 + 2 + 22 + ... + 2k − 2 (1 + 2 + 22 + ... + 2k −1 ) = 1 . 32. Ha m, n ∈ `, n ≠ 0 és m ≤ n jelöljük S m -mel a C n0 + C n1 + C n2 + ... + C nm összeget. Bizonyítsd be, hogy C n0 ⋅ S 0 + C n1 ⋅ S1 + ... + C nn ⋅ Sn = 22n −1 + C 2nn−−11 ! (Országos olimpia, 1993) Megoldás n
n
k
n
k =0
k =0 n
j =0
k
n
n
n
n
j =0
k=j
∑ C nk ⋅ Sk = ∑ C nk ∑ C nj = ∑ ∑ C nkC nj = ∑ ∑ C nkC nj = ∑ C nj ∑ C nk = k = 0 j =0
n
j =0 k = j n j n j =0
= ∑ C nj ⋅ (2n − S j −1 ) = 2n ⋅ ∑ C − ∑ C nj (S j − C nj ) = j =0
j =0
n
n
n
= 22n + ∑ (C nj ) − ∑ C nj S j = 22n + C 2nn − ∑ C nj S j . j =0 n
2
j =0
Ebből következik, hogy 2 ⋅ ∑ C nk Sk = 22n + C 2nn , tehát k =0
j =0
n
∑C
k n
S k = 22n −1 + C 2nn−−11 .
k =0
33. Határozd meg az (x n )n ∈N sorozat általános tagjának képletét, ha x 0 = 1, x 1 = 2 és x n +1 = 2 ⋅ x n +
4 ⋅ (2n − 1) ⋅ x n −1, n +1
∀n ≥1.
(Hegyi Lajos emlékverseny, 1998) 1. megoldás. Matematikai indukcióval igazolható, hogy x 2n = C 2nn . 2. megoldás. (Szabó Vass Melinda megoldása) Keressük az általános tagot x n = 2n ⋅ an alakban. Visszahelyettesítés és egyszerűsítés után a rekurzió a következő alakba írható: (n + 1)an +1 = (n + 1)an + (2n − 1)an −1 Ha mindkét oldalhoz hozzáadunk n ⋅ an -net, akkor az előbbi összefüggés (n + 1)an +1 + nan = (2n + 1)an + (2n − 1)an −1 alakban írható. Ha ezt az egyenlőséget n − 1 -re is felírjuk és a két egyenlőséget kivonjuk egymásból, az (n + 1)an +1 − (n − 1)an −1 = (2n + 1)an − (2n − 3)an −2 egyenlőséghez jutunk. Ebből következik, hogy (n + 1)an +1 − (2n + 1)an = (n − 1)an −1 − (2n − 3)an −2 , ∀ n ≥ 3 ,
(n + 1)an +1 − (2n + 1)an = 3a 3 − 5a2 = 0 , 2n − 1 an = an −1 , (n + 1)an +1 − (2n + 1)an = a1 − a = 0 . Eszerint n
tehát
vagy tehát
Tartalomjegyzék
68 an =
Számlálási feladatok, a kombinatorika elemei
2n − 1 2n − 3 3 1 (2n − 1) !! ⋅ ⋅ ... ⋅ ⋅ = n n −1 2 1 n !
és
így
x n = 2n
(2n − 1) !! n !
= C 2nn ,
∀n ≥ 0. 34. Az alábbi háromszög képzési szabálya ugyanaz, mint a Pascal háromszögnek csak az n.-edik sor első és utolsó eleme minden n ≥ 1 -re éppen n. Határozd meg az n.-edik sor k.-adik elemének képletét! 1 2 2 3 4 3 4 7 7 4 5 11 14 11 5 6 16 25 25 16 6 Megoldás. A mellékelt ábrán látható, hogy az első háromszög külső elemeit elhagyva és a maradék táblázat minden eleméből kivonva a Pascal háromszög megfelelő elemét éppen a vizsgált háromszöghöz jutunk. 1 1 1 1 2 1 1 1 3 3 1 1 1 1 4 6 4 1 1 2 1 1 5 10 10 5 1 1 3 3 1 1 6 15 20 25 6 1 1 4 6 4 1
Így az n-edik sor k-adik eleme C nk ++11 − C nk−1 . Ezt a matematikai indukció módszerével igazolhatjuk.
Tovább
