Ugrás a tartalomhoz

Elemi matematika feladatgyűjtemény

Hraskó András (2013)

ELTE-TTK

5 Kombinatorika

5 Kombinatorika

5.0.0.1 Ajánló

A témához kapcsolódó alapvető művek

Róka Sándor 2000 feladat az elemi matematika köréből[];

Matkönyv[], Dobos Sándor: Kombinatorika 7-8;

http://matek.fazekas.hu/mathdisplay/cache/pdf/volume_k_i.pdf ;

N. J. Vilenkin Kombinatorika"[];

Lovász László, Pelikán József, Vesztergombi Katalin Kombinatorika"[];

Lovász László, Pelikán József, Vesztergombi Katalin Diszkrét matematika"[],

Matkönyv[], Surányi László: Kombinatorika 9-10;

http://matek.fazekas.hu/mathdisplay/cache/pdf/volume_k_ii.pdf ;

Elekes György Kombinatorika feladatok"[],

http://matek.fazekas.hu/portal/tanitasianyagok/Elekes_Gyorgy/elekes_kombfel.pdf ;

Hajnal Péter Elemi kombinatorikai feladatok"[];

Andrásfai Béla Gráfelmélet"[];

Lovász László Kombinatorikai problémák és feladatok"[],

http://www.tankonyvtar.hu/hu/tartalom/tkt/kombinatorikai-problemak/ .

Friedl Katalin, Recski András, Simonyi Gábor Gráfelméleti feladatok"[],

Open Problems in Combinatorics,

http://www.combinatorics.net/problems/ .

5.1 A szita módszer

5.1.1. Feladat A 45 tagú Majmok Tudományos Akadémiája ülést tartott. Ezen az ülésen három kérdést tűztek napirendre, mely fölött szavazással óhajtottak dönteni. A kérdések a következők voltak:

1. Okosabb-e a majom, mint az ember?

2. Szebb-e a majom, mint az ember?

3. Igaz-e, hogy az ember a majom őse?

a) A szavazás után kiderült, hogy az 1. és 3. kérdésre egyaránt 23-23 igen szavazat érkezett, míg a második kérdésre csak 17.

b) Az 1. kérdésre igennel válaszolók közül 13-an a 2.,12-en pedig a 3. kérdésre feleltek nemmel.

c) Igent mondott a 2. és 3. kérdésre 6 akadémikus, de közülük ketten az első kérdésre nemmel szavaztak.

Hányan szavaztak mind a három kérdésre nemmel?

5.1.2. Feladat(Mego.)

Egy matematikaversenyen három feladatot tűztek ki. 56 versenyző oldott meg legalább egy feladatot. 2 versenyző volt, aki mindhárom feladatot megoldotta. A harmadik feladatot megoldók közül 10-zel többen oldották meg a másodikat, mint az elsőt. Az elsőt és a másodikat is megoldók 10-zel többen voltak, mint akik csak a harmadikat oldották meg. Aki megoldotta az elsőt és a harmadikat is, az a másodikat is megoldotta. Akik csak az első vagy csak a második feladatot oldották meg, összesen 14-en voltak. Hány versenyző oldotta meg a harmadik feladatot?

5.1.3. FeladatLovagok és lókötők szigete.(Mego.)

Egy szigeten jártunk, ahol lovagok és lókötők élnek. A lovagok mindig igazat mondanak, a lókötők mindig hazudnak. A szigetnek 100 lakosa és három felekezete van: a Napimádók, a Holdimádók és a Földimádók. Minden lakos pontosan egy felekezethez tartozik. Egy felmérés alkalmával minden lakosnak meg kellett válaszolnia a következő három kérdés mindegyikét: Te Napimádó vagy?, Te Holdimádó vagy?, Te Földimádó vagy?. Az első kérdésre 60, a másodikra 40, a harmadikra 30 igen válasz érkezett. Hány lovag és hány lókötő él a szigeten?

5.1.4. Feladat(I. mego., II. mego., III. mego., IV. mego., V. mego., VI. mego., VII. mego., VIII. mego., IX. mego.)

Egy matematikaversenyen a versenyzők 85%-a megoldotta az első feladatot. A második feladatot 80%-uk oldotta meg. A harmadik feladatot 75%-uk oldotta meg.

Legalább hányan oldhatták meg mindhárom feladatot?

5.1.5. Feladat A finnek nemzeti zászlója: fehér téglalap alapon fekvő kék kereszt (lásd a 18 ábrát). A kék kereszt hosszabbik sávjának a területe 8800 cm2, a rövidebbik sáv területe pedig 5400 cm2. Mekkora a zászló területe, ha a kék kereszt 12600 cm2 területű?

18. ábra

5.1.6. Feladat A 32-fős 12.c osztály osztályfőnökének az osztály nyelvtanulásával kapcsolatos statisztikát kell készítenie. A statisztikai kérdőív a következő kérdésekből állt:

