´ 1. FELADATSOR MEGOLDASAI
´leti a ´ ttekinte ´s Elme Ism´ etl´ es n´ elk¨ uli vari´ aci´ o. Egy n elem˝ u halmazb´ol k´epezhet˝o k elem˝ u sorozatok sz´ama, ha a sorozatok nem tartalmaznak ism´etl˝ od´est n! (1) = n · (n − 1) · . . . · (n − k + 2) · (n − k + 1). (n − k)! Megjegyz´es. 0! = 1 defin´ıci´ o szerint. P´elda. Az {a, b, c} halmaz elemeib˝ ol alkotott 2 elem˝ u sorozatok sz´ama sorozatok a k¨ ovetkez˝ ok: ab, ac, ba, bc, ca, cb.
3! (3−2)!
=
3! 1!
= 6. Ezek a
Ism´ etl´ eses vari´ aci´ o. Egy n elem˝ u halmazb´ol k´epzett k elem˝ u sorozatok sz´ama, ha a sorozatok tartalmazhatnak ism´etl˝ od´est egyenl˝ o (2)
nk .
P´elda. Az {a, b, c} halmaz elemeib˝ ol alkotott, ism´etl˝od´est is tartalmazhat´o 2 elem˝ u sorozatok 2 sz´ ama 3 = 9. Ezen sorozatok a k¨ ovetkez˝ ok: aa, ab, ac, ba, bb, bc, ca, cb, cc. Ism´ etl´ es n´ elk¨ uli kombin´ aci´ o. Egy n elem˝ u halmaz k elemsz´am´ u r´eszhalmazainak sz´ama n n! n · (n − 1) · . . . · (n − k + 1) (3) = = . k (n − k)! k! 1 · 2 · ... · k 3 P´elda. Az {a, b, c} halmaz 2 elem˝ u r´eszhalmazainak sz´ama = 3. A k´et elem˝ u r´eszhalmazok 2 a k¨ ovetkez˝ ok: {a, b}, {a, c}, {b, c}. A nulla elem˝ u r´eszhalmazok sz´ ama 30 = 1 ´es ez a halmaz az u ¨res halmaz. Ism´ etl´ eses kombin´ aci´ o. n fajta t´ argyb´ ol (mindegyikb˝ol tetsz˝olegesen sok ´all rendelkez´esre) k darabb´ ol ´ all´ o csoportokat k´epez¨ unk. Ezek sz´ama: n+k−1 (4) . k P´elda. Ha 3 fajta t´ argyunk van, a, b, c, akkor a 2 darabb´ol ´all´o csoportok sz´ama 3+2−1 = 2 4 ovetkez˝ ok: (a, a), (a, b), (a, c), (b, b), (b, c), (c, c). 2 = 6. Ezen csoportok a k¨ Ism´ etl´ eses permut´ aci´ o. k k¨ ul¨ onb¨ oz˝ o fajta t´argyunk van. Az els˝o fajt´ab´ol van n1 , a m´asodikb´ol n2 , ´es ´ıgy tov´ abb, a k-dik fajt´ ab´ ol pedig nk darabunk van. Ezeket (5)
(n1 + . . . + nk )! n1 ! · · · nk !
-f´elek´eppen lehet sorba rakni (az azonos fajta t´argyakat nem k¨ ul¨onb¨oztetj¨ uk meg). 1
´ 1. FELADATSOR MEGOLDASAI
2
P´elda. Van 3 fajta t´ argyunk: a, b, c. Az a-b´ol van 2, a b-b˝ol 1 ´es a c-b˝ol szint´en 1. Ezeket (2+1+1)! 4! = 2! = 12 m´ odon lehet sorba rakni. Ezen sorozatok a k¨ovetkez˝ok: aabc, aacb, abac, 2! 1! 1! abca, acab, acba, baac, baca, bcaa, caab, caba, cbaa. ´ sa Feladatok megolda Permut´ aci´ ok. 1. Egy ¨ osszej¨ ovetelen 5 fi´ u ´es 5 l´ any vesz r´eszt. A t´ancol´o p´aroknak h´anyf´ele ¨osszet´etele lehets´eges, ha mindenki t´ ancol, ´es a l´ anyok egym´assal, illetve a fi´ uk egym´assal nem t´ancolnak? Megold´ as. Egy t´ ancol´ o fel´ all´ ast vagy p´arba ´all´ıt´as u ´gy kaphatunk, hogy minden t´anc el˝ott a fi´ ukat sorba´ all´ıtjuk egy r¨ ogz´ıtett sorrend szerint, majd a l´anyokat valamilyen sorrendben a fi´ uk el˝ ott felsorakoztatjuk. Mivel a fi´ uk sorrendje r¨ogz´ıtett, ez´ert a l´anyok sorbarendez´ese meghat´ arozza egy´ertelm˝ uen a p´arba ´all´ıt´ast. Ezt pedig 5! = 120-f´elek´eppen tudjuk megtenni. 2. N´eh´ any goly´ ot 720-f´elek´eppen rakhatunk sorba. H´any goly´onk lehet, ha mindegyik k¨ ul¨onb¨oz˝ o sz´ın˝ u? Megold´ as. Tegy¨ uk fel, hogy n darab goly´onk van, ami mind k¨ ul¨onb¨oz˝o sz´ın˝ u. Ezt n! m´odon tudjuk sorbarakni. Ha kezdj¨ uk fel´ırni az n! ´ert´ekeit k¨ ul¨onb¨oz˝o n-ekre (1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720), akkor azt kapjuk, hogy n = 6. 3. Adott k´et halmaz, A = {1, 2, 3, 4, 5, 6}, B = {a, b, c, d, e, f }. H´any olyan f¨ uggv´eny van, amely az A halmaz elemeihez a B halmaz elemeit k¨olcs¨on¨osen egy´ertelm˝ uen rendeli hozz´a? Megold´ as. Egy f : {1, 2, 3, 4, 5, 6} → {a, b, c, d, e, f } f¨ uggv´enyt le´ırhatunk mint egy t´abl´azatot: ! 1 2 3 4 5 6 . f (1) f (2) f (3) f (4) f (5) f (6) Az f f¨ uggv´eny k¨ olcs¨ on¨ osen egy´ertelm˝ u, ha az f (1), . . . , f (6) k¨oz¨ott a B = {a, b, c, d, e, f } halmaz minden eleme pontosan egyszer szerepel. ´Igy minden k¨olcs¨on¨osen egy´ertelm˝ u hozz´arendel´est megkapunk, ha a fenti t´ abl´azat als´o sor´aba be´ırjuk a B elemeit valamilyen sorrendben. Ezt pedig 6! = 720-f´elek´eppen tehetj¨ uk meg. 4. H´ any sz´ am k´esz´ıthet˝ o az al´ abbi sz´amjegyekb˝ol? (Minden megadott sz´amjegyet fel kell haszn´alni.) a) 1, 1, 2, 2, 3, 4, b) 4, 4, 4, 4, 5, 5, 5. Megold´ as. a) Az (5)-¨ os k´eplet alapj´an (2+2+1+1)! = 2!6!2! = 180 hatsz´amjegy´ u sz´am alkothat´ o 2! 2! 1! 1 az 1, 1, 2, 2, 3, 4 sz´ amjegyek felhaszn´al´as´aval. 7! etsz´amjegy´ u sz´am alkothat´o n´egy 4-es ´es b) Az (5)-¨ os k´eplet alapj´ an (4+3)! 4! 3! = 4! 3! = 35 h´ h´ arom 5-¨ os felhaszn´ al´ as´ aval. 5. Egy dobozban 16 goly´ o van, k¨ oz¨ ul¨ uk 10 feh´er, 4 piros ´es 2 k´ek sz´ın˝ u. H´anyf´ele sorrendben h´ uzhatjuk ki egym´ as ut´ an a 16 goly´ot, ha az egysz´ın˝ ueket nem k¨ ul¨onb¨oztetj¨ uk meg?
´ 1. FELADATSOR MEGOLDASAI
3
Megold´ as. Az (5)-¨ os k´eplet alapj´ an (10+4+2)! ele sorrendben h´ uzhatjuk ki egym´as 10! 4! 2! = 120 120 f´ ut´ an a 10 feh´er, 4 piros ´es 2 k´ek goly´ ot. 6. Adott k´et halmaz, A = {1, 2, 3, 4, 5, 6}, B = {a, b, c}. H´any olyan A-t B-re k´epez˝o f¨ uggv´eny van, amely minden B-beli elemet pontosan k´etszer vesz fel ´ert´ek¨ ul? Megold´ as. Az f : {1, 2, 3, 4, 5, 6} → {a, b, c} f¨ uggv´eny megadhat´o az al´abbi t´abl´azattal: ! 1 2 3 4 5 6 . f (1) f (2) f (3) f (4) f (5) f (6) Azoknak az f -nek a sz´ am´ at akarjuk megkapni, melyek az a, b ´es c ´ert´ek mindegyik´et pontosan k´etszer veszi fel, m´ as sz´ oval azokat a fenti t´abl´azatokat, melyek als´o sor´aban pontosan k´et a, k´et b ´es k´et c van. Az als´ o sort alkot´ o sorozatok sz´ama a (5) alapj´an (2+2+2)! 2! 2! 2! = 90. Vari´ aci´ ok. 7. Egy rejtv´enyp´ aly´ azaton 5 k¨ ul¨ onb¨ oz˝ o d´ıjat sorsolnak ki a helyes megfejt´est bek¨ uld˝ok k¨oz¨ott. 78 j´ o megfejt´es ´erkezik be. H´ anyf´ele eredm´enyt hozhat a sorsol´as? Megold´ as. R¨ ogz´ıts¨ uk, hogy az 5 d´ıj k¨ oz¨ ul, melyiket adjuk az els˝o-, m´asodik-, harmadik-, negyedik-, illetve ¨ ot¨ odikk´ent kih´ uzott helyes bek¨ uld˝onek. ´Igy a 78 bek¨ uld˝ob˝ol k´epezett 5 hossz´ us´ ag´ u sorozatok megadj´ ak a sorsol´ as eredm´eny´et. Ezen sorozatok sz´ama az (1)-es k´eplet 78! alapj´ an (78−5)! = 78! 73! = 78 · 77 · 76 · 75 · 74 = 2 533 330 800. 8. Adott k´et halmaz, A = {1, 2, 3}, B = {a, b, c, d, e, f }. H´any olyan f¨ uggv´eny van, amely az A halmaz elemeihez a B halmaz elemeib˝ ol k¨olcs¨on¨osen egy´ertelm˝ uen rendel hozz´a h´armat? Megold´ as. Egy f : {1, 2, 3} → {a, b, c, d, e, f } f¨ uggv´eny le´ırhat´o mint az ! 1 2 3 . f (1) f (2) f (3) t´ abl´ azat, ahol f (1), f (2), f (3) ∈ B = {a, b, c, d, e, f }. K¨olcs¨on¨osen egy´ertelm˝ u f f¨ uggv´enyek ´ eset´en a t´ abl´ azat als´ o sor´ aban a B halmaz 3 k¨ ul¨onb¨oz˝o eleme szerepel. Igy a k¨olcs¨on¨osen egy´ertelm˝ u f¨ uggv´enyek sz´ ama megegyezik a B halmaz elemeib˝ol alkotott 3 hossz´ us´ag´ u soroza6! 6! tok sz´ am´ aval. Az (1)-es k´eplet alapj´ an ez egyenl˝o (6−3)! = 3! = 4 · 5 · 6 = 120-szal. 9. H´ anyf´ele kit¨ olt¨ ott tot´ oszelv´eny van? (13 + 1 m´erk˝oz´es v´egeredm´eny´ere tippelhet¨ unk, mindegyik tipp lehet 1, 2 vagy X.) Megold´ as. Egy tot´ oszelv´eny kit¨ olt´es´en´el az 1, 2, X felhaszn´al´as´aval 14 hossz´ us´ag´ u sorozatokat k´epez¨ unk, melyben az 1, 2, X t¨ obbsz¨ or is el˝ofordulhatnak. A (2)-es k´eplet alapj´an ezen sorozatok sz´ ama 314 = 4 782 969. 10. Adott k´et halmaz, A = {1, 2, 3, 4, 5, 6}, B = {a, b, c, d, e, f }. H´any olyan f¨ uggv´eny van, amely az A halmaz elemeihez a B halmaz elemeit rendeli?
´ 1. FELADATSOR MEGOLDASAI
4
Megold´ as. Egy f : {1, 2, 3, 4, 5, 6} → {a, b, c, d, e, f } f¨ uggv´enyt megadhatunk egy ! 1 2 3 4 5 6 f (1) f (2) f (3) f (4) f (5) f (6) t´ abl´ azattal, ahol f (1), f (2), f (3), f (4), f (5), f (6) ∈ B. Mivel nincs semmilyen kik¨ot´es az f f¨ uggv´enyre, ez´ert a t´ abl´ azat als´o sor´aban a B elemei t¨obbsz¨or is megism´etl˝odhetnek. ´Igy az f f¨ uggv´enyt megadja a t´ abl´ azat als´o sor´aba be´ırt 6 hossz´ us´ag´ u sorozat, melyet a B elemeib˝ ol |A| 6 k´epez¨ unk ´es mely tartalmazhat ism´etl˝od´est. Ezen sorozatok sz´ama |B| = 6 = 46 656, ahol |A| ´es |B| a halmazok elemeinek sz´am´at jel¨oli. Kombin´ aci´ ok. 11. Egy 6 tag´ u t´ arsas´ agban mindenki mindenkivel kezet fog. H´any k´ezfog´as ez ¨osszesen? Megold´ as. Egy k´ezfog´ ashoz a 6 tag´ u t´arsas´agb´ol egy k´et emberb˝ol ´all´o csoportot v´alasztunk ki. Az ilyen csoportok sz´ ama a (2)-es k´eplet alapj´an 62 = 6·5 1·2 = 15. 12. 12 szem´ely egyszerre ´erkezik egy 6 szem´elyes lifthez. H´anyf´elek´eppen v´alaszthatjuk ki k¨oz¨ ul¨ uk az els˝ o menet 6 utas´ at? Megold´ as. Az els˝ o menethez a 12 szem´elyb˝ol kiv´alasztunk egy 6 szem´elyb˝ol ´all´o csoportot, 12 ezt pedig 6 = 924-f´elek´eppen tehetj¨ uk meg. 13. 500 term´ek k¨ oz¨ ott 4% selejtes. H´anyf´elek´eppen lehet 10 term´eket kiv´alasztani u ´gy, hogy a) egy selejtes se legyen; b) mind a 10 selejtes legyen; c) pontosan 5 selejtes legyen; d) legfeljebb 3 selejtes legyen; e) legyen k¨ ozt¨ uk selejtes? (Visszatev´es n´elk¨ ul v´ alasztunk, ´es a sorrendet nem vessz¨ uk figyelembe.) Megold´ as. Az 500 term´ek 4%-a 20, teh´at 480 j´o ´es 20 selejtes term´ek van. a) Tulajdonk´eppen 10 j´ o term´eket kell kiv´alasztani a 480 j´o k¨oz¨ ul, ezt pedig 480 elek´eppen 10 f´ tehetj¨ uk meg. b) Ebben az esetben 10 term´eket kell kiv´alasztani a 20 selejtes k¨oz¨ ul, ´es ezt 20 elek´eppen 10 -f´ lehet megtenni. c) Ebben az esetben pontosan 5 selejtes ´es 5 j´o term´ek van a 10 kiv´alasztott k¨oz¨ott. Ezt 20 480 · 5 -f´elek´eppen lehet kiv´alasztani, mivel a 480 j´o k¨oz¨ ul 5-¨ot 480 , illetve 20 selejtes 5 5 20 k¨ oz¨ ul 5-¨ ot 5 -f´elek´eppen lehet kiv´alasztani. 480 d) 10 term´eket, amely k¨ oz¨ ott pontosan k ∈ {0, 1, 2, . . . , 9, 10} selejtes van 20 k · 10−k f´elek´eppen lehet kiv´ alasztani. Ha legfeljebb 3 selejtes term´ek lehet a 10 kiv´alasztott k¨oz¨ott, akkor lehet olyan v´ alaszt´ as, amikor 0, 1, 2, illetve 3 selejtes term´ek van a 10 k¨oz¨ott. ´Igy 10 term´eket 20 480 20 480 20 480 20 480 · + · + · + · 0 10 1 9 2 8 3 7 f´elek´eppen lehet kiv´ alasztani u ´gy, hogy legfeljebb csak 3 selejtes lehet k¨ozte.
´ 1. FELADATSOR MEGOLDASAI
5
e) K´etf´elek´eppen is megk¨ ozel´ıthetj¨ uk a probl´em´at. Ha a 10 kiv´alasztott k¨oz¨ott van selejtes, akkor van olyan v´ alaszt´ as, amikor pontosan 1, 2, . . . , 9, 10 selejtes term´ek van a kiv´ alasztottak k¨ oz¨ ott. Az el˝ oz˝ o ponthoz hasonl´oan ezt 20 480 20 480 20 480 20 480 · + · + ... + · + · 1 9 2 8 9 1 10 0 f´elek´eppen v´ alaszthatjuk ki. Ugyanezt j´ oval egyszer˝ ubben is kisz´ amolhatjuk, ha u ´gy n´ezz¨ uk, hogy 10 kiv´alasztott term´ek k¨ oz¨ ul nem lehet mind a 10 j´ o. Teh´ at az ¨osszes kiv´alaszt´asi lehet˝os´eg k¨oz¨ ul (500 term´ekb˝ol v´ alasztunk 10-et) kiz´ arjuk azokat, amikor 10 j´ot v´alasztunk (480 j´ob´ol kiv´alasztunk 10-et); 480 ezt 500 elek´eppen tehetj¨ uk meg. 10 − 10 f´ 14. H´ anyf´elek´eppen helyezhet¨ unk el 5 levelet 16 lev´elszekr´enybe, ha a levelek k¨oz¨ott nem tesz¨ unk k¨ ul¨ onbs´eget, ´es egy rekeszbe a) legfeljebb egy levelet, b) t¨ obb levelet is tehet¨ unk? Megold´ as. a) Ha egy lev´elszekr´enybe legfeljebb egy levelet tesz¨ unk, akkor a 16 lev´elszekr´eny k¨ oz¨ ul tulajdonk´eppen kiv´ alasztunk 5-¨ot, amelyekbe egy-egy levelet tesz¨ unk. Ezt 16 5 f´elek´eppen tehetj¨ uk meg. b) Minden lev´el bedob´ as´ an´ al fel´ırjuk a lev´elszekr´eny sz´am´at, ahova a lev´el ker¨ ult. ´Igy 5 lev´el bedob´ asa ut´ an 5 sz´ amot ´ırtunk fel: • a sz´ amok 1 ´es 16 k¨ oz¨ ott vannak, • egy sz´ am t¨ obbsz¨ or is szerepelhet (mivel egy lev´elszekr´enybe t¨obb levelet is dobhatunk) • a sz´ amok sorrendje nem sz´ am´ıt (mivel a levelek k¨ozt nem tesz¨ unk k¨ ul¨onbs´eget). 16+5−1 20 A (4)-es k´eplet alapj´ an = 5 = 15 504-f´elek´eppen dobhatjuk be a leveleket. 5 ´ zi feladatok Ha 15. Oldjuk meg az 13. feladatot u ´gy, hogy a kiv´alasztott term´eket minden h´ uz´as ut´an visszatessz¨ uk. Megold´ as. Visszatev´eses h´ uz´ as eset´en u ´gy lehet tekinteni, hogy van 480 fajta j´o term´ek ´es 20 fajta selejtes, ´es mindegyikb˝ ol korl´ atlan mennyis´eg ´all rendelkez´esre. a) 480 fajta j´ o term´ekb˝ ol v´ alasztunk 10-et, egy fajt´ab´ol ak´ar t¨obbet is a visszatev´es miatt. 489 Ezt 480+10−1 = -f´ e lek´eppen tehetj¨ uk meg a (4)-es k´eplet alapj´an. 10 10 b) 20 fajta selejtes term´ekb˝ ol v´ alasztunk 10-et, egy fajt´ab´ol t¨obbet is a visszatev´es miatt; ezt 20+10−1 29 = = 20 030 010-f´ elek´eppen tehetj¨ uk meg. 10 10 c) 480 fajta j´ o term´ekb˝ ol v´ alasztunk 5-¨ot, illetve 20 selejtes fajt´ab´ol szint´en 5-¨ot (minden 20+5−1 24 fajt´ ab´ ol t¨ obbet is v´ alaszthatunk a visszatev´es miatt). ´Igy 480+5−1 · = 484 5 5 5 · 5 f´elek´eppen v´ alaszthatjuk ki ˝ oket.
´ 1. FELADATSOR MEGOLDASAI
6
d) Ha legfeljebb 3 selejtest v´ alaszthatunk ki, akkor lehet olyan v´alaszt´as, amikor 0, 1, 2 vagy 3 selejtes term´eket v´ alasztunk ki. Visszatev´essel ezt
20 + 0 − 1 480 + 10 − 1 20 + 1 − 1 480 + 9 − 1 · + · 0 10 1 9 20 + 2 − 1 480 + 8 − 1 20 + 3 − 1 480 + 7 − 1 + · + · 2 8 3 7 19 489 20 488 21 487 22 486 = · + · + · + · 0 10 1 9 2 8 3 7
f´ele m´ odon v´ alaszthatjuk ki. e) Ebben az esetben nem v´ alaszthatunk a 480 fajta j´o term´ek k¨oz¨ ul, ez´ert az ¨osszes v´alaszt´ asi lehet˝ os´egb˝ ol levonjuk azokat a v´alaszt´asokat, amikor csak j´o fajta term´eket v´alasztunk: 500 + 10 − 1 480 + 10 − 1 509 489 − = − . 10 10 10 10 16. H´ anyf´elek´eppen t¨ olthet¨ unk ki egy tot´oszelv´enyt – ha 13 + 1 m´erk˝oz´esre tippel¨ unk – u ´gy, hogy 8 darab 1-es, 2 darab X ´es 4 darab 2-es tipp legyen rajta? Megold´ as. Az (5)-¨ os k´eplet alapj´an 8!14! elek´eppen t¨olthetj¨ uk ki a tot´oszelv´enyt, 2! 4! = 45 045-f´ ha nyolcszor 1-sel, k´etszer X-szel, illetve n´egy alkalommal 2-essel tippel¨ unk. 17. H´ anyf´elek´eppen j´ arhat 5 h´ azasp´ar k¨ort´ancot, ha mindenki a h´azast´arsa kez´et fogja? Megold´ as. El˝ osz¨ or azt n´ezz¨ uk meg, hogy 5 p´art h´anyf´elek´eppen lehet k¨orbe ´all´ıtani, ha minden p´ art egy egys´egk´ent tekint¨ unk. Kiv´alasztunk egy p´art, amihez k´epest viszony´ıtjuk a t¨obbi p´ ar ´ helyzet´et az ´ oramutat´ o j´ ar´ as´ anak megfelel˝o ir´anyba haladva. Igy tulajdonk´eppen 4 p´art kell sorba rendezni; ezt 4! = 24-f´elek´eppen lehet megtenni. Minden p´arban k´etf´ele sorrend lehet: a f´erfi balj´ an van a n˝ o vagy a jobbj´an; ez tov´abbi 25 v´alaszt´asi lehet˝os´eget jelent. Azt kapjuk, hogy ¨ osszesen 4! · 25 = 768-f´ele k¨ort´anc fel´all´as lehets´eges, ha mindenki fogja a h´azast´arsa kez´et. 18. Tizenk´et di´ ak h´ arom cs´ onakot b´erel. Az egyik cs´onak 3 u ¨l´eses, a m´asik 4, a harmadik pedig 5u ¨l´eses. a) H´ anyf´elek´eppen foglalhatnak helyet a cs´onakokban? b) H´ anyf´elek´eppen foglalhatnak helyet, ha k´et di´ak felt´etlen¨ ul egy cs´onakba akar ker¨ ulni? Megold´ as. a) A 12 di´ akot felosztjuk h´arom csoportra a cs´onakok kapacit´asa szerint. Az els˝ o 12−3 cs´ onakba u ¨l˝ oket 12 -f´ e lek´ e ppen v´ a laszthatjuk ki, a m´ a sodik cs´ o nakba ker¨ u l˝ o ket = 3 4 9 -f´ e lek´ e ppen, m´ ıg a harmadik cs´ o nakba a megmaradt 5 di´ a k u ¨ l (ez 1-f´ e lek´ e ppen v´ a laszthat´ o 4 9 12! 9! 12! ki). ´Igy a di´ akok 12 · = · = = 27 720-f´ e lek´ e ppen foglalhatnak helyet a 3 4 3! 9! 4!·5! 3! 4! 5! h´ arom cs´ onakban. b) El˝ osz¨ or azt a k´et di´ akot u ¨ltetj¨ uk be, akik egy cs´onakba akarnak ker¨ ulni. H´arom esetet k¨ ul¨ onb¨ oztet¨ unk meg.
´ 1. FELADATSOR MEGOLDASAI
7
˝ ketten az els˝ • Ok o cs´ onakba ker¨ ulnek. A fennmaradt 10 di´akot 3 − 2 = 1-es, 4-es ´es 9 5-¨ os csoportokra osztjuk a cs´ onakokban maradt helyek sz´ama szerint; ezt 10 1 · 4 = 10! ele m´ odon tehetj¨ uk meg. 1! 4! 5! = 1 260-f´ ˝ • Ok ketten a m´ asodik cs´ onakba u ¨lnek. A t¨obbieket 3-as, 2-es ´es 5-es csoportokba 7 10! osztjuk a megmaradt helyek szerint: 10 elek´eppen oszthatjuk 3 · 2 = 3!·2!·5! = 2 520-f´ fel. ˝ ketten a harmadik cs´ • Ok onakba u ¨lnek be. A t¨obbieket 3-as, 4-es ´es 3-as csoportokba 7 10! osztjuk a fennmaradt helyek alapj´an: 10 as van. 3 · 4 = 3! 4! 3! = 4 200 ilyen feloszt´ ¨ Osszegezve, az adott felt´etel mellett a 12 di´akot a 3 cs´onakba 10! 10! 10! + + = 7 980 1! 4! 5! 3! 2! 5! 3! 4! 3! f´ele m´ odon u ¨ltethetj¨ uk be. 19. Egy kock´ aval h´ aromszor dobunk egym´ as ut´an. H´any olyan dob´assorozat fordulhat el˝o, amelyben a 6-os dob´ as is szerepel? Megold´ as. Kivonjuk az ¨ osszes dob´ assorozat sz´am´ab´ol (63 ), azon dob´assorozatok sz´am´at, amikor 3 nem szerepel 6-os dob´ as (5 ). ´Igy azt kapjuk, hogy 63 −53 = 91 olyan dob´assorozat van, amikor szerepel 6-os dob´ as. 20. H´ any olyan 6 jegy˝ u sz´ am van, a) amelynek minden jegye k¨ ul¨ onb¨ oz˝ o; b) amelynek b´ armely k´et szomsz´edos jegye k¨ ul¨onb¨oz˝o; c) amelyben pontosan 2 darab 0 van; d) amelyben van jegyism´etl˝ od´es; e) amelyben a jegyek szorzata 10-zel osztva 5 marad´ekot ad; f) amelyben a jegyek ¨ osszege 10-zel osztva 5 marad´ekot ad; g) amelyben a jegyek ¨ osszege p´ aros? Megold´ as. Feltessz¨ uk, hogy a hatjegy˝ u sz´am kezd˝odhet 0-val. a) Ebben az esetben a {0, 1, . . . , 8, 9} halmazb´ol k´epez¨ unk 6 elem˝ u sorozatokat, melyek nem 10! tartalmaznak ism´etl˝ od´est; 4! = 151 200 ilyen sorozat van az (1)-es k´eplet alapj´an. b) Az A = a1 a2 a3 a4 a5 a6 hatjegy˝ u sz´ amsorozatnak megfeleltetj¨ uk az X = x1 x2 x3 x4 x5 x6 szint´en hatjegy˝ u sz´ amsorozatot (a1 , . . . , a6 , x1 , . . . , x6 ∈ {0, 1, . . . , 8, 9}) a k¨ovetkez˝ok´eppen x1 = a1 ,
x3 ≡ a3 − a2 (mod 10),
x5 ≡ a5 − a4 (mod 10),
x2 ≡ a2 − a1 (mod 10),
x4 ≡ a4 − a3 (mod 10),
x6 ≡ a6 − a5 (mod 10).
Az X sz´ amsorozatb´ ol visszakaphat´ o az A a k¨ovetkez˝ok´eppen: a1 = x1 ,
a4 ≡ x1 + x2 + x3 + x4 (mod 10),
a2 ≡ x1 + x2 (mod 10),
a5 ≡ x1 + x2 + x3 + x4 + x5 (mod 10),
a3 ≡ x1 + x2 + x3 (mod 10),
a6 ≡ x1 + x2 + x3 + x4 + x5 + x6 (mod 10).
´ 1. FELADATSOR MEGOLDASAI
8
c)
d)
e)
f)
g)
P´eld´ aul, ha A = 274334, akkor X = 257901. Az A sorozatban pontosan akkor k¨ ul¨onb¨oz˝ ok a szomsz´edos sz´ amjegyek, amikor az X sorozatban az x2 , . . . , x6 k¨oz¨ ul egyik sem 0. Az ilyen X sz´ amsorozatok sz´ ama 10 · 95 = 590 490. Ha kiv´ alaszottuk a k´et darab 0 hely´et a hatjegy˝ u sz´amsorban ( 62 -f´elek´eppen tehetj¨ uk 4 6 4 meg), akkor a t¨ obbi 4 helyre tetsz˝olegesen 1, 2, . . . , 9 ´ırhat´o (9 lehet˝os´eg). Teh´at 4 · 9 = 98 415 olyan hatjegy˝ u sz´ amsorozat van, amelyben pontosan k´et darab 0 szerepel. Az ¨ osszes lehets´eges hatjegy˝ u sz´amsorozat sz´am´ab´ol (106 ) kivonjuk azoknak a sz´am´at, amelyek nem tartalmaznak jegyism´etl˝od´est, azaz amelyek minden sz´amjegye k¨ ul¨onb¨oz˝o ( 10! 4! = 151 200 az a) pont alapj´ an), teh´at 1 000 000 − 151 200 = 848 800 hatjegy˝ u sz´amsorozat van, amelyik tartalmaz jegyism´etl˝od´est. Ebben az esetben a sz´ amjegyek k¨oz¨ott van 5-¨os, de nincs 0-´as. Ezen hatjegy˝ u sz´amsorozatok sz´ ama egyenl˝ o az ¨ osszes hatjegy˝ u sz´amsorozat sz´ama, mely nem tartalmaz 0-´ast (96 ) m´ınusz azon hatjegy˝ u sz´ amsorozatok sz´ama, mely nem tartalmaz 0-´ast ´es 5-¨ost (86 ), ami v´eg¨ ul 6 6 egyenl˝ o 9 − 8 = 268 297. Legyen A = a1 a2 a3 a4 a5 a6 egy sz´amsorozat u ´gy, hogy a1 + . . . + a6 ≡ 5 (mod 10), amib˝ ol ad´ odik, hogy a6 ≡ 5 − (a1 + . . . + a5 ) (mod 10). Teh´at az els˝o ¨ot sz´amjegy meghat´arozza a hatodikat ebben az esetben. ´Igy az ilyen A sz´amsorozatok sz´ama ugyanannyi, mint az otjegy˝ ¨ u sz´ amsorozatok sz´ ama, 105 . Jel¨ olje S = {0, 1, . . . , 9} ´es legyen A = a1 a2 a3 a4 a5 a6 egy hatjegy˝ u sz´amsorozat, melyre a1 + . . . + a6 ≡ 0 (mod 2). ´Igy, ha a1 + . . . + a5 p´aros, akkor a6 is p´aros, azaz a6 ∈ {0, 2, 4, 6, 8}. Ha a1 + . . . + a5 p´aratlan, akkor a6 is p´aratlan, azaz a6 ∈ {1, 3, 5, 7, 9}. Mindk´et esetben r¨ ogz´ıtett a1 , . . . , a5 sz´amjegyek eset´en az a6 -ot 5-f´elek´eppen v´alaszthat´ o meg. Teh´ at a keresett A-k sz´ama egyenl˝o
|{a1 , . . . , a5 ∈ S | a1 + . . . + a5 p´aros}| · 5 + |{a1 , . . . , a5 ∈ S | a1 + . . . + a5 p´aratlan}| · 5 = |{a1 , . . . , a5 ∈ S}| · 5 = 5 · 105 . 21. Az 1, 2, . . . , 9 sz´ amokat sorba rendezz¨ uk. H´any esetben fordulhat el˝o, hogy az 1, 2, 3 sz´amok a) valamilyen sorrendben egym´as mell´e ker¨ ulnek; b) n¨ ovekv˝ o sorrendben ker¨ ulnek egym´as mell´e; c) egym´ ashoz k´epest (nem sz¨ uks´egk´eppen egym´as mellett) n¨ovekv˝o sorrendben helyezkednek el? Megold´ as. a) El˝ osz¨ or sorba rendezz¨ uk a 4, 5, . . . , 9 sz´amokat (6! = 720-f´elek´eppen lehet), sorba rendezz¨ uk az 1, 2, 3 sz´amokat (3! = 6-f´elek´eppen lehet), majd az ut´obbi sorozatot egyben besz´ urjuk az els˝ o sorozatba valahova (7 helyre sz´ urhatjuk be). Teh´at ¨osszesen 6! · 3! · 7 = 30 240 olyan sor van, ahol az 1, 2, 3 egym´as mellett van valamilyen sorrendben. b) Sorba rendezz¨ uk a 4, 5, . . . , 9 sz´amokat (6! = 720-f´elek´eppen lehet), majd besz´ urjuk ebbe a sorba az 123 sorozatot egyben (´es ugyanebben a sorrenben). Ez ut´obbi sorozatot 7 helyre sz´ urhatjuk be. ´Igy 6! · 7 = 5 040 olyan sorba rendez´ese van az 1, 2, . . . , 9 sz´amoknak, ahol az 1, 2, 3 egym´ as ut´ an k¨ ovetkezik.
´ 1. FELADATSOR MEGOLDASAI
9
c) Kiv´ alasztjuk azt a h´ arom helyet a kilencb˝ol, ahova az 1, 2, 3 ker¨ ul. Mivel az 1, 2, 3 egym´ashoz 9 viszony´ıtott helyzete r¨ ogz´ıtett, ez´ert 3 = 84-f´elek´eppen v´alaszthat´o ki a h´arom hely. A marad´ek hat helyre 6! = 720-f´elek´eppen helyezhetj¨ uk el a 4, 5, . . . , 9 sz´amokat. Azt kaptuk, 9 hogy 3 · 6! = 60 480-f´elek´eppen rendezhetj¨ uk sorba a megadott felt´etellel a sz´amokat. 22. Egy 28 tag´ u sakkszakoszt´ alyban 4 jutalmat osztanak ki. H´anyf´elek´eppen t¨ort´enhet ez, ha a) a jutalmak egyenl˝ ok. ´es egy tag legfeljebb egy jutalmat kaphat; b) a jutalmak egyenl˝ ok, ´es egy tag t¨ obb jutalmat is kaphat; c) a jutalmak k¨ ul¨ onb¨ oz˝ ok, ´es egy tag legfeljebb egy jutalmat kaphat; d) a jutalmak k¨ ul¨ onb¨ oz˝ ok, ´es egy tag t¨ obb jutalmat is kaphat? Megold´ as. a) Ki kell v´ alasztani azt a 4 tagot a 28 k¨oz¨ ul (a sorrend nem sz´am´ıt, mivel a jutal 28 ˝ mak egyform´ ak), aki egy-egy jutalmat kap. Oket elek´eppen v´alaszthatjuk 4 = 20 475-f´ ki. b) Ebben az esetben visszatev´essel h´ uzunk ki 4-et a 28-b´ol. A sorrend most sem sz´am´ıt, mivel 28+4−1 a jutalmak egyform´ ak. Ekkor = 31 ele sorsol´asi eredm´eny van a (4)-es 4 4 = 31 465-f´ k´eplet alapj´ an. c) 4 tagot sorban h´ uzunk ki a 28-b´ ol (a sorrend sz´am´ıt, mert a jutalmak k¨ ul¨onb¨oz˝ok). Az 28! (1)-es k´eplet alapj´ an 24! = 491 400-f´elek´eppen h´ uzhatjuk ki (nem visszatev´eses sorsol´as, mivel egy tag legfeljebb egy jutalmat kaphat). d) Visszatev´essel sorsolunk, mert egy tag t¨obb jutalmat is kaphat, ´es a kih´ uz´as sorrendje is sz´ am´ıt, mivel a jutalmak k¨ ul¨ onb¨ oz˝ ok. A (2)-es k´eplet alapj´an 284 = 614 656-f´ele sorsol´as lehets´eges.
