Ugrás a tartalomhoz

Elemi matematika feladatgyűjtemény

Hraskó András (2013)

ELTE-TTK

13 Kombinatorika feladatok megoldása

13 Kombinatorika feladatok megoldása

13.1 A szita módszer feladatok megoldása

A 5.1.2 feladat megoldása

Venn diagramon ábrázoljuk az első, a második és a harmadik feladatot megoldók halmazait. Az ábrába nem a versenyzőket, hanem azok számát írjuk. A megadott információkat alább átstruktúráltuk, hogy jobban tudjuk követni a diagram kitöltését.

a) 2 versenyző volt, aki mindhárom feladatot megoldotta (lásd a 127 ábrát).

b) A harmadik feladatot megoldók közül 10-zel többen oldották meg a másodikat, mint az elsőt.

c) Az elsőt és a másodikat is megoldók 10-zel többen voltak, mint akik csak a harmadikat oldották meg (lásd a 128 ábrát).

d) Aki megoldotta az elsőt és a harmadikat is, az a másodikat is megoldotta.

e) Akik csak az első vagy csak a második feladatot oldották meg, összesen 14-en voltak (lásd a 129 ábrát).

f) 56 versenyző oldott meg legalább egy feladatot.

127. ábra

128. ábra

129. ábra

Tehát 11+10+2=23 diák oldotta meg a 3. feladatot. A feladat feltételei kielégíthetőek, ha a1 és a2 helyébe tetszőleges olyan nemnegatív számokat írunk, amelyek összege 14, akkor minden előírás megvalósul. Érdekes, hogy így az 1. és a 2. feladat megoldóinak száma nem határozható meg teljes biztonsággal, míg a 3. feladat megoldóinak száma rögzített.

A 5.1.3 feladat megoldása

Összesen 60+40+30=130 igen válasz érkezett. A lovagok egy-egy, a lókötők két-két igen választ adnak, tehát az igen válaszok száma annyival több a létszámnál, amennyi a lókötők száma. Így 30 lókötő van és 70 lovag.

Ez lehetséges is, pl ha lovagok közül 30 Napimádó és 40 Holdimádó van, a 30 lókötő pedig mind Holdimádó, akkor épp a fenti számban kapjuk a válaszokat. Persze sok más megfelelő eloszlás is van.

A 5.1.4 feladat megoldása

13.1.0.1 A 5.1.4 fel. I. megoldása

Nincs értelme 0%-nál kevesebb megoldónak. A legrosszabb esetben is csak senki oldotta meg mind a három feladatot, az nem lehet, hogy senkinél kevesebb. Tehát a versenyzők legalább 0%-a oldotta meg mindhárom feladatot. Mivel a legrosszabb esetet néztük, így ez a feladat eredménye.:-)

13.1.0.2 A 5.1.4 fel. II. megoldása

A harmadik feladatot megoldók és a második feladatot megoldók százalékos arányának összege 155%. A többletet az okozza, hogy vannak olyan versenyzők, akik mind a két feladatot megoldották. Ezek százalékos aránya legalább 55%.

A harmadik és az első feladatot ugyanígy vizsgálhatjuk együtt. Az összeg itt 75+85=160%. A többlet itt 60%, legalább ennyien vannak, akik az első és a harmadik feladatot is megoldották.

Adjuk össze azok arányát (az arány alsó becslését), akik a harmadik és a második illetve akik a harmadik és az első feladatot is megoldották: 55+60=115%. A 100% fölötti rész abból adódik, hogy vannak, akik mind a három feladatot megoldották. Ezek aránya tehát legalább 15%.

A elmondottakból világos, hogy a legrosszabb esetet néztük, tehát a feladat kérdésére a válasz: a versenyzők legalább 15%-a oldotta meg mindhárom feladatot.

13.1.0.3 A 5.1.4 fel. III. megoldása

Ha az előző megoldás mintájára az első és második, majd az első és harmadik feladat megoldóit vizsgáljuk, akkor rendre az alábbi eredményeket kapjuk:

85 + 80 = 165 , tehát legalább 65% oldotta meg az első és második feladatot is, 85+75=160, tehát legalább 60% oldotta meg az első és harmadik feladatot is, 65+60=125 tehát legalább 25% megoldotta mind a három feladatot.

Ez aztán végképp a legrosszabb eset.:-)

13.1.0.4 A 5.1.4 fel. IV. megoldása

(A diákok zöme)

A II. megoldás elején láttuk, hogy azok aránya, akik a második és a harmadik feladatot is megoldották, legalább 55%. Vessük ezt össze azzal, hogy az első feladatot megoldók aránya 85%. A két érték összege, 55%+85%=140% azért lehet több, mint 100%, mert vannak, akik mindhárom feladatot megoldották. Ezek aránya tehát legalább 40%.

Nyilvánvaló, hogy ez a legrosszabb eset, hiszen az előzőeknél is rosszabb.:-)

13.1.0.5 A 5.1.4 fel. V. megoldása

A három adott érték összege: 85%+80%+75%=240%. Ebben nincsenek beleszámítva azok, akik egy feladatot se oldottak meg. Mindenki más legalább egyszer van beszámítva, ez a résztvevők maximum 100%-a. Azok és csak azok, akik legalább két feladatot megoldottak még legalább egyszer bele vannak számítva, ez megint a résztvevők maximum 100%. Az eddig összesen maximum 200%. Azok és csak azok, akik mind a három feladatot megoldották ezeken kívül még egyszer számítanak az összegben, ők adják a 200%-on felüli részt, a 40%-ot.

Tehát legalább 40% azok aránya, akik mind a három feladatot megoldották. Ez a legrosszabb eset, az előző megoldás is ezt mutatja.:)

13.1.0.6 A 5.1.4 fel. VI. megoldása

Lehetséges, hogy a diákok 75%-a megoldotta mind a három feladatot, és volt még 10%, aki csak az elsőt illetve 5%, aki csak a másodikat oldotta meg. Így ki is jönnek az arányok és ez az eset az összes eddiginél nyilvánvalóan rosszabb. A feladat kérdésére a válasz: 75%.

13.1.0.7 Megjegyzés a 5.1.4 feladathoz

A feladat kérdése a következőképpen értendő: vélhetően sokféleképpen előfordulhat az, hogy az első, második, harmadik feladat megoldóinak aránya 85%, 80% illetve 75%. Mindegyik esetben megnézhetjük a mindhárom feladatot megoldók százalékos arányát. Az összes megvalósítható esetet figyelembe véve mennyi ennek az aránynak a minimuma. Másképp: melyik az a legnagyobb érték, amelyről bizton állítható, hogy akárhogy is történt (de a feladat feltételeinek megfelelően), a mindhárom feladatot megoldók aránya legalább akkora mint ez az érték.

A VI. megoldás nem ezzel foglalkozik, hanem azzal, hogy az összes megvalósítható esetet figyelembe véve mennyi a mindhárom feladatot megoldók arányának maximuma.

Az I-V. megoldásokban hiányzik annak igazolása, hogy valóban a minimumról van szó, mindegyik egy jó alsó korlátot ad a minimumra. A legrosszab eset-re való hivatkozás félrevezető, mert a legrosszabb fogalma nincs tisztázva.

13.1.0.8 A 5.1.4 fel. VII. megoldása

Megmutatjuk, hogy a feladat kérdésére a 40% a helyes válasz, a IV., V. megoldások eredménye éles. Lehetséges, hogy a résztvevőknek csak a 40%-a oldotta meg mind a három példát. Kizárhatjuk, hogy az olimpikon, ha helyesen gondolkodik, akkor nagyobb arányt garantáló bizonyítással térjen vissza.

130. ábra

Az V. megoldásból az is világos, hogy a 40%-os határ csak akkor érhető el, ha nincs olyan vesenyző, aki pontosan egy feladatot oldott meg. Jelölje xij (1i<j<3) azok arányát százalékban, akik pontosan két feladatot oldottak meg, nevezetesen az i-ediket és a j-ediket (lásd a 130 ábrát). Ha valóban 40% a mindhárom feladatot megoldók száma, akkor az alábbi egyenletrendszert írhatjuk fel:

x 12 + x 13 + 40 = 85 x 12 + x 23 + 40 = 80 x 13 + x 23 + 40 = 75 , } x 12 + x 13 = 45 x 12 + x 23 = 40 x 13 + x 23 = 35 , }

amiből a már látott módon fejezhetők ki az ismeretlenek:

x 12 = 25 , x 13 = 20 , x 23 = 15 .

Ezekkel a százalékos arányokkal megvalósíthatók a feladat feltételei. Tehát legalább a résztvevők 40% megoldotta mind a három feladatot és lehetséges, hogy ennél többen nem oldották meg mind a három példát.

13.1.0.9 A 5.1.4 fel. VIII. megoldása

A kérdés így szólt: Legalább hányan oldhatták meg mindhárom feladatot?. Ez nem százalékos arányra vonatkozik, hanem darabszámra, azaz főre. A VII. megoldásban kijött százalékos arányok: 15%, 20%, 25%, 40%, ezek mindegyikének egész fő felel meg, tehát legnagyobb közös osztójuknak az 5%-nak is egész szám felel meg. A legkisebb megoldást az 5%=1 fő esetén kapjunk, ilyenkor a mindhárom feladatot megoldó diákok száma 8. Tehát legalább 8-an oldották meg mind a három példát.

13.1.0.10 A 5.1.4 fel. IX. megoldása

A VIII. megoldásból kiderül, hogy nem a mindhárom feladatot megoldó versenyzők százalékos arányának minimumát keressük, hanem a darabszám minimumát.

Ez nagy különbség. Lehet, hogy a százalékos arányban nem optimális megoldás adja darabszámra az optimumot. Első megközelítésben nem elképzelhetetlen, hogy 50% a mindhárom feladatot megoldók aránya, de minden más előforduló arány is a 10% többese, így a 10%=1 fő helyettesítés a mindhárom feladatot megoldó diákok számára 5-öt ad, ami kisebb az előbb kapott 8-nál. Mégsem fordulhat elő ez az eset, mert a feladat szövegében említett 85%, 80%, 75% mind egész értéknek felel meg, tehát az 5% is egész, tehát legalább 1. Ezzel a kiegészítéssel a VIII. feladat megoldása helyes.

A 5.1.12 feladat megoldásai

13.1.0.11 A 5.1.12 fel. I. megoldása

(Hiányos)

Jelölje k az egy kör által lefedett területet, l a kettő által, m a három által, n a négy által lefedett területet. Ekkor a négy kör összege k+2l+3m+4n. Ez akkor lesz a legnagyobb, ha n a legnagyobb szám, m a következők összege,és így tovább. Az így kapott maximális összeg 49+3(8+7+6)+2(5+4+3)+(2+1+0)=126 Ezt osszuk el 4-gyel, hogy megkapjuk az egy körre jutó összeget! Így 31,5-t kapunk, ennél tehát nem lehet nagyobb a körösszeg, hanem legfeljebb csak 31 lehet.

13.1.0.12 Megjegyzés a 5.1.12 fel. I. megoldásához