1. Hányan járnak az osztályba?

2. Hány tanulónak van középfokú nyelvvizsgája angol nyelvből?

3. Hány tanulónak van középfokú nyelvvizsgája francia nyelvből?

4. Hány tanulónak van középfokú nyelvvizsgája német nyelvből?

5. Hány tanulónak van középfokú nyelvvizsgája a fenti három nyelv mindegyikéből?

6. Hány tanulónak van középfokú nyelvvizsgája a fenti három nyelv közül pontosan kettőből?

7. Hány tanulónak van középfokú nyelvvizsgája a fenti három nyelv közül pontosan egyből?

8. Hány tanulónak nincs középfokú nyelvvizsgája a fenti három nyelv egyikéből sem?

Az utolsó két kérdés az osztályfőnök szerint felesleges.

a) Határozzuk meg a rájuk adandó választ, ha az első hat kérdésre adott válasz rendre 32, 20, 15, 6, 2, 9!

b) Jelölje az i-edik kérdésre adott választ xi. Fejezzük ki x7 és x8 értékét x1, x2, x3, x4, x5, és x6 segítségével!

5.1.7. FeladatDobos Sándor feladata

a) Helyezzünk 15 piros pontot egy hatszög oldalaira úgy, hogy minden oldalon ugyanannyi piros pont legyen! (A hatszög csúcsára is kerülhet piros pont, de egy pontra csak egy piros pontot tehetünk.)

b) Oldjuk meg a feladatot 16 ponttal!

c) 2003 ponttal!

d) El lehet-e helyezni 15 pontot egy hétszög oldalaira a fenti szabálynak megfelelően?

e) Helyezzünk 10 piros és 14 kék pontot egy hatszög oldalaira úgy, hogy minden oldalon ugyanannyi piros pont legyen, mint kék!

5.1.8. Feladat Írjuk be az 1, 2, 3, 4, 5, 6, 7, 8, 9 számokat a 19 ábrán látható kilenc karikába úgy, hogy a háromszög oldalain található négy-négy szám összege egyenlő legyen

a) 20-szal; b) egymással és a lehető legnagyobb legyen.

19. ábra

5.1.9. Feladat Írjuk be az 1, 2, 3, ..., 16 számokat a 20 ábrán látható (egy tetraéder csúcsaiba és éleire helyezett) tizenhat gömbbe úgy, hogy a tetraéder (háromszög alapú gúla) élein található négy-négy szám összege mindenütt 30 legyen!

20. ábra

5.1.10. Feladat Egy 3×3-as táblázatban elhelyeztünk 9 számot. Egy ilyen táblázatot bűvös négyzetnek nevezünk, ha a számok összege minden sorban, minden oszlopban és mindkét főátlóban ugyanaz az érték. Igaz-e, hogy bármely bűvös négyzetben a középen található szám a bűvös négyzet 9 számának átlaga?

5.1.11. Feladat Helyezzünk el egy 3×3-as táblázatban 9 különböző pozitív egész számot úgy, hogy a számok szorzata minden sorban, minden oszlopban és mindkét főátlóban ugyanaz az érték legyen!

5.1.12. Feladat(I. mego., II. mego., III. mego.)

Négy kör úgy helyezkedik el, ahogyan az a 21 ábrán látható. A körökön belül létrejött 10 tartományba úgy kell beírni a 0, 1, 9 számokat, hogy az egyes körökön belüli számok összege egyenlő legyen egymással. Legfeljebb mekkora lehet ez az összeg?

21. ábra

5.1.13. Feladat(Kvant)

A 22 ábra négyzeteibe írjunk egy-egy számot úgy, hogy minden három négyzetből álló téglalapban 1 legyen a számok összege és az összes szám összege is 1 legyen!

22. ábra

5.1.14. Feladat Egy füzetlap 33×41 kis négyzetből áll. Be lehet-e írni a számokat 1-től 3341=1353-ig a négyzetekbe úgy, hogy minden 2×2-es négyzetben a számok összege ugyanannyi legyen?

5.1.15. Feladat Hogyan kell a 23 hiányzó helyeire beírni 3-tól 9-ig a természetes számokat úgy, hogy a számok összege minden sugár és kör mentén ugyanaz legyen?

23. ábra

5.1.16. Feladat Egy 4×4-es táblázatban 16 szám volt. Az alábbi táblázatot úgy kaptuk az eredetiből, hogy egy lépésben egyszerre minden számot helyettesítettünk a sorában és oszlopában álló másik hat szám számtani közepével.

6. táblázat

Hogyan volt kitöltve az eredeti táblázat?

5.1.17. Feladat Egy 3×3-as táblázatban elhelyeztünk 9 számot. Egy ilyen táblázatot bűvös négyzetnek nevezünk, ha a számok összege minden sorban, minden oszlopban ás mindkét főátlóban ugyanaz az érték. Igaz-e, hogy a bűvös négyzet fölső sorában álló számok négyzetének összege mindig megegyezik az alsó sorban álló számok négyzetösszegével?

