Ebben a fejezetben olyan feladatokkal foglalkozunk, amelyek többsége különösebb matematikai előképzettség nélkül, “józan paraszti ésszel” is megoldható. Természetesen az ismeretek rendszerezése és pontos definiálása most is segíti a problémák közötti eligazodást.

Egy sakktábla két átellenes sarkán levő mezőket kivágjuk. A megmaradt mezők lefedhetők-e 2×1-es dominókkal? (70. ábra)

a) Igazoljuk, hogy egy 30 fős osztályban van legalább két olyan ember, aki ugyanabban a hónapban született!

b) Igazoljuk, hogy egy 30 fős osztályban van legalább három olyan ember, aki ugyanabban a hónapban született!

b) Készítsünk 12 dobozt a 12 hónap nevével ellátva és egy-egy darab papírra írjuk fel az osztály tagjainak nevét. Ezután a neveket tartalmazó cédulákat tegyük bele abba a dobozba, amelyen az illető születési hónapjának neve található. Ha minden dobozba legfeljebb két cédula kerülne, akkor 6 papírdarab kimaradna, ezért biztosan lesz legalább egy olyan doboz, amelybe legalább három név kerül.

Mivel “halmazos” feladatral van szó, célszerűnek látszik Venn-diagramot készíteni (71. ábra).

A kapott összefüggést szita-formulának (logikai szita) nevezzük. Hasonló összefüggések teljesülnek kettőnél több halmazra is, de ezekkel itt nem foglalkozunk.

Bizonyítsuk be, hogy az első n pozitív egész szám összege !

Az ilyen szerkezetű állítások bizonyítása gyakran az úgynevezett teljes vagy matematikai indukció módszerével történik. Ez az eljárás két lépésből áll.

1. lépés: belátjuk az első (vagy az első értelmes) elemi állítást

2. lépés: igazoljuk, hogy az állítások igaz volta “öröklődik”, azaz bebizonyítjuk, hogy a k-adik állításból következik a (k+1)-edik, minden (szóba jövő) pozitív egész k-ra.

a) Egy futóverseny nyolcas döntőjében hányféleképpen alakulhat a végső sorrend, ha nincs holtverseny?

a) Az első helyezett a nyolc résztvevő bármelyike lehet, a második helyezett ettől függetlenül a maradék hét résztvevő bármelyike lehet, azaz az első két helyezés 8× 7=56 féleképpen alakulhat. A gondolatmenetet folytatva az adódik, hogy a nyolc helyezés 8× 7× 6× 5× 4× 3× 2× 1=40320 féleképpen valósulhat meg.

b) Az előző rész gondolatmenetét követve a dobogós helyezések 8× 7× 6=336 féleképpen oszthatók ki.

Az előző példa megoldása után esetleg gondolhatnánk, hogy a lehetséges küldöttségek száma 30× 29× 28=24360. Csakhogy ebben a 24360 esetben különbséget teszünk a küldöttséget alkotó diákok sorrendje szerint is, ami a feladatnak nem felel meg. Minden egyes 3 fős küldöttséget hatszor számoltunk meg, mert három ember 3× 2× 1=6 féleképpen állítható sorrendbe. Ezért a helyes eredmény a 24360 hatoda, azaz a lehetséges küldöttségek száma 4060.

A fejezet végén találhatunk önálló megoldásra kitűzött feladatokat.

Az 5. példa a) részéből kiindulva megismerkedünk néhány új fogalommal.

1-től n-ig a természetes számok szorzatát n faktoriálisnak nevezzük. Jele: n! Megállapodás szerint 0!=1. (A későbbiekben látni fogjuk e megállapodás célszerűségét.)

n különböző elem egy lehetséges sorrendjét az n elem egy (ismétlés nélküli) permutációjának nevezzük. Az összes (ismétlés nélküli) permutációk számát P_n jelöli.

Ha n elem között egyenlők is vannak, mégpedig k₁, k₂, …, k_r darab (k₁+k₂+…+k_r = n), akkor az n elem egy lehetséges sorrendje az elemek egy ismétléses permutációja. Az összes ismétléses permutációk számát jelöli.

n különböző elem összes (ismétlés nélküli) permutációinak száma P_n = n!.

Tekintsünk egy n darab cellából álló sort (72.ábra).

Az első helyre az n elem bármelyike kerülhet, ettől függetlenül a második helyre (n−1) elem kerülhet, és így tovább. Tehát az összes lehetséges sorrendek száma n× (n−1)× (n−2)× … × 2× 1 = n!.