Fent nem láttuk be, hogy a 31 elérhető, ezért a megoldás hiányos. És valóban, alább látni fogjuk, hogy a maximum ennél kisebb.

13.1.0.13 A 5.1.12 fel. II. megoldása

Jelölje a körök egyenlő összegét x, az egyes tartományokba írt számokat pedig a 131. ábrán a megfelelő helyre írt betű.

Összeadom körönként azokat a területeket, amik rajta kívül esnek, ez 45-x (45=0+1+2+3+4+5+6+7+8+9) Ha ezeket az (egyenlő) számokat sikerül csökkenteni, akkor nő a körökön belüli összeg.

45 - x = i + a + j = i + f + c + d + a = i + f + h + g + j = a + b + d + g + j Innen leolvashatjuk az alábbiakat: i=b+d+ga=f+h+g és j=f+c+d. Mivel azt szeretnénk, hogy 45-x minimális legyen ezért az i+a+j=(b+d+g)+(f+h+g)+(f+c+d) összeget akarjuk minimalizálni. Mivel ebben az összegben g,f,d szerepel kétszer, így ők lesznek a legkisebbek.

131. ábra

Legyen g;f;d=0;1;2 és b;h;c=3;4;5 Így i+a+j6+7+8 De ekkor i+a+j(b+d+g)+(f+h+g)+(f+c+d) vagyis számokkal behejttesítve: 6+7+8>k=05n+k=02n azaz 6+7+8>20+21+22+3+4+5 ami egyszerűbben írva: 21>18

Ha b;h;c-t eggyel növeljük, akkor i+a+j eggyel csökken. Ekkor 20>19 tehát még ez sem jó. 45-x-et min. 2-vel kell csökkenteni. Erre a következő levezetésnél látunk majd megoldásokat.

13.1.0.14 A 5.1.12 fel. III. megoldása

Használjuk az előző megoldás ábrájához tartozó jelöléseket!

Az egyes körökbe írt számok:

x = a + b + c + d + e x = c + e + f + h + i x = e + d + h + g + j x = b + c + d + e + f + g + h .

Vonjuk ki az első három sor összegéből az utolsót!

2 x = a + c + d + 2 e + h + i + j .

Így 2x értéke nem haladhatja meg 29+8+7+6+5+4+3=51 értékét, azaz x lévén egész szám legfeljebb 25. Ez az érték el is érhető, a 132 ábrán két példát mutatunk rá.

132. ábra

A 5.1.12 feladat megoldásai

13.1.0.15 A 5.1.12 fel. I. megoldása

Először bebizonyítjuk, hogy a sorozatnak nem lehet 17 tagja. Vegyünk az első 14 tagot a sorozatban! Ezek összege negatív, hiszen az első és a második 7 tag összege külön-külön negatív. Bármely 11 szomszédos tag összege pedig pozitív, tehát az első 11 tagé is, így az utolsó három tag (12.-14.) összege negatív. A 14-ből azonban az utolsó 11 tag összege is pozitív, így a 4.-11. tartó 8 tag összege pozitív. Mivel minden szomszédos 7 tag összege negatív, ezért a 4.-10. tartó tagok összege negatív, a 11. tag tehát biztosan pozitív. Ugyanezt megcsinálhatjuk nem az első helyről kezdve, hanem a 2.-tól (minden tag helyett az eggyel utána lévőt mondjuk most), így ha van 17 tagja a sorozatnak, akkor 2.,3.,4. tagtól kezdődve is van még 14 tag, tehát sorban a 12., 13. és 14. tag is pozitív. Ez azonban ellentmondás, mert tudjuk, hogy a 12.-14. tartó 3 tag összege negatív.

Most mutassuk meg, hogy 16 tagból állhat a sorozat! Legyen minden pozitív tag 1, minden negatív tag pedig pedig -(2,5+11000). Minden egymást követő 7 tag közt legalább 2 negatív kell legyen és minden egymást követő 11 tag közt legalább 8 pozitív kell legyen. Ezt meg is csinálhatjuk, ha a tagok: +,+,-,+,+,+,-,+,+,-,+,+,+,-,+,+.

13.1.0.16 A 5.1.20 fel. II. megoldása

Nem lehet 17 tagja. Ennek igazolásához írjuk fel egy táblázat első sorába sorba az 1., 2., , 7. elemeket, a 2.-ba a 2., 3, , 8. elemeket, stb., végül az utolsóba a 11., 12., , 17. elemeket. Ekkor minden sorösszeg negatív, minden oszlopösszeg pozitív, ez lehetetlen.

16 tag lehetséges, jó sorozat pld az alábbi:

1 ; 1 ; - 2 , 6 ; 1 ; 1 ; 1 ; - 2 , 6 ; 1 ; 1 ; - 2 , 6 ; 1 ; 1 ; 1 ; - 2 , 6 ; 1 ; 1 .

13.2 Feladatok a sakktáblán

A 5.2.1 feladat megoldásai

13.2.0.1 A 5.2.1 a) mego.

Bejárható. A 133 ábrán követhető az ugrássorozat: 0, 1, , 24 jelöli a mezőket, amelyeken a ló egymás után végigugrál.

133. ábra

13.2.0.2 A 5.2.1 b) fel. I. megoldása

Körbeéréssel nem járható be. A sarkokról csak a A 5.2.1 a) feladat megoldásának 133 ábráján látható sötétszürke mezőkre léphetünk, illetve csak onnan léphetünk a sarkokra. A sötétszürke mezőkre így egy-egy sarokról kell lépni és egy-egy sarokra kell ellépni róluk. Így a sarkokon átmenő körút szükségképpen egy nyolc mezőből álló körré álló össze, amely a 4 sarokból és a fenti négy sötétszürke mezőből áll. Ez a körút nem fedi le az össze mezőt, tehát nincs megoldás.

13.2.0.3 A 5.2.1 b) fel. II. megoldása

Nem járható be.

Tekintsük a sakktábla 134. ábrán látható szokásos színezését!

Annak a mezőnek a színe, amelyre a ló ráugrik minden lépésben megváltozik. Mivel páratlan sok mező van, az a) feladatrészben bármely eljárásnal a kezdő mező (a fenti ábrán 0) és a befejező mező (fent 24) színe mindig azonos, így nem lehet visszaugrani a kezdőmezőre.

134. ábra

A 5.2.2 feladat megoldása

Használjuk a sakktábla színezését (lásd a 135 ábrát)!

Ha két átellenes sarkot vágunk le, akkor két azonos színű mezőt hagyunk ki, így 30 marad az egyik színből és 32 a másikból. Egy 1×2-es dominó által lefedett két mező mindig különböző színű, tehát az egyik fehér, a másik fekete. Így a dominók ugyanannyi fehér és fekete mezőt tudnak lefedni, 30-at az egyik színből, 32-at a másikból nem tudnak. Így ebben az esetben nincs lefedés.

135. ábra

Ha két szomszédos sarkot vágunk le, akkor a fenti kizárás nem működik, ezek különböző színű mezők. Most lefedés is van. Ha pl a két sarok azonos sorban van, akkor fedjünk soronként! A teljes sorokban nyolc mező van, azeket lefedi nyolc dominó, a csonka sorban csak hat szomszédos mező van, ehhez elég három dominó.

előzetes megjegyzés a 5.2.3 feladathoz

A feladat úgy értendő, hogy akárki, akármilyen kellemetlen módon is jelöl ki 40 kis négyzetet ki kell(ene) választani belőle 10-et, amelyeknek nincs közös pontja.

A 5.2.3 feladat megoldása

Színezzük a végtelen négyzetrácsot négy színnel a 136 ábrán látható módon!

136. ábra

Az azonos színű mezőknek nincs közös pontja. A 40 négyzet közül lesz 10, amelyek azonos színűek, tehát annak a 10 mezőnek sem lesz közös pontja. A feladat kérdésére a válasz: Igaz, mindig kiválasztható.

A 5.2.4 feladat megoldásai

13.2.0.4 A 5.2.4 a) mego.

8-nál több bástyát nyilván nem lehet felrakni, hiszen minden sorba legfeljebb 1-et rakhatunk. 8-at fel lehet, pl. az egyik átlóba.

13.2.0.5 Megjegyzés a 5.2.4 a) feladathoz

Kérdés lehet az is, hogy a 8 bástyát hányféleképp lehet felrakni. Tanulságos lehet a különböző gondolatmenetek összehasonlítása. Ha mind egyformák, akkor 8!-féleképp, ha mind különbözőek, akkor 8!2-féleképp.

13.2.0.6 A 5.2.4 b) mego.

14 futót fel tudunk rakni pl. úgy, hogy az 1. sorba 8-at teszünk, a 8. sorba hatot úgy, hogy a két szélső mezőt üresen hagyjuk. Ennél többet nem lehet, hiszen ha az egyik átlóval párhuzamos egyeneseket tekintjük, ezekből 15 van, de magának az átlónak nem tehetünk mindkét végpontjára.

13.2.0.7 A 5.2.4 c) mego.

Sokan azt hiszik, hogy 24 lovat lehet így felrakni (pl. úgy, hogy az 1., a 4. és a 7. sort telerakjuk. Valójában 32 ló is elhelyezhető, ha pl. az összes fekete mezőre rakunk (hiszen a ló mindig ellenkező színű mezőre üt).

Tanulságos példa arra, hogy abból, hogy egy rögzített felrakás esetén nem tudunk még egy figurát felrakni, nem következik, hogy másképp elkezdve nem is lehet többet.

32-nél azonban már nem lehet többet. Ahhoz hogy ezt belássuk, tegyük fel, hogy valaki azt állítja, hogy felrakott legalább 33-at. Ekkor volna olyan fele a sakktáblának, melyen legalább 17, olyan negyede, melyen legalább 9 és olyan nyolcada, amelyen legalább 5 ló van. Ez azonban lehetetlen, a 2×4-es téglalapon minden ló pontosan egy másik mezőt üt.

Egy másik gondolatmenet a A 5.2.1 a) feladat megoldására épül. Ha azt a példát megoldottuk 8×8-as táblára is, tehát tudjuk, hogy a lóval bejárható a sakktábla, akkor azt is tudjuk, hogy a körbemenéskor csak minden második mezőn lehet ló, tehát maximum 32 lehet a táblán.

13.2.0.8 A 5.2.4 d) mego.

16 királyt könnyű felrakni, többet nem lehet (az előző gondolatmenethez hasonlóan látható be).

13.2.0.9 A 5.2.4 e) mego.

8-nál többet nyilván nem lehet, némi ügyességgel 8-at igen.

A 5.2.5 feladat megoldásai

13.2.0.10 A 5.2.5 a) mego.

8 a minimum. Ha kevesebb bástyát helyeztünk el, akkor kimaradt még sor és oszlop is, azok kereszteződésében elhelyezhetünk még egyet.

13.2.0.11 A 5.2.5 b) fel. eredménye

Itt 5 a minimum, de a konstrukció nem könnyű és nem átlátható röviden annak igazolása, hogy 4 nem elég.

A 5.2.6 fel. eredménye

a) 6449366=3456

b) 644936=20736;

c) 6449362=10368.