5.1.18. Feladat Adjunk meg 25 nem feltétlenül különböző számot úgy, hogy alkalmas sorrendben írva azokat, bármely három szomszédos szám összege pozitív, ugyanakkor a 25 szám összege negatív legyen!

5.1.19. Feladat Egy 4×4-es táblázat 16 mezőjébe egy-egy egész számot írtak. Tudjuk, hogy a táblázat mindegyik 3×3-as részében (tehát mind a négyben) a 9 szám összege negatív. Következik-e ebből, hogy a 4×4-es táblázatban található 16 szám összege is negatív?

5.1.20. Feladat(I. mego., II. mego.)

Egy sorozat bármely 7 szomszédos tagját összeadva negatív, bármely 11 szomszédosat összeadva pedig pozitív számot kapunk. Legfeljebb hány tagja lehet a sorozatnak?

5.1.0.1 Ajánló

I. M. Jaglom A zsák meg a foltjai"[];

Elekes György Kombinatorika feladatok[], 1.7. fejezet,

http://matek.fazekas.hu/portal/tanitasianyagok/Elekes_Gyorgy/elekes_kombfel.pdf .

Lovász László Kombinatorikai problémák és feladatok"[], 2. fejezet,

http://www.tankonyvtar.hu/hu/tartalom/tkt/kombinatorikai-problemak/ch02.html ;

5.2 Feladatok a sakktáblán

5.2.1. Feladat(a) mego., b) I. mego., b) II. mego.)

Bejárható-e egy 5×5-ös sakktábla lóval,

a) ha nem kell ugyanott befejeznünk, ahonnan indultunk?

b) ha ugyanott kell befejeznünk, ahonnan indultunk?

Mindkét esetben minden mezőre pontosan egyszer kell lépnünk (kivéve a b) feladatrészben az egymással megegyező kezdő és befejező mezőt).

5.2.2. Feladat(Mego.)

Egy sakktábla két sarokmezőjét levágjuk. Lefedhető-e a sakktábla 1×2-es (éppen két sakktáblamező méretű) dominókkal?

5.2.3. Feladat(Elő. megj.,Mego.)

Kockás lapon 40 kis négyzetet kiszíneztünk. Igaz-e, hogy ekkor biztosan kiválasztható közülük 10, amelyeknek nincs közös pontja? (Még közös csúcs se lehet!)

5.2.4. Feladat(a) mego., b) mego., c) mego., d) mego., e) mego.)

Egy 8×8-as sakktáblán maximum hány

a) bástyát; b) futót; c) lovat; d) királyt; e)* királynőt;

lehet elhelyezni, úgy, hogy ne üssék egymást?

5.2.5. Feladat(A legkisebb hegycsúcs) (a) mego., b) eredm)

Helyezzünk el minél kevesebb

a) bástyát b) királynőt

a sakktáblán úgy, hogy ne üssék egymást, de további bástya ill. királynő már ne legyen elhelyezhető úgy, hogy semelyik kettő se üsse egymást!

5.2.6. Feladat(Mego.)

Hányféleképpen lehet egy 8×8-as sakktáblára 3 bástyát feltenni úgy, hogy semelyik kettő ne legyen egy sorban vagy egy oszlopban, feltéve hogy

a) mind egyformák;

b) mind különbözőek;

c) kettő egyforma és egy másmilyen

5.2.0.1 Ajánló

Jevgenyij Jakovlevics Gik Sakk és matematika[];

Róka Sándor 2000 feladat az elemi matematika köréből[];

A Matkönyv[] megfelelő fejezetei: http://matek.fazekas.hu/mathdisplay/cache/pdf/volume_k_i.pdf

5.3 Egyszerűbb leszámolási feladatok

5.3.1. Feladat

Hányféleképpen olvasható ki a PASCAL szó a 24 ábrán látható elrendezésekben?

24. ábra

5.3.2. Feladat

a) Hány ötbetűs szó (karaktersorozat) állítható össze három B és két A betű felhsználásával? (Tehát azoknak a szavaknak a számát keressük, amelyekben pontosan három B és pontosan két A betű van és más betű nincs. Pld: ABBAB.)

b) Hány ötbetűs szó (karaktersorozat) állítható össze B és A betűk felhsználásával? (Tehát azoknak az ötbetűs szavaknak a számát keressük, amelyekben csak A és B betű van, de az is lehet, hogy csak az egyikük szerepel. Pld: BBBAB.)

5.3.3. Feladat

a) Hány két elemből álló részhalmaza van egy ötelemű halmaznak?

b) És hány három elemből álló részhalmaza van?

c) Összesen hány részhalmaza van egy ötelemű halmaznak?

