Kombinatorika - feladatok és megoldásaik

  1. Hány különböző rendszám adható ki, amely három betűből és azt követő három számból áll (az angol ábécé 25 betűt tartalmaz)?

    Megoldás:

    Az egyes betűhelyeken egymástól függetlenül 26-féle betű, míg a számhelyeken szintén egymástól és a betűktől is függetlenül 10-féle szám állhat. A megfelelő rendszámok száma ezért $26^3*10^3$.

    1. Hányféleképpen állítható sorba $n$ (különböző) gyerek?
    2. Hányféleképpen ültethető kör alakú asztal köré $n$ lovag?
    3. Hányféleképpen fűzhető fel $n$ különböző színű gyöngy egy láncra?
    4. Válaszoljuk meg az előző kérdéseket akkor is, ha Jancsi és Juliska, Sir Lancelot és King Arthur, illetve a kék és a fehér gyöngy egymás mellé kell hogy kerüljenek.

    Megoldás:

    1. Az első helyre $n$, a másodikra $(n-1)$, általában az $i$-edik helyre $(n+1-i)$-féleképpen válaszhatunk embert ( $1 \leqslant i \leqslant n$), az összes lehetőség száma ezek szorzata, azaz $n!$ (ez valójában az ismétlés nélküli permutáció mintapéldája).
    2. Először állítsuk sorba a lovagokat (az előző példa alapján ezt $n!$-féleképpen tudjuk megtenni), majd ültessük le őket a kerekasztalhoz. Az ültetés után nem tudjuk megmondani, hol volt a sor vége, sőt: ha az ültetés alapján akarjuk sorbaállítani a lovagokat, akkor pontosan $n$-féleképpen jelölhetjük ki -- immár önkéntesen -- a sor kezdetét és végét. A lehetőségek száma ezért az előző feladat eredményének $n$-edrésze, azaz $(n-1)!$.
    3. Míg a lovagok kerekasztalának kétirányú körüljárását megkülönböztettük, a lánc esetében azonosnak tekintünk két elrendezést, ha azok egymás tükörképei. Ezért a megoldások száma az előző esetnek a fele, azaz $(n-1)!/2$.
    4. A közös alapötlet, hogy az egymás mellé teendő párokat egyként kezeljük. Az első két esetben a párok egymás közötti sorrendje számít, a megoldás így az $(n-1)$-es eset kétszerese, azaz rendre $2(n-1)!$ illetve $2(n-2)!$. A harmadik esetben a tükrözést már eleve külön esetként kezeltük, így a párok egymás közötti sorrendje már nem számít. Ezért a harmadik esetre adandó válasz $(n-1)!$.

  3. Hány olyan hatjegyű szám létezik, amelyben van két azonos számjegy? És hány ilyen 15-jegyű szám létezik?

    Megoldás:

    Az összes hatjegyű számok száma nyilván $10^6-10^5$, elegendő a ,,rossz'', azaz csupa különböző számjegyből álló számokat megszámolni. Egy ilyen szám első számjegye 9-féle lehet (a $0$ nem megengedett), a második számjegy szintén 9-féle (ez már lehet $0$, de nem lehet azonos az első számjeggyel), a harmadik számjegy 8-féle, stb. A jó számok száma mindezek alapján $10^6-10^5-9*9*8*7*6*5=763920$.

    A 15-jegyű számoknak a skatulyaelv alapján mindig van két azonos számjegye. Ezek száma $10^{15}-10^{14}$.

  4. Hányféleképpen olvasható ki az alábbi ábrából a ``BSz Fan Club''?
    B S Z F A N
    S Z F A N C
    Z F A N C L
    F A N C L U
    A N C L U B

    Megoldás:

    Az olvasás során ötször lépünk jobbra és négyszer lefelé. Az összesen kilenc lépésből tetszőlegesen kiválaszthatjuk a négy lelépést, ehhez pontosan egy jó olvasás fog tartozni és viszont. A lehetőségek száma ezért $9 \choose 4$.

  5. Hányféleképpen lehet eljutni az origóból a (2,3,5) pontba, úgy, hogy csak egységnyi hosszú jobbra, fel és előre lépések lehetségesek?

    Megoldás:

    Az előző feladatban látotthoz teljesen hasonló gondolatmenettel az eredmény ${10 \choose 2}{8 \choose 3}{5 \choose 5}$.

  6. Legfeljebb hány pontban metszik egymást egy konvex 9-szög átlói?

    Megoldás:

    A 9-szög tetszőlegesen választott négy csúcsa konvex négyszöget alkot. A négyszög átlói a 9-szögnek is átlói. A 9-szög tetszőleges két átlójának metszéspontja előáll, mint egy alkalmasan választott ilyetén konvex négyszög két átlójának metszéspontja. Az ilyen négyszögek száma $n \choose 4$, legfeljebb ennyi lehet tehát a 9-szög átló-metszéspontjainak a száma (ez el is érhető, ha semelyik három átló nem metszi egymást egy pontban).

  7. Hányféleképpen tölthető ki egy lottószelvény? Hány 5, 4 és 3 találatos kitöltés van?

    Megoldás:

    Egy adott kitöltés során 5 számot választunk a 90-ből, a kitöltések száma ezért $90 \choose 5$.

    Adott sorsolás mellett az öttalálatos kitöltések száma nyilván 1.

    Négy találat eléréséhez először ki kell választanunk az eltalálni kívánt négy számot ($5 \choose 4$ lehetőség), majd ötödiknek egy rossz számot kell választani a 85 rossz számból ($85 \choose 1$ lehetőség). A négytalálatos kitöltések száma ezért ${5 \choose 4}{85 \choose 1}$.

    Három találat eléréséhez először ki kell választanunk az eltalálni kívánt három számot ($5 \choose 3$ lehetőség), majd negyediknek és ötödiknek egy-egy rossz számot kell választani a 85 rossz számból ($85 \choose 2$ lehetőség). A háromtalálatos kitöltések száma ezért ${5 \choose 3}{85 \choose 2}$.

  8. A polcon egymás mellett 12 könyv van. Hányféleképpen lehet kiválasztani 4-et úgy, hogy ne legyen közöttük két egymás melletti?

    Megoldás:

    Számozzuk meg a könyveket 1-től 12-ig, majd a polc mindkét szélére tegyünk egy-egy vázát.

    A négy könyv levétele után nézzük meg, hogy az egyes könyvek között 0 vagy 1 könyvnyi hely van. A két szélen pedig a két vázát viszonyítsuk a könyvekhez. Ezeket a foghíjakat balról jobbra haladva egy 9 hosszú 0-1 sorozattal tudjuk leírni.

    Vegyük észre, hogy ha a négy könyvet a feladat szövegének megfelelően vettük le a polcról, akkor a 9 hosszú 0-1 sorozat pontosan 4 darab 1-est fog tartalmazni (a levett négy könyv helyén tátongó űrt szimbolizálva).

    Igaz továbbá, hogy tetszőleges 9 hosszú, 4 darab egyest tartalmazó 0-1 sorozathoz hozzárendelhető a maradék 8 darab könyv megfelelő elrendezése, így a könyvleszedéseket kölcsönösen egyértelműen megfeleltettük a 9 hosszú, 4 darab egyest tartalmazó 0-1 sorozatoknak.

    Utóbbiak száma nyilván $9 \choose 4$, ez a feladat kérdésére adott válasszal is megegyezik.

  9. Egy részeg postás figyelmetlenül oszt szét öt levelet azok címzettjeinek. Hányféleképpen teheti ezt meg úgy, hogy senki se a sajátját kapja meg? És úgy, hogy pontosan 1, 2, 3, 4 ill. 5 címzett kapja meg a saját levelét?

    Megoldás:

    Nyilvánvaló, hogy mind az öt levelet csak egyféleképpen lehet helyesen kézbesíteni, pontosan négy levelet pedig egyáltalán nem lehet helyesen kézbesíteni (hiszen ekkor az ötödik sem tévedhet el).

    Ha pontosan három levél ér célba, akkor a postás tévedésből két levelet megcserélt. E két levél szabadon választható az ötből ( ${5 \choose 2}=10$ lehetőség), így ezen esetek száma 10.

    Ha pontosan két levél ér célba, akkor a postás tévedésből három levelet ciklikusan elcserélt (másképp nem lehet pontosan hármat tévedni). E három levél szabadon választható az ötből ( ${5 \choose 3}=10$ lehetőség), ezenkívül a ciklikus permutáció irányát is kétféleképpen választhatjuk meg. A lehetőségek száma ezért ebben az esetben 20.

    Ha pontosan egy levél ér célba, akkor a postás kétféleképpen tévedhetett: vagy ciklikusan elcserélt 4 levelet, vagy pedig összecserélt két párt is. Négy adott levél $\frac{4!}{4}=6$-féleképpen permutálható ciklikusan (lásd a kerekasztal lovagjainak ültetéseit). Két pár összecserélése pedig 3-féleképp történhet (egy ilyen konfigurációt egyértelműen meghatároz, hogy az 1-es számú levelet a másik három melyikével cseréltük össze). Ezért négy adott levélre a tévedési lehetőségek száma 9, a négy adott levelet pedig ${5 \choose 4}=5$-féleképpen választhatjuk ki. A pontosan egy találat ezek szerint 45-féleképpen jöhet létre.

    Ha pontosan 0 levél ér célba, akkor a postás ismét csak kétféleképpen tévedhetett: vagy ciklikusan cserélte el az öt levelet ( $\frac{5!}{5}=24$ lehetőség), vagy pedig egy párt összecserélt, a másik hármat pedig ciklikusan permutált. Utóbbi eset lehetőségeinek számához először válasszuk ki a párként elcserélt 2 levelet ( ${5 \choose 2}=10$ lehetőség), a maradék hármat pedig vagy erre permutáljuk ciklikusan, vagy arra (2 eset). Az utóbbi eset ezért 20-féleképpen fordulhat elő, azaz összesen 44-féle módon lehetséges az, hogy a postás egyetlen levelet sem helyesen kézbesít.

    Érdemes elvégezni a következő egyszerű (ámbátor redundáns) ellenőrzést: a taglalt esetek uniója nem más, mint a levelek összes permutációinak halmaza, a lehetőségek számának összege tehát 120-at kell adjon eredményül (ez teljesül).

    A feladat egy, a fentiekől gyökeresen különböző módon is megoldható. Igaz, hogy a másik megoldás sokkal bonyolultabb, de legalább általánosítható n darab levélre is. Megnézem.

  10. Hány olyan 10 hosszú dobássorozat van (hagyományos dobókockával), melyben a dobott számok összege osztható 3-mal?

    Megoldás:

    Megadunk egy leképezést, amely tetszőleges 3-mal osztható összegű dobáshoz két másikat rendel: egy olyat, amely 3-mal osztva 1 maradékot ad és egy másikat, amely 2-t.

    Legyen az $a_1, a_2, \dots, a_{10}$ dobások összege 3-mal osztható. Legyen $b=a_1+1 \pmod{6}$ és $c=a_1+2 \pmod{6}$. Ekkor a $b, a_2, \dots, a_{10}$ dobások összege 3-mal osztva 1, míg a $c, a_2, \dots, a_{10}$ dobások összege 3-mal osztva 2 maradékot ad.

    E leképezés kölcsönösen (háromoldalúan) egyértelmű, hiszen bármelyik maradékot adó dobássorozatból egyértelműen előállítható a másik kettő.

    Az egyes maradékosztályokat eredményül adó dobássorozatok között tehát sikerült egy kölcsönösen egyértelmű megfeleltetést találnunk, ezek száma ezért egyenlő. A számunkra megfelelő dobássorozatok száma ezért az összes lehetséges dobássorozat harmada, azaz $\frac{6^{10}}{3}$.

  11. Egy $n$ elemű halmaznak legfeljebb hány részhalmaza adható meg úgy, hogy bármelyik kettő metszete nemüres halmaz legyen?

    Megoldás:

    Egy $n$ elemű halmaznak $2^n$ részhalmaza van. A részhalmazok párosíthatók úgy, hogy minden párban két diszjunkt halmaz legyen található (megfelelő, ha minden halmazhoz a saját komplementerét rendeljük párnak).

    Megmutatjuk, hogy a feladat kérdésére adott válasz legfeljebb $2^{n-1}$. Tegyük fel, hogy mégsem, azaz a részhalmazoknak több, mint a fele megadható megfelelően. Ekkor azonban a skatulyaelv alapján a megadottak között biztosan lenne kettő, amelyeket az előző bekezdésben egymás párjának választottunk - ám e két halmaz diszjunkt.

    Másfelől megmutatjuk, hogy $2^{n-1}$ darab részhalmaz viszont kiválasztható megfelelő módon. Jelöljük ki az eredeti halmaz egy $a$ elemét és tekintsük az összes olyan részhalmazt, amely tartalmazza $a$-t. Ezek száma nyilván $2^{n-1}$ és közülük bármely kettő metszete nemüres, hiszen tartalmazzák $a$-t.

    A feladat kérdésére adandó válasz ezért $2^{n-1}$.

Vissza