13.3 Egyszerűbb leszámolási feladatok megoldása

A 5.3.5 feladat megoldása

Egyik lehetséges gondolatmenet esetszétválasztáson alapul aszerint, hogy hány golyót választunk ki. (0 golyót 1-féleképpen választhatunk, 1 golyót 20-féleképp, 2 golyót 20 alatt a 2-féleképp stb.) Így a Pascal-háromszög 20. sorának összegét kapjuk.

Másik gondolatmenet szerint egy 20 elemű halmaz összes részhalmaza lesz jó, melyek száma 220.

Ha minden golyó egyforma, akkor 21 lehetőségünk van (vagy0, vagy 1, vagy 2 ...vagy 20 golyót választunk ki).

13.3.0.1 Megjegyzés a 5.3.5 fel. megoldásához

Érdekes lehet olyan eseteket is meggondolni, amikor vannak egyformák is és különbözőek is a golyók között.

A 5.3.6 feladat megoldása

1 × 1 -es négyzet 64, 2×2-es 49, 8×8-as egy van, így a rácsnégyzetek száma

1 + 2 2 + 3 2 + 4 2 + 5 2 + 6 2 + 7 2 + 8 2 = 204 .

Egy rácstéglalapot meghatároz két átlós csúcsa. Az egyik csúcs a 81 rácspont bármelyike lehet. A vele átlósan szemben levő csúcsot az ő rácsegyenesén nem választhatjuk, marad 64 lehetőség. Ílymódon minden téglalapot 4-szer számoltunk (Ugyanazt a két csúcsot választjuk fordított sorrendben, illetve a másik átlójának választottuk ki a két végpontját), a válasz tehát 8116=1296.

Úgy is gondolkodhatunk, hogy egy téglalap megadásához két különböző vízszintes és két különböző függőleges rácsegyenest kell kiválasztanunk a 9 vízszintes és 9 függőleges rácsegyenes közül.

( 9 2 ) ( 9 2 ) = 9 8 9 8 2 2 = 1296 .

A 5.3.7 feladat megoldásai

13.3.0.2 A 5.3.7 a) mego.

Összesen 6!=720-féle hatjegyű számot készíthetünk. Ezek fele lesz páros (2-re végződő is 5! darab van, 4-re és 6-ra végződő is). Mindegyik osztható lesz 3-mal, hiszen a számjegyek összege 21.

4-gyel azok lesznek oszthatók, melyek végződése a 12, 16, 24, 32, 36, 52, 56, 64 valamelyike. Minden végződéshez 4!-féle lehet az első 4 számjegy sorrendje, így a válasz 84!=192.

Az 5-tel oszthatóknak 5-re kell végződniük, ilyenből 5!=120 van.

6-tal az összes páros osztható lesz (mert 3-mal mind osztható).

13.3.0.3 Megjegyzés a 5.3.7 a) feladat megoldásához

Az, hogy az elkészíthető számok fele páros, nem automatikus, pl. ha. 1-től 7-ig lenne a számkészletünk, melyből 7-jegyű számokat készítünk, nem az összes elkészíthető szám fele lenne páros (hanem 3/7 részük) mint ahogy példánkban sem a számok harmada osztható 3-mal vagy a negyede 4-gyel.

13.3.0.4 A 5.3.7 c) mego.

Láttuk, hogy a hárommal való oszthatóság feltétele nem megszorítás ebben az esetben. Minden helyiértéken minden számjegy ugyanannyiszor szerepel, azaz 6!/6=5!=120-szor. Helyiértékenként összeadva az ott szereplő számokat, minden helyiértéken (1+2+3+4+5+6)5!=2520 lesz a számok összege. Így az összeg

111111 ( 1 + 2 + 3 + 4 + 5 + 6 ) 5 ! = 279999720 .

13.3.0.5 A 5.3.7 b) mego.

Összesen 66 szám készíthető. A párosak esetén az utolsó számjegyet 3-féleképp választhatjuk meg, az összes többit 6-féleképpen, a párosak száma 365.

Ahhoz, hogy 3-mal oszthatót kapjunk, az első 5 számjegyet tetszőlegesen választhatjuk meg, az utolsó számjegynél kell ügyelnünk arra, hogy a számjegyek összege 3-mal osztható legyen. Erre minden kezdés esetén két lehetőségünk van (a hat számjegy közül minden 3-as maradékhoz 2 tartozik), így a lehetőségek száma 652.

4-gyel azok a számok lesznek oszthatók, melyek végződése a 12, 16, 24, 32, 36, 44, 52, 56, 64 valamelyike, így a lehetőségek száma 964.

Az 5-tel oszthatók száma 56 (5-re kell végződniük, a többi jegy tetszőleges).

A 6-tal oszthatók száma a 3-mal oszthatókénak a fele, azaz 65 (a háromféle hármas maradékot képviselő 2-2 szám közül minden esetben az egyik páros).

13.3.0.6 A 5.3.7 d) mego.

Ha egy tetszőleges számjegyet egy tetszőleges helyiértéken rögzítünk, akkor a maradék 5 helyre a számjegyeket 642-féleképpen adhatjuk meg. Tehát most ninden helyiértéken minden számjegy 642=2592-ször szerepel. A c) feladatrészben leírt gondolatmenet alapján most az összeg

111111 ( 1 + 2 + 3 + 4 + 5 + 6 ) 6 4 2 = 6047993952 .

A 5.3.8 feladat megoldásai

13.3.0.7 A 5.3.8 a) mego.

Összesen 9000 négyjegyű szám van. Olyan, amiben nem szerepel a 7-es számjegy 893=5832 van (az első számjegy nem lehet 0 vagy 7, a többi bármi lehet a 7-en kívül). Az összesből levonva azok számát, melyekben nem szerepel a 7-es, megkapjuk azokét, melyekben igen. Mivel az 5832 nagyobb, mint a 9000 fele, olyanból van több, amiben nincs 7-es.

13.3.0.8 A 5.3.8 b) mego.

Olyan számot, melyben a számjegyek szigorúan növekvő sorrendben állnak, úgy kapunk, hogy a 9 lehetséges számjegyből (a 0 egy ilyen számban nem szerepelhet) kiválasztunk 4 különbözőt, és azokat növekvő sorrendbe rakjuk. A válasz tehát (94)=126, ami sokkal kevesebb, mint a 9000/2 fele, így ilyen van kevesebb.

13.3.0.9 A 5.3.8 c) mego.

Ha a számban nincsenek egyforma számjegyek, akkor az első számjegy 9-féle (0 nem), a második is 9-féle (0 már lehet, de ugyanez, mint az első nem), a harmadik 8, a negyedik 7-féle lehet. Ez összesen 9987=4536 lehetőség, ami több mint a 9000 fele, így ilyenből van több.

13.3.0.10 Megjegyzés a 5.3.8 feladathoz

Érdemes a kérdést nem négyjegyű számokra is megvizsgálni (a vizsgálódás gondolatmenete hasonló).

A 5.3.9 feladat megoldása

A feladatot megoldhatjuk esetszétválasztással aszerint, hogy hány darabból akarjuk kirakni a 10-et (és evvel egyben megoldjuk a b) feladatot.

Gondolkodhatunk úgy is, hogy elképzelünk egy 10 cm hosszú rudat, cm-es beosztásokkal, melyet minden lehetséges módon szét akarunk fűrészelni a beosztások mentén. Minden beosztásnál 2 lehetőségünk van vagy fűrészelünk, vagy nem. Így a lehetőségek száma 29.

2 db rúdból 9-féleképp rakhatjuk ki (1+9,2+8,3+7,,9+1). 3 db esetén a lehetséges 9 választóvonalból 2-t kell kiválasztanunk, 4 db. esetén 3-at, stb. Megoldásként a Pascal-háromszög 9. sorának elemeit kapjuk.

13.3.0.11 Megjegyzés a 5.3.9 feladathoz

Az a) és b) feladat megoldását összevetve bizonyíthatjuk, hogy a Pascal-háromszög n-edik sorában szereplő elemek összege 2n.

Érdemes először rövidebb rudak kirakásával kísérleteznünk. Az egységnyi hosszúságút nyilván csak egyféleképp rakhatjuk ki. A 2 hosszúságút 2-féleképp (1+1 vagy 2). A 3 hosszúságút 3 (1+1+1, 1+2, 2+1) és mielőtt hamis sejtésre jutnánk a 4 hosszúságút 5 (1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2).

Hogyan kaphatjuk meg eddigi eredményeink felhasználásával próbálgatás nélkül az 5 hosszúságú rudak kirakási lehetőségeinek számát? Jó kirakást kapunk, ha az összes különböző 4-es kirakást 1-gyel folytatjuk (1+1+1+1+1, 1+2+1+1, 2+1+1+1, 1+1+2+1, 2+2+1). Így megkapjuk az 5-ös rúd összes 1-re végződő kirakását. A 2-re végződő kirakásokat vagy úgy kapjuk meg, hogy az 1-re végződő 4-es kirakásokban az 1-es végződést 2-re cseréljük (1+1+1+2, 1+2+2, 2+1+2), vagy úgy, hogy a 3-as kirakásokat toldjuk meg 2-vel. Mindenképp ugyanazt kapjuk, hiszen 1-re végződő 4-es kirakás pont annyi volt, mint ahány hármas kirakás összesen.

Ez a gondolatmenet folytatható (vannak tanulók, akiket érdemes hagyni, hogy tovább kísérletezzenek, mielőtt megsejtik, hogy az előző két kirakási lehetőség összegződik, vagyis a Fibonacci-sorozat elemeit kapjuk). Folytatva a Fibonacci sorozatot, eljutunk a válaszhoz: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.

A 5.3.10 feladat megoldásai

13.3.0.12 A 5.3.10 a) mego.

Ha elképzelünk egy 100 cm hosszú rudat cm-es beosztásokkal (99 beosztás), akkor az a kérdés, hogy hányféleképpen tudjuk ezt szétvágni a beosztások mentén 10 darabra. Nyilván annyiféleképp, ahányféleképp a 99 osztóvonalból kiválaszthatunk 9-et, vagyis (999)-féleképp.

13.3.0.13 A 5.3.10 b) mego.

Most képzeljük úgy, hogy 2 centinként vannak a beosztások (49 beosztás), ezek közül kell kiválasztanunk 9-et, vagyis (499)-féleképp.

13.3.0.14 A 5.3.10 c) mego.

10 egész összegeként nyilván végtelen sokféleképpen előállítható a 100.

13.3.0.15 A 5.3.10 d) mego.

Ha a 100-at 10 tagú összegként akarjuk felírni, szükségünk van 100 db 1-esre és 9 db. + jelre. Ezek bármilyen sorrendje jó előállítást ad a + jelek közti 1-eseket összegezve (ha két + jel szerepel egymás mellett, akkor 0 van köztük az összegben, ha a sor elején (vagy végén) van + jel, akkor az összeg 0-val kezdődik (vagy végződik)). Így a lehetőségek száma (1099).

A 5.3.11 feladat megoldása

Annyit, ahányféleképp a 90 számból (hagyományos ötös lottó esetén) kiválasztható 5, tehát (905)=43949268.