5.3.4. Feladat Bontsuk fel a zárójelet és hajtsunk végre összevonást az alábbi kifejezésekben!

( a + b ) 2 , ( a + b ) 3 , ( a + b ) 4 , ( a + b ) 5 .

5.3.5. Feladat(Mego.)

20 golyóból véletlenszerűen kiválasztok valamennyit (lehet, hogy mind a húszat, és lehet, hogy egyet sem). Hányféle különböző választás lehetséges, ha

a) minden golyó más színű;

b) minden golyó egyforma?

5.3.6. Feladat(Mego.)

A 8×8-as sakktáblán hány

a) rácsnégyzetet

b) rácstéglalapot találhatunk?

5.3.7. Feladat(a) mego., b) mego., c) mego., d) mego.)

Az 1, 2, 3, 4, 5 és 6 számjegyekből hatjegyű számokat készítünk.

Hány 2-vel, 3-mal, 4-gyel, 5-tel, 6-tal osztható szám van közöttük, ha

a) minden számjegyet csak egyszer használhatunk fel;

b) egy számjegyet többször is felhasználhatunk?

Mennyi az így készíthető 3-mal osztható hatjegyű számok összege a fenti

c) a) esetben? d) a fenti b) esetben?

5.3.8. Feladat(a) mego., b) mego., c) mego.)

A négyjegyű számok között melyikből van több,

a) amelyekben szerepel a 7-es számjegy, vagy amelyekben nem?

b) amelyekben a számjegyek szigorúan növekvő sorrendben állnak, vagy amelyekben nem?

c) amelyekben nincsenek egyforma számjegyek, vagy amelyekben vannak?

5.3.9. Feladat(Mego.)

1-10 hosszúságú színes rudakkal szőnyegezünk (ugyanazt a hosszúságot rakjuk ki többféleképpen rövidebb rudakból, úgy, hogy a sorrend is számít).

a) Hányféleképpen tudjuk a 10-et kirakni?

b) Hányféleképpen tudjuk a 10-et pontosan 2 darab rúdból (pontosan 3, 4, darab rúdból kirakni?

c) Hányféleképpen tudjuk a 10-et kirakni, ha csak fehér (1) és rózsaszín (2) rudakat használunk?

5.3.10. Feladat(a) mego., b) mego., c) mego., d) mego.)

A 100-at hányféleképpen lehet

a) 10 pozitív egész szám;

b) 10 pozitív páros szám;

c) 10 egész szám;

d) 10 természetes szám (a 0 is megengedett)

összegeként előállítani, ha számít az összeadandók sorrendje?

5.3.11. Feladat(Mego.)

Hány lottószelvényt kell kitöltenünk a biztos telitalálathoz?

5.3.12. Feladat(a) mego., b) mego.)

Május 35-én a lottót úgy játsszák, hogy az 1, 2, 3, 20 számokból 18-at húznak ki.

a) Hány szelvényt kell kitöltenünk a biztos telitalálathoz?

b) Hány kell ahhoz, hogy biztosan legyen legalább 15 találatunk?

5.3.13. Feladat(Mego.)

Két iskola legjobb sakkozói versenyeztek egymással. Mindenki mindenkivel egy játszmát játszott. Először az egy-egy iskolán belüli játszmákra: összesen 66 játszmára került sor. Az egész körmérkőzés 136 játszmából állt. Hány versenyző indult az egyik és hány a másik iskolából?

5.3.14. Feladat(Mego.)

Hány olyan egymáshoz nem hasonló háromszög van, amely tompaszögű, továbbá nem egyenlő szárú és mindegyik szöge fokokban mérve egész számot ad?

5.3.15. Feladat(Mego.)

Egy egyfordulós futballbajnokságon a csapatok sorrendjét a gólarányok figyelembevétele nélkül egyértelműen meg lehetett határozni. A bajnokságon volt olyan csapat, amelyet a nála jobb helyezést elért csapatok valamelyike nem győzött le. Bizonyítsuk be, hogy a bajnokság folyamán volt döntetlen mérkőzés is. (Egyfordulós futballbajnokságon minden csapat minden csapattal egyszer játszik. Minden egyes mérkőzés után a győztes csapat két pontot, döntetlen esetén mindkét csapat egy-egy pontot kap.)

5.3.16. Feladat(Mego.)

A sakktábla bal alsó sarkából a jobb felső sarokba hányféle útvonalon juthat el a sánta bástya, amelyet csak jobbra és fölfelé léphet, mindig csak a szomszédos mezőre?

5.4 A Pascal háromszög

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

25. á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 (13)-(14) 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 (14) 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 (13), (14), (15) 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).

26. ábra

5.4.1. Feladat(I. mego., II. mego.)

A koordinátarendszer origójából indulva a rácspontokon mozgunk. Jobbra és felfelé léphetünk a szomszédos rácspontra. Hányféleképpen juthatunk el a (k;l) pontba (k,lN)?