Először tegyük fel , hogy mind az n elem különböző. Ekkor az előző tétel alapján összesen n! féle sorrend lehetséges. E permutációk között valójában annyi egyforma van, ahány módon az egyenlőket egymás között cserélgethetjük. A k₁ egyforma elemet k₁! féleképpen, a k₂ egyforma elemet k₂! féleképpen stb. cserélgethetjük. Így az egyenlő permutációk száma k₁!× k₂!× …× k_r!. Tehát az ismétléses permutációk száma .

Ha n különböző elemből k darabot sorba rendezünk, akkor az n elem egy k-ad osztályú (ismétlés nélküli) variációját kapjuk. Az összes k-ad osztályú variációk számát jelöli.

Ha n különböző elem közül k-szor választunk egy-egy elemet (ugyanazt az elemet többször is választhatjuk) és azokat sorba rendezzük, akkor az n elem egy k-ad osztályú ismétléses variócióját kapjuk. Az összes ismétlésese variációk számát jelöli.

n különböző elem k-ad osztályú ismétlés nélküli variációinak száma .

A bizonyítás az ismétlés nélküli permutációkra vonatkozó gondolatmenet alapján történik. Az első helyre az n elem bármelyike kerülhet, a második helyre a maradék (n−1) elem bármelyike kerülhet, … , a k-adik helyre a maradék (n−k+1) elem bármelyike kerülhet. Tehát az összes lehetőségek száma .

n különböző elem k-ad osztályú ismétléses variációinak száma n^k.

A k hely mindegyikére egymástól függetlenül az n elem bármelyike kerülhet, így az összes lehetőségek száma n^k.

Ha n különböző elem közül kiválasztunk k darabot a sorrendre való tekintet nélkül, akkor az n elem egy k-ad osztályú (ismétlés nélküli) kombinációját kapjuk. Az összes k-ad osztályú kombinációk számát jelöli.

n különböző elem k-ad osztályú (ismétlés nélküli) kombinációinak száma .

A bizonyítás az ismétléses permutációkra vonatkozó tétel bizonyításához hasonló. Ha a k darab kiválasztott elem sorrendjét is figyelembe vesszük, akkor a lehetséges kiválasztások száma n× (n−1)× (n−2)× …× (n−k+1). Az így kapott k-asok között annyi egyenlő van, ahány különböző sorrendje lehetséges k különböző elemnek, azaz k!. Az összes kombinációk száma tehát .

A kombinációk számára kapott képletet egyszerűbb alakban is felírhatjuk, ha a törtet bővítjük (n−k)!-sal: . Az kifejezést binomiális együtthatónak nevezzük és -val jelöljük (ejtsd “n alatt a k”).

201. Hány 15-tel kezdődő ötjegyű szám képezhető az 1, 3, 5, 7, 9 számjegyekből, ha egy számjegyet csak egyszer használhatunk fel?

202. Hány 5-tel osztható hatjegyű szám képezhető a 0, 1, 2, 3, 4, 5 számjegyekből, ha minden számjegy csak egyszer szerepelhet?

203. A 4, 4, 5, 5, 6 számjegyekből hány 56-tal kezdődő ötjegyű szám készíthető?

204. Az 1, 1, 1, 2, 2, 3, 3 számjegyekből hány 13-mal kezdődő hétjegyű számot lehet készíteni?

205. A MATEMATIKA szó betűinek hány permutációja van?

206. Hány ötjegyű szám készíthető az 1-es és 2-es számjegyek felhasználásával?

Megoldások 201-206

207. Hány öttel osztható négyjegyű szám képezhető az 1, 3, 5, 7, 9 számjegyekből, ha egy számjegy csak egyszer szerepelhet?

208. Az 1, 3, 5, 7, 9 számjegyekből hány ötjegyű számot állíthatunk elő, ha egy számjegyet többször is felhasználhatunk?

209. Csupa páratlan számjegyből hány 1-gyel kezdődő ötjegyű számot készíthetünk?

210. Egy hatelemű halmaznak hány háromelemű részhalmaza van?

211. Egy futóverseny előfutamának egyik csoportjában tíz versenyző indul. Az első négy versenyző jut a középdöntőbe. Hányféleképpen alakulhat a továbbjutók csoportja?

212. Egy dobozban 15 cédula van, amelyekre rendre az 1, 2, …, 15 számokat írtuk. Húzzunk ki egymás után öt cédulát visszatevés nélkül. Hány olyan eset van, amikor a kihúzott számok növekvő sorrendben követik egymást?

Megoldások 207-212