A 5.3.12 feladat megoldásai

13.3.0.16 A 5.3.12 a) mego.

190 (annyit, ahányféleképp 20-ból kiválaszthatunk 18-at (vagy 2-t, ami nem nyer).

13.3.0.17 A 5.3.12 b) mego.

Egy szelvény elég.

A 5.3.13 feladat megoldása

Ha az egyik iskolából x, a másikból y versenyző indult, akkor iskolákon belül

x ( x - 1 ) 2 + y ( y - 1 ) 2 = 66 mérkőzés volt, az iskolák között pedig xy=136-66=70.

Az egyenletrendszer megoldása x=10, y=7 (vagy fordítva).

A 5.3.14 feladat megoldása

Csoportosítsuk a háromszögeket a legnagyobb szögük szerint (ez legfeljebb 177, legalább 91 fok), és nézzük meg, hogy a maradék két szög hányféleképp áll elő két különböző pozitív egész összegeként. Az 1, 1, 2, 2, 3, 3, 4, 443, 43, 44 számokat kapjuk, melyek összege 1936.

A 5.3.15 feladat megoldása

Összesen n csapat (n-1)2 mérkőzést játszott, így n(n-1) pont került szétosztásra. Ha nem lett volna döntetlen, akkor minden csapat páros számú ponttal végzett volna. Ez n csapat esetén a 0, 2, 4, 6, 2n-2 (n-féle) pontszámok valamelyikét jelentené minden csapat számára. Az egyértelmű sorrend miatt minden csapat pontszáma különböző kellett volna, hogy legyen, vagyis az előbbi pontszámok mindegyike pontosan egy csapathoz tartozott volna. Ez csak úgy fordulhatott volna elő, ha 1 csapat mindenkit legyőzött volna, egy csapat az előzőn kívül mindenkit legyőzött volna stb. Ezt a feladat feltételei kizárják, így kellett döntetlennek lennie.

A 5.3.16 feladat megoldása

Egyik lehetséges megfontolás, hogy megvizsgáljuk, hogy az egyes mezőkre hányféleképp juthatunk. Azt tapasztaljuk, hogy minden mezőre annyiféleképp juthatunk, mint az alatta levőre és a jobbra mellette levőre összesen.

Úgy is gondolkodhatunk, hogy összesen 14 mezőnyi lépést kell megtennünk (7 jobbra és 7felfelé), így a válasz az, hogy ahányféleképp az összesen 14 lépésnyiből kiválaszthatjuk azt a 7-et, amit mondjuk, felfelé teszünk meg. (Azaz a lehetőségek száma (147)=3432, ami a Pascal háromszög 7. sorában a középső elem.)

13.4 A Pascal háromszög feladatok megoldása

Pascal eredetileg a 137 ábrán látható elrendezésben adta meg háromszögét.

137. ábra

A koordinátarendszer zárt pozitív síknegyedének rácspontjaiba írtunk számokat úgy, hogy az origóba 1-est írtunk, majd onnan kiindulva jobbra és felfelé haladva minden rácspontra az alatta és tőle balra levő számok összegét írtuk le. A (k;l) koordinátájú pontra írt számot (k+lk)=(nk)-val is jelöljük és n alatt a k-nak mondjuk, ahol n=k+l. A Pascal háromszög n-edik sorát azok az elemek alkotják, amelyek koordinátáinak összege: k+l=n. A sorokat tehát 0-tól kezdjük számozni. A soron belül az elemeket is 0-tól kezdve sorszámozzuk, az n-edik sorban tehát 0-tól n-ig. Az n-edik sor k-adik eleme (nk), tehát a (k;n-k) koordinátájú pontba írt szám. Ezekkel a jelölésekkel tehát:

( 0 0 ) = 1 ,

és

( n k ) = ( n - 1 k - 1 ) + ( n - 1 k ) ( n > 1 , n N ) .

A (160)-(161) képletek önmagukban még nem definiálják a Pascal háromszöget, hiszen általuk még (10) értéke sincs meghatározva. A (161) képlet szerint ugyanis

( 1 0 ) = ( 0 - 1 ) + ( 0 0 ) ,

de (0-1) értékéről nincs információnk. A problémát áthidalná, ha 1-nek rögzítenénk a Pascal háromszög szélein elhelyezkedő elemek, azaz (n0) és (nn) értékét (nN). Ehelyett más utat választunk. Legyen

( 0 k ) = 0 ( k 0 , k Z ) .

Az (160), (161), (162) képletek már meghatározzák a Pascal háromszöget, sőt segítségükkel soronként kitölthető a Pascal félsík (lásd a 138 ábrát).

138. ábra

A 5.4.1 feladat megoldásai

13.4.0.1 A 5.4.1 fel. I. megoldása

Jelölje a feladat megoldását u(k;l). Vegyük észre, hogy a (k;l) pontra vagy a (k-1;l) vagy a (k;l-1) pontról lépünk rá. Tehát annyiféleképpen juthatunk el (k;l)-be, mint (k-1;l)-be és (k;l-1)-be összesen:

u ( k ; l ) = u ( k - 1 ; l ) + u ( k ; l - 1 ) .

Másrészt

u ( 0 ; 0 ) = 1 ,

és

u ( k ; - k ) = 0 ha  k 0 , k Z .

A (163), (164), (165) összefüggéseket teljesíti az (k+lk) mennyiség, ha azt u(k,l) helyébe írjuk, hiszen épp ezeket az összefüggéseket fogalmazzák meg a (160), (161), (162) képletek. Mivel u(k;l) értékét meghatározzák a (163) (165) relációk, így

u ( k ; l ) = ( k + l k ) .

13.4.0.2 A 5.4.1 fel. II. megoldása

Pontosan akkor jutunk az origóból a (k;l) pontba, ha összesen n=k+l lépést teszünk és abból k-szor jobbra és l-szer felfelé lépünk. A lépések sorszámai:

1 . , 2 . , 3 . , ( n - 1 ) . , n .

Ezek közül ki kell választani azt a k lépést, amelyikben balra léptünk. Álljunk neki a kiválasztásnak! Először egyet választunk, ez n-féle lehet; a következő már az első bármely választása esetén csak (n-1)-féle, stb, az utolsót már csak (n-k+1)-féle. Így

n ( n - 1 ) ( n - 2 ) ( n - k + 1 )

esetet kaptunk, de ebben a kiválasztás sorrendjét is belevettük. Nem számít, hogy az előbbi eljárás során egy adott sorszámú lépést a kiválasztás során hanyadik lépésben találtunk meg, csak az számít, hogy bevettük-e a kiválasztásba vagy nem. A kiválasztott k lépést összesen k!-féle sorrendben választhattuk ki a fenti eljárás során, tehát a (k;l) pontbavezető lépéssorozatok száma:

u ( k ; l ) = n ( n - 1 ) ( n - k + 1 ) k ! .

I. Megjegyzés a 5.4.1 feladathoz

A két megoldás eredményét összetéve állíthatjuk, hogy

( n k ) = n ( n - 1 ) ( n - k + 1 ) k ! .

II. Megjegyzés a 5.4.1 feladathoz

A II. megoldás mutatja, hogy az n elemből álló halmaz k-elemű részhalmazaina száma épp (nk). Valóban a II. megoldásban a lépéssorszámok {1.;2.;;n.} halmazából választottunk ki az összes lehetséges módon k elemet, erre kaptuk az u(k;l)=(nk) eredményt.

A 5.4.2 feladat megoldásai

13.4.0.3 A 5.4.2 fel. I. megoldása

Ha maradunk a természetes kitevőnél (nN), akkor a binomiális tételt könnyen igazolhatjuk. Az

( a + b ) n = ( a + b ) ( a + b ) ( a + b ) ( a + b )

szorzat n tényezőből áll és a zárójelek felbontásakor minden egyes tényezőből kiválasztjuk az a vagy a b tagot, így an-ibi alakú tagokat kapunk és ilyenből épp annyit, ahányféleképpen kiválasztható az n szorzótényezőből az az i darab, amelyből a b tagot választjuk. Ezek száma (ni).

13.4.0.4 A 5.4.2 fel. II. megoldása

n szerinti teljes indukcióval, az (a+b)n+1=(a+b)n(a+b) azonosság felhasználása és a Pascal háromszög képzési szabálya alapján is bizonyíthatunk.

Segítség a 5.4.3 feladathoz

Keressük meg az eredményt a Pascal háromszögben. Indokoljuk meg a kapcsolatot!

Segítség a 5.4.4 feladathoz

Keressük meg az eredményt a Pascal háromszögben. Indokoljuk meg a kapcsolatot!

előzetes megjegyzés a 5.4.5 feladathoz

Alább látható, hogy az egyes sorokban mennyi az összeg:

78. táblázat

Sejthető, hogy az n-edik sor elemeinek összege 2n.

A 5.4.5 feladat megoldásai

13.4.0.5 A 5.4.5 fel. I. megoldása

Jelölje az n-edik sor elemeinek összegét Sn. A 0-sorban csak egy 0-tól különböző szám van, ami 1, így

S 0 = 1 .

Másrészt bármelyik sort az előzőből képezzük úgy, hogy az előző sor két elemének összegeként kapjuk az új sor egy elemét. (Az alábbi ábrán a 3. sor az előző sor és a 4. sor az új sor.) Az előző sor bármely elemét az új sor két elemében kell tekintetbe venni: a tőle jobbra levőben és a fölötte levőben. Így a sorösszeg mindig megduplázódik:

S n + 1 = 2 S n .

139. ábra

Mindezekből Sn=2n.

13.4.0.6 A 5.4.5 fel. II. megoldása

A feladat így fogalmazható át: hányféleképpen juthatunk el az origóból az n-edik sorba, ha minden lépésben egyet léphetünk jobbra vagy felfelé? Erre a kérdésre 2n a válasz, hiszen összesen n lépést kell tennünk és mindegyikről dönthetünk, hogy felfelé vagy jobbra vezessen.

13.4.0.7 A 5.4.5 fel. III. megoldása

A feladat így fogalmazható át: hány részhalmaza van az n elemből álló halmaznak? Természetesen 2n hiszen minden elemről külön-külön eldönthetjük, hogy belevesszük-e a részhalmazba vagy nem.

13.4.0.8 A 5.4.5 fel. IV. megoldása

Alkalmazzuk Newton binomiális tételét (lásd a 5.4.2 feladatot)!

Az (a+b)n=k=0n(nk)akbn-k formulába írjunk a és b helyére is 1-et!

2 n = ( 1 + 1 ) n = k = 0 n ( n k ) 1 k 1 n - k = k = 0 n ( n k ) .

A 5.4.6 feladat megoldásai

13.4.0.9 A 5.4.6 fel. I. megoldása

(Rekurzió)

A 0-adik sort kivéve mindegyik sort az előző sorból képezzük. Az előjeles összegben az előző sor minden egyes tagját egyszer pozitív és egyszer negatív előjellel vesszük figyelembe, összesen tehát minden egyes tagot 0-szor. így az előjeles összeg minden olyan sorban zérus, amelyet egy előző sorból kaptunk. A 0-adik sorban az összeg 1.