5.4.2. Feladat(I. mego., II. mego.)

A 5.3.4 feladatban már láttuk, hogy

( a + b ) 0 = 1 ; ( a + b ) 1 = a + b ; ( a + b ) 2 = a 2 + 2 a b + b 2 ; ( a + b ) 3 = a 3 + 3 a 2 b + 3 a b 2 + b 3 ; ( a + b ) 4 = a 4 + 4 a 3 b + 6 a 2 b 2 + 4 a b 3 + b 4 .

Igazoljuk, hogy általában, tetszőleges n természetes szám esetén fennáll az

( a + b ) n = i = 0 n ( n i ) a n - i b i

összefüggés, amelyet Newton binomiális tétele néven szokás említeni. Valójában Newton tétele egy ennél általánosabb összefüggés, amelyben n tetszőleges valós szám lehet.

5.4.3. Feladat(Segít.)

Kavicsokat rendezünk a 27 ábrán látható rendben kupacokba. Hány kavics lesz a 100-adik kupacban?

27. ábra

5.4.4. Feladat(Segít.)

Határozzuk meg a 100. tetraéderszámot! (Hány golyó van a 28 ábrán a 100. kupacban? A kupacsorozat oldal- és fölülnézetben is látható az ábrán.)

28. ábra

5.4.5. Feladat(Elő. megj., I. mego., II. mego., III. mego., IV. mego.)

Határozzuk meg a Pascal háromszög n-edik sorában található elemek összegét!

5.4.6. Feladat(I. mego., II. mego., III. mego.)

Határozzuk meg a Pascal háromszög n-edik sorában álló elemek váltakozó előjelű összegét! Pld a negyedik sorban: 1-4+6-4+1=0.

5.4.7. Feladat(Elő. megj., Mego.)

Határozzuk meg a Pascal háromszög n-edik sorában található elemek négyzetösszegét!

5.4.8. Feladat(Elő. megj., I. mego., II. mego., III. mego.)

Igazoljuk a

( k + l n ) = i + j = n ( k i ) ( l j ) ,

azaz

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

összefüggést, ahol x<y esetén (xy)-t 0-nak tekintjük a Pascal félsík értelmezésének megfelelően.

5.4.9. Feladat(a) I. mego., a) II. mego., a) III. mego., b) I. mego., b) II. mego., b) III. mego., b) IV. mego., b) V. mego., c) eredm., d) mego.)

Adjuk össze a Pascal háromszög n-edik sorában az elemeket úgy, hogy a sorban k-adikat (0-tól számolva) megszorozzuk

a) 2k-nal! Pld a negyedik sorban: 11+42+622+423+124=81.

b) k-val! Pld a negyedik sorban: 10+41+62+43+14=32.

c) k(k-1)-gyel! Pld a negyedik sorban: 10(-1)+410+621+432+143=48.

d) k2-tel! Pld a negyedik sorban: 102+412+622+432+142=80.

5.4.10. Feladat(a) mego., b) mego., c) mego.)

Bergengóciában a Pascalháromszög helyett a Mascalháromszöggel számolnak. Ennek 0. sorában három elem áll:

2 - 5 4

A Mascal-háromszög képzési szabálya a Pascalháromszögével azonos. Határozzuk meg a Mascalháromszög n-edik sorában az elemek

a) összegét, b) előjeles összegét!

c) Írjuk fel képlettel a Mascal háromszög n-edik sorában a k-adik helyen álló számot (a 0. sorban rendre a 0., 1., 2. helyeken állnak a 2, -5, 4 számok).

5.4.11. Feladat(a) mego., b) mego., c) mego.)

Dr. Kekec a Piscalháromszögre esküszik. Ennek 0-adik sorában egyetlen 1-es áll, az alatta levő sorokban minden szám a fölötte lévő három szám összegével egyenlő (az üres helyek 0-nak tekintendők).

7. táblázat

Keressük a Piscal háromszög tulajdonságait! Pld határozzuk meg a Piscal-háromszög n-edik sorában található számok

a) összegét; b) váltakozó előjelű összegét!

c) Van-e szerepe az algebrában?

5.4.12. Feladat(Mego.)

Hányféle lépéssorozattal juthat el a bástya a 4×4-es sakktábla bal alsó sarkából a jobb felsőbe, ha csak jobbra (akármennyit) vagy felfelé (akármennyit) léphet? (Ha lép egyet jobbra majd kettőt megint jobbra, az más lépéssorozat, mintha egyből hármat lépne jobbra.)

5.4.13. Feladat(Segít.)

Adjunk váltakozóan előjeleket a Pascal háromszög n-edik sorában álló elemeknek és tekintsünk egy tetszőleges (n+1) elemből álló számtani sorozatot, ahol n>1! Vizsgáljuk a két sorozat skaláris szorzatát, azaz az azonos sorszámú elemek szorzatának összegét. Pld n=4 és a 3, 7, 11, 15, 19 sorozat esetén