13.4.0.10 A 5.4.6 fel. II. megoldása

(Kombinatorikai értelmezés)

Állítjuk, hogy az előjeles összeg a nulladik sortól különböző sorokban zérus. Ez az állítás ekvivalens a következővel: egy nem üres véges halmaz páros elemszámú részhalmazainak száma megegyezik a páratlan elemszámú részhalmazainak számával. Az utóbbit könnyű igazolni.

Válasszuk ki a nem üres halmaz egy tetszőleges elemét! Ha készítünk egy részhalmaz, akkor róla is el kell dönteni, hogy belekerüljön-e vagy ne. Választásunktól függően a létrejövő részhalmaz páros elemszámú lesz vagy páratlan. így a páros elemszámú részhalmazok és a páratlan elemszámú részhalmazok között kölcsönösen egyértelmű megfeleltetést kapunk, ha azokat a részhalmazokat párosítjuk egymással, amelyek csak abban különböznek egymástól, hogy tartalmazzák-e az előre kiválasztott elemet vagy nem.

13.4.0.11 A 5.4.6 fel. III. megoldása

(Binomiális tétel)

Alkalmazzuk Newton binomiális tételét (lásd a 5.4.2 feladatot)!

Az (a+b)n=k=0n(nk)akbn-k formulába írjunk a helyére (-1)-et, b helyére 1-et!

0 n = ( 1 - 1 ) n = k = 0 n ( n k ) ( - 1 ) k 1 n - k = k = 0 n ( - 1 ) k ( n k ) ,

tehát n>0, nN esetén az előjeles összeg értéke zérus.

előzetes megjegyzés a 5.4.7 feladathoz

Alább látható, hogy az egyes sorokban mennyi a négyzetösszeg:

79. táblázat

Az eredmények megtalálhatók a Pascal háromszögben, a főátlóban. Sejthető, hogy az n-edik sor elemeinek négyzetösszege (2nn).

A 5.4.7 feladat megoldása

A Pascal háromszög szimmetrikus a főátlójára, azaz (ni)=(nn-i), tehát n=i+j esetén

( n i ) = ( n j ) .

Azt kell tehát igazolnunk, hogy

i + j = n ( n i ) ( n j ) = ( 2 n n ) .

A jobb oldalon látható kifejezés értelme világos: ennyiféleképpen juthatunk el az origóból az (n;n) pontba 2n lépésben, ha minden lépésben a jobbra vagy felfelé található szomszédos rácspontra megyünk át. Egy ilyen útvonal pontosan egyszer halad át a x+y=n egyenletű egyenesen, mindig ezen egyenes egy rácspontján megy keresztül. Legyen ez a rácspont a (i;j) pont.

Hány útvonal megy az origóból (2n;n)-be a (i;j) ponton (i+j=n) keresztül? Az origóból a (i;j) pontba

( i + j i ) = ( n i )

útvonal megy, míg onnan, hogy (2n;n)-be jussunk még (n-i)=j-t kell jobbra lépni és (n-j)=i-t felfelé, tehát az utak száma

( n - i + n - j n - i ) = ( n j ) .

Az origóból (i;j)-be menő bármely utat folytathatjuk az (i;j)-ből (2n;n)-be vezető bármely úton, tehát a keresett utak száma:

( n i ) ( n j ) .

Tehát a (168) képlet bal oldalán látható kifejezés is az origóból a (2n;n) pontba menő utak számát adja meg, mégpedig aszerint részletezve, hogy az x+y=n egyenes melyik rácspontján megy át egy adott út.

előzetes megjegyzés a 5.4.8 feladathoz

Ez a példa, az előző (5.4.7 feladat) általánosítása, hiszen a (17) formulából a 5.4.7 feladat eredménye a k=l=n helyettesítéssel adódik.

A 5.4.8 feladat megoldásai

13.4.0.12 A 5.4.8 fel. I. megoldása

Számoljuk össze az origóból az (n,k+l-n) pontba menő lépéssorozatok számát, ha minden lépésben a jobbra vagy felfelé található szomszédos rácspontra megyünk át!

Az ilyen utak száma egyszerűen (k+ln).

Soroljuk fel az utakat aszerint is, hogy hol metszik az x+y=k egyenest! Számítsuk ki azon utak számát, amelyek az (i,k-i) pontban metszik ezt az egyenest. Az origóból ide menő utak száma (ki), míg innen tovább (n,k+l-n)-be még összesen l-et kell lépnünk és ebből j=(n-i)-t felfelé, tehát a továbbmenetelre (ln-i) lehetőség van. Az origóból a (n,k+l-n) pontba az (i,k-i) ponton át menő lépéssorozatok száma tehát (kl)(ln-i). Ezeket a számokat össze kell adnunk, az x+y=k egyenes összes pontjára. Ez a (17) képletnek megfelelően épp azt jelenti, hogy i-t futtatnunk kell, hogy az (i,k-i) pont bejárja ezt az egyenest.

13.4.0.13 A 5.4.8 fel. II. megoldása

Tegyük fel, hogy egy társaságban k fiú és l lány van. Hányféleképpen választhatunk ki közülük n embert? Természetesen (k+ln)-féle módon. Ez a kifejezés áll a (17) egyenlet bal oldalán. Másrészt, ha végiggondoljuk hány olyan kiválasztás van, amelyben a fiúk és lányok megoszlása (0;n), (1;n-1), (2;n-2), , (n;0), akkor a (17) egyenlet bal oldala jelenik meg.

13.4.0.14 A 5.4.8 fel. III. megoldása

Az alábbi egyenlet nyilvánvalóan azonosságot fejez ki:

( 1 + x ) k ( 1 + x ) l = ( 1 + x ) k + l .

Határozzuk meg xn együtthatóját az egyik, illetve a másik oldalon. A jobb oldalon ez az együttható (k+ln), míg a bal oldalon az (1+x)k felbontásában szereplő xi és az (1+x)l felbontásában szereplő xj szorzatából jön ki ilyen tag valahányszor i+j=n.

A 5.4.9 feladat megoldásai

13.4.0.15 A 5.4.9 a) fel. I. megoldása

(Rekurzió)

Az első néhány sorba kiszámolva az összeget sejthetjük, hogy az n-edik sorban a kifejezés értéke 3n. Ezt indukcióval igazolhatjuk. Az (n+1)-esik sorhoz tartozó kifejezés 2k(n+1k) alakú tagokból áll. De

2 k ( n + 1 k ) = 2 k ( ( n k ) + ( n k - 1 ) ) = 2 k ( n k ) + 2 2 k - 1 ( n k - 1 ) ,

ahol 2k(nk) és 2k-1(nk-1) az előző sor kifejtésében szereplő tagok. Tehát ha az összeg értéke az n-edik sorban bn, akkor

b n + 1 = k = 0 n + 1 2 k ( n + 1 k ) = k = 0 n + 1 2 k ( n k ) + 2 k = 0 n + 1 2 k - 1 ( n k - 1 ) = b n + 2 b n = 3 b n .

13.4.0.16 A 5.4.9 a) fel. II. megoldása

(Kombinatorikai értelmezés)

Hányféleképpen tölthető ki az n mérkőzésből álló totó szelvény? Természetesen 3n-féleképpen. Dr Agy nem szereti a döntetlent. ő először kiválasztja azokat a meccseken, amelyekről feltételezi, hogy eldőlnek, ezek mindegyikére eldönti, hogy ki fog nyerni, a maradékokra pedig X-et ír (azok a döntetlenek). Ha így számoljuk végig a lehetőségeket, akkor könnyű meggondolni, hogy a k=0n2k(nk) kifejezést kapjuk.

13.4.0.17 A 5.4.9 a) fel. III. megoldása

(Binomiális tétel)

Alkalmazzuk Newton binomiális tételét (lásd a 5.4.2 feladatot)!

Az (a+b)n=k=0n(nk)akbn-k formulába írjunk a helyére 22-t, b helyére 1-et!

3 n = ( 2 + 1 ) n = k = 0 n ( n k ) 2 k 1 n - k = k = 0 n 2 k ( n k ) .

13.4.0.18 A 5.4.9 b) fel. I. megoldása

(Rekurzió)

Az első néhány sorba kiszámolva az összeget sejthetjük, hogy az n-edik sorban a kifejezés értéke n2n-1. Ezt indukcióval igazolhatjuk. Az (n+1)-esik sorhoz tartozó kifejezés k(n+1k) alakú tagokból áll. De

k ( n + 1 k ) = k ( ( n k ) + ( n k - 1 ) ) = k ( n k ) + ( k - 1 ) ( n k - 1 ) + ( n k - 1 ) ,

ahol k(nk) és k-1(nk-1) az előző sor kifejtésében szereplő tagok. Tehát ha az összeg értéke az n-edik sorban cn, akkor

c n + 1 = k = 0 n + 1 k ( n + 1 k ) = k = 0 n + 1 k ( n k ) + k = 0 n + 1 k - 1 ( n k - 1 ) + k = 0 n + 1 ( n k - 1 ) = c n + c n + 2 n = 2 c n + 2 n .

Így ha cn=n2n-1, akkor

c n + 1 = 2 ( n 2 n - 1 ) + 2 n = n 2 n + 2 n = ( n + 1 ) 2 n = ( n + 1 ) 2 ( n + 1 ) - 1 .

13.4.0.19 A 5.4.9 b) fel. II. megoldása

(Kombinatorikai értelmezés)

Hányféleképpen választható ki egy n-fős társaságból egy csoport, vezetővel?

Kiválaszthatjuk először a csoportvezetőt ez n lehetőség majd mindenki másról eldöntjük, hogy bekerül-e a csoportba, vagy nem ez 2n-1 lehetőség, összesen tehát n2n-1.

Kiválaszthatjuk először a csoportot is ha k főt választunk, akkor arra (nk) lehetőség van és közülük választunk egy vezetőt, ez így k(nk) lehetőség. Ezt végig kell tekintenünk az összes lehetséges k-ra, így kapjuk a k=1nk(nk)=n2n-1 formulát.

13.4.0.20 A 5.4.9 b) fel. III. megoldása

(Algebra)

Mivel

k ( n k ) = k n ( n - 1 ) ( n - k + 1 ) k ( k - 1 ) 1 = n ( n - 1 ) ( n - k + 1 ) ( k - 1 ) 1 = n ( n - 1 k - 1 ) ,

így

k = 0 n k ( n k ) = n k = 0 n ( n - 1 k - 1 ) = n 2 n - 1 .

13.4.0.21 A 5.4.9 b) fel. IV. megoldása

(Generátorfüggvény)

A Binomiális tétel szerint (lásd a 5.4.2 feladatot)

( 1 + x ) n = k = 0 n ( n k ) x k .

Deriváljuk mindkét oldalt!

n ( 1 + x ) n - 1 = k = 0 n k ( n k ) x k - 1 .

Tehát x=1-re

n 2 n - 1 = k = 0 n k ( n k ) .

13.4.0.22 A 5.4.9 b) fel. V. megoldása

(Valószínűségszámítás)

Ha feldobunk n pénzérmét, akkor átlagosan hány fej lesz közte? Természetesen n2. Másrészt (nk)2n az esélye, hogy k fejez és (n-k) írást dobunk.

13.4.0.23 A 5.4.9 c) fel. eredménye

k = 0 n k ( k - 1 ) ( n k ) = n ( n - 1 ) 2 n - 2 . A 5.4.9 b) feladatra adott számos megoldás alkalmazható most is.

13.4.0.24 A 5.4.9 d) mego.

k = 0 n k 2 ( n k ) = k = 0 n ( k ( k - 1 ) + k ) ( n k ) = k = 0 n k ( k - 1 ) ( n k ) + k = 0 n k ( n k ) =

= n ( n - 1 ) 2 n - 2 + n 2 n - 1 = n ( n + 1 ) 2 n - 2 .

13.4.0.25 Megjegyzés a 5.4.9 d) feladathoz

Ez az eredmény hasznos a binomiális eloszlás szórásának kiszámításához.

A 5.4.10 feladat megoldásai

13.4.0.26 A 5.4.10 a) mego.

A 0-adik sorban az összeg 1 és a Pascal háromszöghöz hasonlóan mindig duplázódik, tehát az n-edik sor elemeinek összege 2n.

13.4.0.27 A 5.4.10 b) mego.

A 0-adik sorban az előjeles összeg 11, de a Pascal háromszöghöz hasonlóan minden olyan sorban, amelynek van megelőző sora (tehát az összes többi sorban) az összeg zérus.

13.4.0.28 A 5.4.10 c) mego.

Ha a Pascal háromszög 0-adik sorában a nullákon kívül nem egyetlen 1-es, hanem egyetlen 2-es állna, de a képzési szabály nem változna, akkor abban a háromszögben minden szám az eredeti duplája lenne. Ugyanígy képezzünk még egy-egy Pascal háromszöget egyetlen -5-ösből illetve egyetlen 4-esből kiindulva. Ezt a három Pascal háromszöget kissé toljuk el úgy, hogy a 0-adik sorban ne egymáson, hanem egymás mellett álljon a 2, a (-5) és a 4. Ha ennek a három háromszögnek az egymásra került elemeit összeadjuk és azt írjuk az adott helyre, akkor ugyanahhoz a számkitöltéshez jutunk, mintha a Mascal háromszöget képeznénk.

Így az n-esik sor k-adik eleme 2(nk)-5(nk-1)+4(nk-2) lesz.

A 5.4.11 feladat megoldásai

13.4.0.29 A 5.4.11 a) mego.

Most minden elem háromszor számít bele a következő sorba, tehát a sorösszeg háromszorozódik. Mivel a nulladik sorban 1 az összeg, így az n-edikben 3n.

13.4.0.30 A 5.4.11 b) mego.

Az előjeles összeg most állandó, értéke 1.

Minden elem eredeti előjelétől függően a következő sor előjeles összegében kétszer pozitív és egyszer negatív előjellel (tehát összességében 1-szer) vagy kétszer negatív és egyszer pozitív előjellel (tehát összességében (-1)-szer) számít. Könnyen ellenőrizhető, hogy éppen azok a számok szerepelnek a következő sor előjeles összegében +1-szer, amelyek sajt soruk előjeles összegében is +1-szer számítanak és azok lesznek a másik sorban (-1)-szer, amelyek saját sorukban is így szerepeltek.

13.4.0.31 A 5.4.11 c) mego.

A Piscal háromszög n-edik sorában az (1+x+x2)n polinom kifejtésében az x2n, x2n-1, x2, x, 1 együtthatói szerepelnek.

Ez teljes indukcióval könnyen igazolható.

Az a), b) feladatok a 3n=(1+1+1)n, 1=1n=(1-1+1)n összefüggésekkel kapcsolatosak.

A 5.4.12 feladat megoldása

A lehetőségek száma a Pascal háromszög kitöltéséhez hasonló eljárással határozható meg. A tábla bal alsó mezőjébe 1-est írunk, majd onnan indulva minden egyes mezőbe beírjuk a saját sorába, tőle jobbra található összes szám illetve a saját oszlopában alatta található összes szám összegét.

80. táblázat

A lehetőségek száma 106.

Segítség a 5.4.13 feladathoz

Segédfeladat: határozzuk meg az k=0n(-1)kk(nk) kifejezés értékét!

A 5.4.14 feladat megoldása

Lemma: Bármely mn természetes számok esetén

k = m n ( k m ) = ( n + 1 m + 1 ) ,

azaz (lásd a 140 ábrát) a Pascal háromszög bármely zokni alakú részében a száron található számok összege az ujjaknál található számmal egyezik meg.

140. ábra

a Lemma bizonyítása: Cseréljük ki az összeg első tagját, (mm)-et a vele azonos értékű (m+1m+1)-re és használjuk fel rekurzívan a (km)+(km+1)=(k+1m+1) azonosságot!

( m m ) + ( m + 1 m ) = ( m + 1 m + 1 ) + ( m + 1 m )

( m + 1 m + 1 ) + ( m + 1 m ) = ( m + 2 m + 1 ) , ( m + 2 m + 1 ) + ( m + 2 m ) = ( m + 3 m + 1 ) ,

( m + 3 m + 1 ) + ( m + 3 m ) = ( m + 4 m + 1 ) , , ( n m + 1 ) + ( n m ) = ( n + 1 m + 1 ) .

A 140 ábrán látható, ahogy a kezdeti részletösszegek értéke halad lefelé a Pascal háromszögben.

141. ábra

A 5.4.15 feladat megoldása

a) A 5.4.14 feladatban szereplő zokni-tétel szerint a 142 ábrán az egyes vonalakban található számok a sötétszürkével színezett számokkal egyenlők.

142. ábra

A 143 ábrán most újra használhatjuk a zokni-t, csak fordított helyzetben, ha még egy 1-est hozzáadunk a vizsgált összeghez:

143. ábra

Tehát a keresett összeg 56-1=55.

b) Az általános esetben a vizsgált téglalap sarkaiban az

( 0 0 ) , ( n - 1 0 ) , ( k - 1 0 ) , ( n + k - 2 n - 1 )

számok állnak, az utóbbi alatt (a kettővel lejjebbi sorban) álló szám a

( n + k n ) = ( n + k k ) ,

tehát a végeredmény (n+kn)-1.

13.5 Összetett leszámolási feladatok megoldása

Lásd még az Analízis/Különböző sorozatok fejezetet!

A 5.5.1 feladat megoldásai

13.5.0.1 A 5.5.1 a) fel. I. megoldása

Az első számjegy lehet 1, 2, 3, 4, 5, 6, ill. 7.

Ha az első szám 1-es és a második 2-es, akkor a harmadik 7-féle lehet (3, 4, 5, 6, 7, 8, 9).

Ha az első szám 1-es és a második 3-as, akkor a harmadik 6-féle lehet (4, 5, 6, 7, 8, 9).

Ha az első szám 1-es és a második 8-as, akkor a harmadik 1-féle lehet (9).

Ez eddig 7+6+5+4+3+2+1=28 lehetőség. Az összegzést a Pascal háromszögben is elvégezhetjül a Zokni-val.

Ha az első szám 2-es, akkor a fentihez hasonlóan 6+5+4+3+2+1=21 lehetőség lesz.

Ha az első szám 3-as, 4-es, 5-ös, 6-os illetve 7-es akkor rendre

5 + 4 + 3 + 2 + 1 = 15 , 4+3+2+1=10, 3+2+1=6, 2+1=3, illetve 1 lehetőség lesz. Ezek a számok mind ott vannak a Pascal-háromszögben. A Zokni szerint az összegük is ott van: 28+21+15+10+6+3+1=84.

Tehát 84 db olyan háromjegyű szám van, amelynek jegyei növekvők.

13.5.0.2 A 5.5.1 a) fel. II. megoldása

Az eredmény (93)=84. Az indoklás a 5.3.8. b) feladat megoldásában olvasható.

13.5.0.3 A 5.5.1 b) fel. I. megoldása

A keresett számokat három csoportba oszthatjuk:

1. csoport: mind a három számjegy különböző. Az ilyen számok a 16. a) feladatnak felelnek meg, számuk (93)=84.

2. csoport: két számjegy egyforma, a harmadik különböző. A dupla számot 9-féleképpen választhatjuk, ennek kiválasztása után a másik számot már csak 8-féleképpen. Ha kiválasztottuk őket, akkor a kisebbiket vagy kisebbeket rakjuk balra, a nagyobbakat vagy nagyobbat jobbra, ez már egyértelmű. Tehát 98=72 ilyen szám van.

Egy másik leszámlálási módszer: először kiválasztjuk azt a két számot, amely szerepel, erre (92)=36 lehetőség van. Utána eldöntjük, hogy ezek közül melyikből lesz kettő, ez két eset, tehát 2(92)=72 megoldás van ebben az esetben.

3. csoport: a három szám egyforma. Ilyen számból (91)=9 van.

összesen tehát 84+72+9=165 megfelelő szám van.

13.5.0.4 Megjegyzés a 5.5.1 fel. b) I. megoldásához

Az összegzést így is elvégezhetjük:

( 9 3 ) + 2 ( 9 2 ) + ( 9 1 ) = ( ( 9 3 ) + ( 9 2 ) ) + ( ( 9 2 ) + ( 9 1 ) ) =

= ( 10 3 ) + ( 10 2 ) = ( 11 3 ) = 65 .

13.5.0.5 A 5.5.1 b) fel. II. megoldása

Két halmazt vizsgálunk:

M az 1, 2, , 9 elemekből álló monoton növő sorozatok halmaza;

S az 1, 2, , 9, 10, 11 elemekből álló szigorúan monoton növő sorozatok halmaza.

Feladatunk, a b) példa, az M halmaz elemszámát kérdezi. Az a) feladat már korábban tárgyalt megoldása szerint a fenti S halmaz elemszáma (113). Alább megmutatjuk, hogy az M, S halmazok elemszáma egyenlő, tehát a b) feladat eredménye (113).

Kölcsönösen egyértelmű megfeleltetést adunk meg az M, S halmazok között. Legyen (m0,m1,m2)M és (s0,s1,s2)S egy-egy monoton növő illetve szigorúan monoton növő sorozat. Értelmezzük a

φ : M S

leképezést az

φ ( ( m 0 , m 1 , m 2 ) ) = ( m 0 , m 1 + 1 , m 2 + 2 )

képlettel. Mivel m0m1 és m1m2, így m0<m1+1 és m1+1<m2+2, tehát az (m0,m1+1,m2+2) sorozat szigorúan monoton növő. Másrészt mivel 1m0,m1,m29, így 1m0,m1+1,m2+211, tehát az (m0,m1+1,m2+2) sorozat S-ben van. A φ leképezés az M halmaz minden eleméhez hozzárendeli az S halmaz egy-egy elemét.

Könnyű meggondolni, hogy ha (s0,s1,s2) az S halmaz tetszőleges eleme, akkor (s0,s1-1,s2-2) az M halmazban van és (s0,s1,s2) ennek és csakis ennek az M-beli elemnek a φ-nél származó képe. A φ leképezés tehát kölcsönösen egyértelmű a két halmaz között.