3 1 - 7 4 + 11 6 - 15 4 + 19 1 = 0 .

Mit tapasztalunk? Keressünk magyarázatot!

5.4.14. Feladat(Zokni)(Mego.)

Töltsük ki a 29 ábrán a Pascal háromszöget és adjuk össze a vastagon szedett helyeken levő számokat! Végezzük el az összegzést hasonló állású egyenesek mentén! Miért érdekes az eredmény? Tegyünk megfigyelést, fogalmazzunk meg sejtést és igazoljuk!

29. ábra

5.4.15. Feladat(Mego.)

a) Határozzuk meg a Pascal háromszög jelzett téglalap alakú részében található számok összegét!

b) Adjunk meg n és k segítségével a megfelelő n×k méretű téglalap alakú részben található számok összegét!

30. ábra

5.5 Összetett leszámolási feladatok

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

5.5.1. Feladat(a) I. mego., a) II. mego., b) I. mego., b) II. mego., b) III. mego.)

Hány olyan háromjegyű szám van, amelyben minden számjegy

a) nagyobb, b) legalább akkora,

mint az előző (mint a tőle balra levő)?

5.5.2. Feladat(Mego.)

Mennyi az esélye, hogy a Lottószámok (az 1, 2, , 90 számokból húznak ki ötöt) között nincs két szomszédos szám?

5.5.3. Feladat(a) mego., b) mego.)

a) Külföldre utazom, három ajándékot szeretnék vinni magammal, majd később döntök kinek melyiket adom. Kilencféle ajándék jön szóba: Rubik-kocka, Tokaji aszú, Unicum, népművészeti terítő, Liszt cd, angol nyelvű album, angol nyelvű verseskötet, téli szalámi, matek könyv. Hányféleképpen választhatom ki a hármat, ha mindegyikből többet is vihetek, de összesen pontosan hármat?

b) Egy-egy ajándékot szeretnék kiválasztani a fenti 9-ből kinti cserepartneremnek, egy másik diáknak és az egyik tanárnak. Hányféleképpen választhatok, ha ugyanazt az ajándékot több embernek is adhatom?

5.5.4. Feladat(a) mego., b) eredm.)

a) Ha n-féle dologból k darabot kell választani, de a kiválasztott darabok sorrendje nem számít és mindegyik dologból többet akármennyit is választhatunk, akkor n elem k-adosztályú ismétléses kombinációiról beszélünk. Határozzuk meg ezek számát!

b) Ha n-féle dologból k darabot kell választani, és a kiválasztott darabok sorrendje is számít és mindegyik dologból többet akármennyit is választhatunk, akkor n elem k-adosztályú ismétléses variációiról beszélünk. Határozzuk meg ezek számát!

5.5.5. Feladat(I. mego., II. mego., III. mego.)

Pitagorasz táblázata (a szorzótábla) úgy van kitöltve, hogy a bal fölső sarkától számított n-edik sor és m-edik oszlop találkozásában található mezőben az nm szorzat értéke áll. Tekintsük az azonos átlóban álló számok összegeit! (a1=1, a2=2+2, a3=3+4+3 ) Határozzuk meg az N. átlóban álló számok összegét!

31. ábra

5.5.6. Feladat(Eredm.)

Egy körön felvettünk n pontot, majd összekötöttük mindegyiket mindegyikkel egy-egy egyenes szakasszal. Így legfeljebb hány metszéspont jöhetett létre a kör belsejében?

5.6 Dimenzió

Lásd még a 6.3.23, 6.3.6 feladatokat.

5.6.1. Feladat Osztójáték[](Segít.)

Ketten felváltva mondják a varázsszám pozitív osztóit. Már kimondott osztó osztóját egyik játékos sem említheti újra. Az veszt, aki kimondja a varázsszámot. Kinek kedvező a játék, Kezdőnek vagy Másodiknak, ha a varázsszám

a) 10, b) 16, c) 24, d) 36, e) 30, f) 2010?

5.6.2. Feladat(Mego.)

Rajzoljuk fel 10, 16, 24, 36, 30 és 2010 osztóhálóját!

Próbáljuk az adott szám osztóit a sík egy-egy pontjára írni úgy, hogy ha az 1-nek megfeleltetett pontot tekintjük origónak, akkor bármelyik osztóval való szorzásnak az osztó helyvektorával való eltolás feleljen meg.

5.6.3. Feladat (Segít., Mego.)

Írjuk be az alábbi táblázatba, hogy az n-dimenziós kockának (lásd a 32 ábrát) hány k-dimenziós (nk) lapja van!

8. táblázat

32. ábra

5.6.4. Feladat(Mego.)

Adjuk meg a

a) 30, b) 2010

minél több pozitív osztóját úgy, hogy közülük semelyik se legyen egy másikuk osztója!