Az M, S halmazok elemszáma egyenlő, ezzel a feladatot megoldottuk.

13.5.0.6 A 5.5.1 b) fel. III. megoldása

A számjegyek most kilencfélék lehetnek: 1, 2, 3, , 9. Ezek közül kell hármat kiválasztanunk, de lehet ugyanazt többször. A sorrend viszont nem számít, a három kiválasztott számot egyféleképpen rakhatjuk olyan sorrendbe, amelyet a feladat kér. A megoldások száma tehát 9 elem 3-adosztályú ismétléses kombinációinak száma, ami (113)=65.

A 5.5.2 feladat megoldása

A lottószámok között pontosan akkor nincs két szomszédos, hogy ha növekvő sorrendjükben rendre 0-t, 1-et, 2-t, 3-at ill. 4-et kivonva belőlük öt különböző 1 és 86 közti egész számot kapunk. Így a valószínűség: (865)(905).

A 5.5.3 feladat megoldásai

13.5.0.7 A 5.5.3 b) mego.

Cserepartneremnek 9-féle ajándékból választhatok. Bármelyiket is választom, a másik diák számára is 9 lehetőségem van, és ugyanúgy a tanárnak is. Ez összesen 999=93 eset, mind különböző.

13.5.0.8 A 5.5.3 a) mego.

Érdemesebb először a 5.5.3 b) feladatot megoldani. Az ott kapott 93 eset, most nem mind különböző. A (Rubik kocka, Unikum, téli szalámi), (Unikum, Rubik kocka, téli szalámi) hármasok a b) feladatrészben különbözőek, az a)-ban azonosak. Azt gondolhatnánk, hogy 3 elem lehetséges sorrendjeinek permutációinak számával kell osztani a b)-beli eredményt, de 93 nem is osztható ezzel. A gond ott van, hogy az a)-beli (Unikum, Unikum, Rubik-kocka) hármas a b)-ben nem 6-szor, hanem csak 3-szor fordul elő, míg az (Unikum, Unikum, Unikum) hármas csak egyszer. Másként kell gondolkodni.

Feleltessük meg a 9 ajándéknak az 1, 2, 3, , 9 számokat! A kiválasztott 3 ajándék, azaz 3 szám, sorrendje nem számít, rakjuk azokat növekvő sorrendbe (egyenlőség megengedett)! Így a feladatot visszavezettük a 5.5.1 b) feladatra. A megoldások száma (113).

A 5.5.4 feladat megoldásai

13.5.0.9 A 5.5.4 a) mego.

Feleltessük meg az n-féle dolognak az 1, 2, , n számokat! A kiválasztott k darab számot, amelyek közül bármelyik többször is szerepelhet, állítsuk növekvő sorrendbe. Így egy monoton növő sorozatot kapunk. Adjunk most a növekedési sorban i-edik számhoz (i+1)-et! Így egy szigorúan monoton számsorozatot kapunk, amelynek elemei az {1,2,3,,n+k-1} halmazból kerülnek ki. Ennek a halmaznak a k-elemű részhalmazai kölcsönösen egyértelmű megfeleltetésben állnak ugyanazen halmaz k-tagú szigorúan monoton sorozataival, ezek pedig az {1,2,,n} számok k-tagú monoton sorozataival, tehát ezek száma is (n+k-1k).

13.5.0.10 A 5.5.4 b) fel. eredménye

n k .

A 5.5.5 feladat megoldásai

13.5.0.11 A 5.5.5 fel. I. megoldása

Az n-edik átló olyan szorzatokat tartalmaz, amelyben a két tényező összege (n+1):

a n = k = 1 n k ( n + 1 - k ) = k = 1 n k ( n + 1 ) - k 2 = = ( n + 1 ) k = 1 n k - k = 1 n k 2 = ( n + 1 ) n ( n + 1 ) 2 - n ( n + 1 ) ( 2 n + 1 ) 6 ,

ahol felhasználtuk az első n pozitív egész összegére, illetve az első n pozitív négyzetszám összegére vonatkozó jól ismert képleteket (lásd az órán később). Egyszerűbb alakot kapunk ha a két tényezőből kiemeljük az n(n+1) szorzatot és közös nevezőre hozunk:

a n = n ( n + 1 ) ( 3 ( n + 1 ) 6 - ( 2 n + 1 ) 6 ) = n ( n + 1 ) ( n + 2 ) 6 .

13.5.0.12 A 5.5.5 fel. II. megoldása

Ezt a megoldást a Zokni-ra (lásd a 5.4.14 feladatot) építjük

Haladjunk a szorzótáblában átlóról átlóra (lásd a 144 ábrát)!

144. ábra

A második átlóban a számok rendre 1-gyel illetve 2-vel nagyobbak a fölöttük az előző átlóban álló számnál. A harmadik átlóban rendre 1, 2 és 3 a differencia stb. A további gondolatmenet leolvasható az alábbi elrendezésből, amelyben az összegzések a zoknin alapulnak.

a 1 = 1 = ( 1 1 ) = ( 2 2 ) = ( 3 3 ) a 2 = a 1 + ( 1 + 2 ) = a 1 + ( ( 1 1 ) + ( 2 1 ) ) = ( 3 3 ) + ( 3 2 ) = ( 4 3 ) a 3 = a 2 + ( 1 + 2 + 3 ) = a 2 + ( ( 1 1 ) + ( 2 1 ) + ( 3 1 ) ) = ( 4 3 ) + ( 4 2 ) = ( 5 3 ) a n = a n - 1 + ( 1 + 2 + + n ) = a n - 1 + ( ( 1 1 ) + ( 2 1 ) + + ( n 1 ) ) = ( n + 1 3 ) + ( n + 1 2 ) = ( n + 2 3 )

13.5.0.13 A 5.5.5 fel. III. megoldása

Kombinatorikai értelmezés

Az előző megoldásokban kapott végeredménynek, az (n+23)-nak önálló jelentése van: azt mondja meg hányféleképpen választható ki (n+2) objektumból három. Szeretnénk megérteni miképpen kapcsolódik ez a jelentés a feladathoz.

Válasszunk ki az 1, 2, , (n+2) számokból hármat úgy, hogy először közülük a nagyságrendi sorrendben középsőt választjuk ki!

A középső szám értéke 2 és n+1 közötti egész szám lehet. Ha ez a középső érték (k+1), ahol 1kn, akkor a legkisebb szám k-féle, a legnagyobb szám pedig (n+2)-(k+1)=n+1-k-féle lehet, tehát k(n+1-k)-féleképpen lehet a k szám a középső. Ez azt jelenti, hogy a szorzótábla n-edik átlójában (lásd az I. megoldásban is használt (171) képletet) álló számok azt fejezik ki, hogy hányféleképpen választhatunk ki az első (n+2) pozitív egészből hármat, ha a középső rögzített. Az átlóban álló számok összege pedig kiadja azt összes lehetőséget, ahányféleképpen három szám kiválasztható (n+2)-ből.

A 5.5.6 feladat megoldása

Minden köri pontnégyesből egyféleképpen választható ki két pár melyek összekötő szakasza metsző, így a megoldások száma (n4).

13.6 Dimenzió a feladatok megoldásai

A 5.6.2 feladat megoldásai

13.6.0.1 Segítség a 5.6.2 feladathoz

Rajzoljunk táblát a játékhoz! Minden osztó legyen egy mező. Az a osztó mezője kerüljön a b osztó mezője fölé, ha a a b többszöröse. Tehát legalulra az 1 kerüljön. Közvetlen föléje mik? Azok fölé?

13.6.0.2 A 5.6.2 feladat megoldása

A 10 és a 16 osztóhálója a 145 ábrán, a 24 és a 36 osztóhálója a 146, a 30 osztóhálója a 147 ábrán, végül a 2010 osztóhálója a 148 ábrán látható.

145. ábra. A 10 és a 16 osztóhálója

146. ábra. A 24 és a 36 osztóhálója

147. ábra. A 30 osztóhálója

148. ábra. A 2010 osztóhálója

A 5.6.3 feladat megoldása

13.6.0.3 Segítség a 5.6.3 feladathoz

Az n dimenziós kocka csúcsai megfeleltethetők az n hosszú 0-1 sorozatoknak.

A kocka egy éle a csúcsok egy két elemből álló halmaza. Egy élt meghatározó két csúcs két olyan sorozatnak felel meg, amelyek csak egyetlen helyen térnek el egymástól.

A kocka egy lapja (2-dim lapja) a csúcsok egy négy elemből álló részhalmaza. Egy lapot meghatározó négy csúcs négy olyan sorozatnak felel meg, amelyek 2 helyet kivéve minden más helyen megegyeznek egymással, azon a két helyen pedig felveszik a négy lehetséges értékpárt.

A kocka egy 3-dim lapja

13.6.0.4 A 5.6.3 feladat megoldása

Az eredmények a 3 táblázatban olvashatók.

3. táblázat. Az $n$-dimenziós kocka $k$-dimenziós lapjainak száma

Az n-dimenziós kocka k-dimenziós lapjainak száma (nk)2n-k, hiszen ki kell választanunk azt a k helyet (koordinátát), amelyet szabadon hagyunk és rögzítenünk kell a maradék (n-k) koordináta értékét (lásd még a Segítség a 5.6.3 feladathoz részben leírtakat).

A 5.6.4 feladat megoldása

a) Legfeljebb 3 osztó választható ki így. Jó pld. a 2, 3 és az 5. Az {1,2,6,30}, {3,15}, {5,10} halmazok mindegyikéből legfeljebb egy választható ki, tehát 3-nál több semmiképp.

b)

( 4 2 ) = 6 db, a két prím szorzatából álló osztók. Ennél több nem lehet, az alábbi hat osztólánc tartalmazza az összes osztót:

( 1 , 2 , 2 3 , 2 3 67 , 2010 ) , ( 1 , 2 , 2 5 , 2 5 3 , 2010 ) , ( 1 , 3 , 3 5 , 3 5 67 , 2010 )

( 1 , 5 , 5 67 , 2 5 67 , 2010 ) , ( 1 , 67 , 2 67 , 2 5 67 , 2010 ) , ( 1 , 67 , 3 67 , 3 5 67 , 2010 ) .

A 5.6.5 feladat megoldása

Készítsük el a 60 osztóhálóját és számítsuk ki, hogy az 1-nek megfelelő csúcsból hányféle lépéssorozattal lehet eljutni a 60-hoz, ha mindig egy többszörösre kell lépni (tehát pld lehet egyből a 60-ra is)! Töltsük ki az osztóháló csúcsait számokkal a Pascal háromszöghöz hasonló módon, de kissé másképp, a 5.4.12 feladatban már látott módon: írjunk 1-est az 1-es osztónak megfelelő csúcsra és minden más osztónak megfelelő csúcsra írjuk az ő osztóihoz írt számok összegét (lásd a 149 ábrát)!

149. ábra. A 60 osztóhálója és Pascal-szerű kitöltése

13.7 Gráfok feladatok megoldása

A 5.7.1 feladat megoldása

C. Frank kilenc választ kapott. Bárki az asztalnál legfeljebb nyolcat mondhatott (magát és párját mindenki ismeri). Ezért az elhangzott számok; 0,1,2,3,4,5,6,7,8.

Könnyű látni, hogy aki 8-at mondott, annak a házastársa 0-t, aki 7-et, annak párja 1-et és így tovább. Mivel a 4 szám nem hangzott el kétszer, és mivel van 4,4 pár, ezért ez a C. Frank házaspár lehetett, így noha C. Frank nem nyilatkozott, R. Korszakov kitalálta, hogy ő négy embert nem ismer.

A 5.7.2 feladat megoldásai

13.7.0.1 A 5.7.2 fel. I. megoldása

Buszgráf-nak nevezzük azt a gráfot, amelynek csúcsai Bergengócia városai, és két csúcs akkor van összekötve, aha nekik megfelelő két város között van közvetlen buszjárat.

Ha buszgráf összefüggő, akkor készen vagyunk, busszal bármelyik városból bármelyik másikba el lehet jutni.

Ha a buszgráf nem összefüggő, akkor a csúcsok felbonthatók két nemüres részhalmaz A, és B diszjunkt uniójára úgy, hogy A-beli csúcs és B-beli közt nincs él. Ez azt jelenti, hogy a két csoport közti élek mind a repülőgráf-ban vannak. A repülőgráf tehát összefüggő, mert ezeken az éleken bármelyik csúcsból bármelyik másikba eljuthatunk legfeljebb kettő hosszú úton.

13.7.0.2 A 5.7.2 fel. II. megoldása

A városok számára vonatkozó teljes indukcióval bizonyítunk. Az állítás nyilván igaz 1 illetve 2 város esetén. Tegyük fel, hogy 2<k város esetén is igaz, bizonyítsuk (k+1) városra.

Legyen az egyik város Bergóc. A többi város ez összesen csak k város között megoldható a közlekedés az egyik járművel, pld busszal.

Ha Bergócból indul ki buszjárat, akkor az bevonja Bergócot a többi város buszforgalmába, így busszal innen is el lehet jutni mindenhová, a busz megoldja a közlekedést önmagában.

Ha Bergócból nem indul buszjárat, akkor innen mindenhová megy repülőjárat, így repülővel bárhonnan bárhová el lehet jutni (Bergócon keresztül).

A 5.7.3 feladat megoldása

Ha a városok száma legalább három, akkor ellenpélda adható. Az egyik város legyen Bergóc. Az összes többi város között menjen buszjárat, míg Bergócból csak vonat és repülőjáratok induljanak, néhány (legalább 1) városhoz vonat, néhány (legalább 1) városhoz pedig repülő. Ebben az esetben egyik közlekedési eszköz sem tudja biztosítani bármely két város között az elérhetőséget.

Háromnál több város esetén olyan példa is adható, amelyben minden városból mind a háromféle közlekedési társaság indít járatokat. Pld négy város, A, B, C, D esetén egy ellenpélda: AB és CD a buszvonalak, AC és BD a vonatok és AD és BC a repülők. Több csúcs esetén négy csoportra oszthatjuk a csúcsokat és köztük ugyanezt a beosztást alkalmazzuk, a csoportokon belül pedig tetszőlegeset.

A 5.7.4 feladat megoldásai

13.7.0.3 A 5.7.4 a) mego.

Igaz. Tekintsünk egy tetszőleges járatot és szüntessük meg, ha része egy körutazásnak. Haladjunk tovább, egyesével menjünk így végig az éleken. Minden egyes lépésben igaz marad, hogy bárhonnan bárhová el lehet jutni, mert a kihagyott járat pótolható a körút többi járatával. Az eljárás végén csak olyan járatok maradnak meg, amelyek nem részei körútnak, de továbbra is el lehet jutni mindenhonnan mindenhová.

13.7.0.4 A 5.7.4 b) mego.

Nem. Ha például egy repülő körbemegy az összes városon. mindegyiknél leszáll és a végén a visszajut oda, ahol indult, akkor biztosított a közlekedés bármelyik két város között, de ehhez nem hagyható ki a láncból egyetlen járat sem.

A 5.7.5 feladat megoldása

A feladatot úgy is megfogalmazhatjuk, hogy egy n pontú teljes, irányított gráfban van olyan pont, melyből bármelyik másik pont legfeljebb kettő hosszú írányított út mentén elérhető.

Kézenfekvő azt gondolni, hogy a legeredményesebb versenyző lesz a megfelelő játékos. Tegyük tehát fel, hogy az X játékos nyerte a legtöbb csörtét. Ha nincs olyan A játékos, aki X-et legyőzte, készen vagyunk. Tegyük tehát fel, hogy egy A játékos legyőzte X-et. Ekkor azok közül, akiket legyőzött X kell lenni olyannak, aki A-t legyőzte. Ellenkező esetben ezek mindegyikét legyőzte volna A,+ még X-et, ami összesen több, mint amennyit X legyőzött. Ez ellentmond annak, hogy X győzte le a legtöbb játékost.

A 5.7.6 feladat megoldása

A feladat ekvivalens avval, hogy ha egy 6 pontú teljes gráf éleit színezzük két színnel, akkor lesz egyszínű háromszög (6 tudós a 6 pont, akivel levelez, avval pirossal kötjük össze, akivel nem, avval kékkel kötjük össze).

Egy kiszemelt tudósnak megfeleltetett pontból biztosan kiindul 3 egyszínű él (mondjuk piros). Ha ezen élek végpontjai között van 2, amely piros éllel van összekötve, akkor kész vagyunk. Ha nincs, akkor ezek közül bármelyik kettő kékkel van összekötve, ami egy kék háromszöget ad.

13.8 Kombinatorikus geometria feladatok megoldása

A 5.8.1 feladat megoldása

a) Tegyük fel, hogy nem igaz az állítás! Ha az 1 piros akkor 2 kék (1+1=2 megoldás lenne), hasonlóan a 4 ezért piros (2+2=4), 5 kék (1+4=5). Nem lehet a 3 piros (1+3=4) de kék se (2+3=5). Ez az ellentmondás igazolja az állítást.

b) Az 1 és 4 piros, 2,3 kék.

A 5.8.2 feladat megoldása

Ha X,Y,Z egy a oldalú szabályos háromszög, akkor X,Y,Z közül kettőnek azonos a színe.

A 5.8.3 feladat megoldása

Tekintsük a 150. ábrán látható Motzkin gráfot, amelyben ADE, BFG, CDE, CFG egységoldalú szabályos háromszögek és az AB szakasz hossza is egységnyi. Ha ebben az ADE és a CDE háromszög csúcsai között nincsenek azonos színűek, akkor A és C színe megegyezik. Ha a BFG és a CFG háromszög csúcsai között sincsenek azonos színűek, akkor B és C színe is megegyezik. Ekkor tehát A és B színe is megegyezik, melyek távolsága egységnyi.

150. ábra

A 5.8.4 feladat megoldása

Parkettázzuk ki a síkot szabályos hatszögekkel, és színezzük egy hatszöget az 1-es színnel (a hatszög belsejét és három egymásutáni élét, a csatlakozó élek kezdőpontját, a harmadikét már nem) a körötte levő hatszögeket ciklikusan.

A 5.8.5 feladat megoldása

Vegyünk egy a oldalú szabályos háromszöget. Ezt fogjuk egy olyan felületre ráfektetni amelynek pontjai egyszínűek, ezzel bizonyítva az állításunk.

Mint már láttuk, találtunk két pontot, P-t és Q-t, amelyek egyszínűek (piros), és távolságuk éppen a. Az O szakaszfelező pontjukból, mint középpontból a PQ síkjára meröleges síkon húzzunk egy 3a/2 sugarú kört. Ennek pontjai P-vel és Q-val szabályos háromszöget alkotnak, ha van piros pontja, készen vagyunk. Legyen e kör minden pontja kék. Tekintsünk e körön tetszőleges két pontot, T-t és V-t, amelyek egyszínűek (kék), és távolságuk éppen a.TV síkjára meröleges síkon húzzunk megint egy 3a/2 sugarú kört a szakaszfelező pontjukból, mint középpontból. Mint láttuk ennek az ellenkező színűnek kell lennie (piros), különben készen vagyunk. A T és V pontok tetszölgesen voltak választva a kék körön, tehát bárhol felvéve piros köröket kapunk, melyek egy tórusz felületét súrolják. E felület piros.

Rövid számolással igazolható, erre fektetve egy a oldalú szabályos háromszöget, annak mindhárom csúcsa e tórusz felületén van.

A 5.8.6 feladat megoldása

A A 5.8.3 fel. megoldásában látható Motzkin gráf ezt a feladatot is megoldja.

A 5.8.7 feladat megoldása

Vegyünk egy egység oldalú szabályos háromszöget, és toljuk el két példányban úgy, hogy a háromszögünk megfelelő csúcsai egy a oldalú szabályos háromszöget alkossanak. Így van egy 9 pontú gráfunk. Az egység oldalú szabályos háromszögekben csak egy pont lehet legfeljebb piros, tehát legalább két kék pont van. Ezért a három a oldalú szabályos háromszögek közül az egyikben minden pont kék.

A 5.8.8 feladat megoldása

Tekintsük az öt pont konvex burkát. Ha ez öt-, vagy négyszög, akkor készen vagyunk. Ha háromszög, akkor belsejében tartalmaz két pontot. Az ezeket összekötő egyenes egyik oldalán két pont van (nincs három közülük egy egyenesen). A két beslő pont és e két pont egy konvex négyszöget alkot.

A 5.8.9 feladat megoldása

Vegyünk ki közülük egy tetszőleges pontot, legyen ez O, és tegyük fel, hogy ettől a ponttól a többi pont legfeljebb 699 különböző távolságot határoz meg. Ezzel a 699 távolsággal, mint sugárral O körül húzzunk köröket. Nyilván nincs olyan pont, amelyik valamelyik körön ne nyugodna. (Ez egy újabb távolságot jelent ellenkezó esetben). Ekkor a 699 kör között van olyan, amelyik legalább 1,000,000/699>1430 pontot tartalmaz. E körön kijelölve egy pontot és az e körön levő pontokkal összekötve legalább 1430/2>700 különböző távolságot kapunk, ugyanis egy távolság legfeljebb kétszer fordulhat elő.

A 5.8.10 feladat megoldásai

13.8.0.1 A 5.8.10 a) mego.

Tegyük fel, hogy van egy olyan színezés, melyben nincs három különböző, melyek azonos színűek és egy számtani sorozat alkotnának. Lényegében a következő két esetet kell diszkutálni:

1. eset: 1 és 9 azonos színű (piros) az 5-ös kék.

2. eset 1 és 5 azonos színű (piros) az 9-es kék.

Mindkét esetben a további pontok színei egyértelműek, és ellentmondásra vezetnek.

13.8.0.2 A 5.8.10 b) mego.

1 , 2 , 5 , 6 pontok színe kék, 3,4,7,8 piros.