5.6.5. Feladat(Mego.)

Hány olyan sorozat van, amely különböző pozitív egész számokból áll, első eleme az 1, utolsó eleme a 60 és minden eleme az előző elem egész számú többszöröse?

5.6.0.1 Ajánló

Julie Rehmeyer Seeing in four dimensions Mathematicians create videos that help in visualizing four-dimensional objects"[],

http://www.sciencenews.org/view/generic/id/35740/description/Seeing_in_four_dimensions .

Alexander Bogomolny[], The Tesseract,

http://www.maa.org/editorial/knot/tesseract.html .

5.7 Gráfok

5.7.1. Feladat(Mego.)

Egy nagy cég vacsoráján egy asztalhoz öt házaspár ült le. A hosszú hallgatást C. Frank úr törte meg, megkérdezvén mindenkit, még a saját feleségét is, hogy hány embert nem ismer. Csupa különböző választ kapott. Újabb rövid hallgatás után R. Korszakov úr szeme felcsillant és C. Frank úrhoz fordult.

Á, szóval ön embert nem ismer az asztalnál!

Noha C. Frank úr nem nyilatkozott, mennyit mondott R. Korszakov, és hogyan jött rá?

5.7.2. Feladat(I. mego., II. mego.)

Bergengócia bármely két városa között van busz- vagy repülőgépjárat. Igaz-e Bergengóciában, hogy vagy busszal vagy repülővel bármelyik városból bármelyik másikba el lehet jutni (átszállással, ha szükséges)?

5.7.3. Feladat(Mego.)

Bergengócia bármely két városa között van busz-, vonat- vagy repülőgépjárat. Igaz-e Bergengóciában, hogy vagy busszal vagy vonattal vagy repülővel bármelyik városból bármelyik másikba el lehet jutni (átszállással, ha szükséges)?

5.7.4. Feladat(a) mego., b) mego.)

Bergengócia bizonyos városai között van repülőgépjárat és bármelyik városból bármelyik másikba el lehet jutni menetrendszerinti repülőgépjáratokkal, átszállásokkal. A pénzügyminiszter mérges, mert látja, hogy a járatok alkalmazásával körutakat is lehet tenni, tehát vannak felesleges járatok. Követeli, hogy ezt szüntessék meg. Igaz-e, hogy járatok megszüntetésével elérhető, hogy ne lehessen körutazást tenni, de továbbra is el lehessen jutni bármelyik városból bármelyik másikba?

Oldjuk meg a feladatot az alábbi mindkét értelmezésben:

a) Egy repülőgépjárat két város közti oda-vissza közvetlen közlekedést jelent;

b) Egy repülőgépjárat két város egyikéből a másikba való közvetlen utazás lehetőségét jelenti, a visszautat nem.

5.7.5. Feladat(Mego.)

Bizonyítsuk be, hogy egy 30 fős vívóversenyen, ahol mindenki mindenkivel pontosan egyszer játszott, a verseny végén van olyan vívó, aki az összes többi versenyzőt vagy legyőzte, vagy ha kikapott egy A versenyzőtől, akkor van oly B versenyző, akit legyözött, és aki legyőzte A-t!

5.7.6. Feladat(Mego.)

Egy nagyszabású projektben 6 tudósból álló csoportok dolgoznak egy-egy résztémán. Az egyes csoportokban néhányan leveleznek egymással.

Mutassuk meg, hogy bármelyik hatos csoportban vagy van 3 ember, akik közül mindenki mindenkivel levelez, vagy van 3 olyan, hogy semelyik sem ír a másiknak.

5.7.0.1 Ajánló

Andrásfai Béla Versenymatek gyerekeknek[], IV. (Gumiországban) fejezet;

Gallai Tibor A königsbergi hidak, a kilenc ösvény és más gráfelméleti problémák, a [] kötetben,

http://www.tankonyvtar.hu/en/tartalom/tkt/matematikai-mozaik/ar07.html ;

Andrásfai Béla Hány szín kell a térkép színezéséhez, a [] kötetben,

http://www.tankonyvtar.hu/en/tartalom/tkt/matematikai-mozaik/ar11.html ;

Alexander Bogomolny Cut the Knot"[] portáljának gráfos nyitócikke (linkek a további cikkekre a lap alján):

http://www.cut-the-knot.org/do_you_know/graphs.shtml ;

Matkönyv[], Dobos Sándor: Kombinatorika 7-8., Gráfok fejezet,

http://matek.fazekas.hu/mathdisplay/cache/pdf/volume_k_i.pdf ;

Matkönyv[], Surányi László: Kombinatorika 9-10. megfelelő fejezetei,

http://matek.fazekas.hu/mathdisplay/cache/pdf/volume_k_ii.pdf ;

Pataki János A zsebrádiótól Turán tételéig"[],

http://matek.fazekas.hu/portal/tanitasianyagok/Pataki_Janos/elemek/elemek.html ;

Recski András Gráfok színezése,

http://matek.fazekas.hu/portal/eloadas/2007/eloadas_2008_01_22_recski.html ;

Bérczi Gergely, Gács András, Hraskó András, Szőnyi Tamás Reguláris gráfok, az [] kötetben,

http://www.tankonyvtar.hu/en/tartalom/tkt/uj-matematikai-mozaik-uj/ar03.html ;

Gyárfás András, Hraskó, András Teljes gráfok felbontásairól, az [] kötetben,

http://www.tankonyvtar.hu/en/tartalom/tkt/uj-matematikai-mozaik-uj/ar08.html ;

Virág Bálint Véletlen gráfok[],

http://matek.fazekas.hu/portal/eloadas/2010/Perkolacioelmelet_vegl.pdf ;

Egy olaszországi versenyfeladattól a Kneser sejtésig, a [] 2011. okt. 26-ai foglalkozása;

http://matek.fazekas.hu/portal/tovabbkepzesek/szeminarium/2011/2011pub03.pdf ;

5.8 Kombinatorikus geometria

5.8.1. Feladat(Mego.)

a) Bizonyítsuk be, hogy ha az 1,2,3,4,5 számokat pirossal és kékkel kiszíneztük, akkor az x+y=z egyenletnek van olyan megoldása, melyben x,y,z ugyanazt a színt kapta! (Itt nem kell az x, y, z ismeretleneknek különbözőnek lennie.)

b) Ha csak az 1,2,3,4 számokat színezzük ki?

5.8.2. Feladat (Mego.)

A sík pontjait pirossal és kékkel színeztük ki. Bizonyítsuk be, hogy bármely a>0 valós számhoz találunk két pontot, P-t és Q-t, amelyek egyszínűek, és távolságuk éppen a!

5.8.3. Feladat(Mego.)

A sík pontjait pirossal és kékkel és zölddel színeztük ki. Bizonyítsuk be, hogy bármely a>0 valós számhoz találunk két pontot, P-t és Q-t, amelyek egyszínűek, és távolságuk éppen a!

5.8.4. Feladat(Mego.)

Színezzük ki a síkot hét színnel úgy, hogy ne legyen két azonos színű pont, melyek közötti távolság 1!

5.8.5. Feladat(Mego.)

Színezzük ki a teret két színnel és bizonyítsuk be, hogy bármely a>0 számhoz találunk egy a oldalú szabályos háromszöget, melynek csúcsai egyszínűek!

5.8.6. Feladat(Mego.)

Ha a síkot két színnel színezzük, akkor vagy van két piros pont, melynek egységnyi a távolsága, vagy van három kék pont, melyek egy egység oldalú szabályos háromszöget alkotnak.

5.8.7. Feladat(Mego.)

Legyen a tetszőleges pozitív szám. Ha a síkot két színnel színezzük, akkor vagy van két piros pont, melynek egységnyi a távolsága, vagy van három kék pont, melyek egy a oldalú szabályos háromszöget alkotnak.

5.8.8. Feladat(Mego.)

Adott öt pont a síkon úgy, hogy nincs három közülük egy egyenesen. Bizonyítsuk be, hogy ekkor kiválasztható közülük négy, amelyik egy konvex négyszöget alkot!

5.8.9. Feladat(Mego.)

Adott a síkon 1,000,000 pont. Bizonyítsuk be, hogy akkor e pontok legalább 700 különböző távolságot határoznak meg!

5.8.10. Feladat(a) mego., b) mego.)

a) Színezzük meg pirosra vagy kékre az 1,2,,9 pontokat. Bizonyítsuk be, hogy akkor e pontok között van három különböző, melyek azonos színűek és egy számtani sorozat alkotnak.

b) Színezzük meg pirosra vagy kékre az 1,2,,8 pontokat úgy, hogy ne legyen három különböző, melyek azonos színűek és egy számtani sorozat alkotnának.

5.8.0.1 Ajánló

Hoksza Zsolt (Tóth Géza előadásától inspirálva) Kombinatorikus geometria és a Ramsey-tétel[]

http://matek.fazekas.hu/portal/kutatomunkak/Hoksza_Zsolt/ramsey.html ;

Tóth Géza Ramsey-típusú tételek és feladatok, az [] kötetben,

http://www.tankonyvtar.hu/hu/tartalom/tkt/uj-matematikai-mozaik-uj/ar09.html ;

Pach János A Happy End probléma – A kombinatorikus geometria kezdetei, az [] kötetben,

http://www.tankonyvtar.hu/hu/tartalom/tkt/uj-matematikai-mozaik-uj/ar10.html ;

Jaglom, Boltyanszkij Konvex alakzatok [];

V. G. Boltyanszkij, I. C. Grohberg Tételek és feladatok a kombinatorikus geometriából[].