19. FEJEZET: Leszámlálás

Feladat: 19.1.
Hány olyan pontosan négyjegyű szám van, amely nem osztható öttel és minden jegye különböző?
 

Feladat: 19.2.
[176] Hány olyan ötjegyű szám van, amely 6-tal végződik és hárommal osztható? (Kürschák-verseny 1930.)
 

Feladat: 19.3.
[187]. Book 5. Hány olyan permutációja van az első n pozitív számnak, ahol sem az egyes, sem a kettes nem áll a helyén?
 

Feladat: 19.4.
[94] Hány olyan legfeljebb hatjegyű természetes szám van, amelyben előfordul az 1-es számjegy? (OKTV, 1960)
 

Feladat: 19.5.
[94] Hány olyan megoldása van az ∣x∣+∣y∣<1000 egyenlőtlenségnek, amelyben x és y egész számok? (OKTV, 1959)
 

Feladat: 19.6.
[94]* Legyenek a és b valós számok. Hány olyan száztagú számtani sorozat van, amelynek a és b is tagja?
 

Feladat: 19.7.
Egyforma egyforintosokat osztunk ki gyerekek között. Hányféleképpen oszthatunk ki
a) 2 gyereknek 8 Ft-ot
 
b) 3 gyereknek 8 Ft-ot
 
c) 4 gyereknek 10 Ft-ot
 
d) k gyereknek n Ft-ot
 

, ha azt akarjuk, hogy minden gyerek kapjon legalább egy forintot?
 

Feladat: 19.8.
Egyforma egyforintosokat osztunk ki gyerekek között, de most nem ragaszkodunk hozzá, hogy mindenki kapjon legalább 1 forintot. Hányféleképpen oszthatunk ki
a) 2 gyereknek 8 Ft-ot?
 
b) 3 gyereknek 8 Ft-ot?
 
c) 4 gyereknek 10 Ft-ot?
 
d) k gyereknek n Ft-ot?

 

Feladat: 19.9.
Hányféleképpen lehet szétosztani n darab egyforma egyforintost k gyerek között úgy, hogy mindenki kapjon legalább 2 forintot?
 

Feladat: 19.10.
Hányféleképpen oszthatunk szét n darab egyforma egyforintost k fiú és l lány között úgy, hogy a lányok mindegyike kapjon leaglább egy forintot?
 

Feladat: 19.11.
A kaszinóban k gróf kártyázik. Eredetileg mindegyiknek p pengője volt. A játék végén összeszámlják, hogy ki hány pengőt nyert vagy vesztett. Hány lehetséges kimenetel adódhat? (Senki sem kért kölcsön a játék közben.)
 

Feladat: 19.12.
* Hányféleképp lehet a kocka gráfjának hét élét úgy kiválasztani, hogy azok egy Hamilton-utat alkossanak?
 

Feladat: 19.13.
Kutató munka: Hozzuk zárt alakra a következő összeget: ( 2 2 )+( 3 2 )+…+( n 2 )!
 

Feladat: 19.14.
Kutató munka: Hogyan általánosítható a 19.13. feladat eredménye?
 

Feladat: 19.15.
Hozzuk zárt alakra a következő kifejezést: ( n 0 )( n k )+( n 1 )( n k-1 )+…+( n i )( n k-i )+…+( n k )( n 0 )
 

Feladat: 19.16.
Hogyan általánosítható a 19.15. feladat állítása?
 

Feladat: 19.17.
Kutató munka: A K.I.4.19. feladatban már szó esett Dr. Kekecről, aki a Piscal-há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). A ,,rendes" Pascal háromszög n-edik sorának k-adik helyén álló számot megkaphatjuk úgy, hogy összeszámoljuk, hányféleképpen írhatjuk fel a k számot n tagú összegként úgy, hogy minden tag nulla vagy egy, a sorrend számít. Próbáljunk ehhez hasonló utasítást találni a Piscal-háromszög n-edik sorának a) n-edik sorának középső oszlopában álló számra, b) n-edik sorának a középső oszlopától balra és jobbra k hellyel arrébb álló számra!
 

Feladat: 19.18.
Kutató munka: Folytassuk a Piscal-háromszögnek a 19.17. feladatban megkezdett elemzését! Bizonyítsuk be, hogy az n-edik sor középső oszlopában álló számok megegyeznek azzal, ahányféleképpen n golyót ki tudunk színezni három színnel, fehérrel, feketével és tarkával úgy, hogy a fehér és a fekete golyók száma megegyezik.
 

Feladat: 19.19.
Kutató munka: Folytassuk a Piscal-háromszög a 19.17. feladatban megkezdett elemzését! Fejezzük ki az n-edik sor középső oszlopában álló számot binomális együtthatókkal!
 

Feladat: 19.20.
[187]. Book 3. A következő azonosságra keresünk kombinatorikai bizonyítást:

( ( n 2 ) 2 )=3( n+1 4 ).

Felveszünk n pontot a síkon. Az azonosság bal oldala ekkor az ezek között behúzható szakaszokból alkotott párok száma. Hogyan interpretáljuk az azonosság jobb oldalát?
 

Feladat: 19.21.
Egy kilencelemű halmazból akarunk kiválasztani hármasokat úgy, hogy semelyik két kiválasztott hármasnak ne legyen egynél több közös eleme. Legfeljebb hány hármast választhatunk ki?
 

Feladat: 19.22.
Egy n elemű halmazból háromelemű részhalmazokat akarunk kiválasztani úgy, hogy semelyik elempár ne szerepeljen két kiválasztott részhalmazban. (Vagy másképp fogalmazva: hogy bármely két kiválasztott hármasnak legfeljebb egy közös eleme legyen.) Bizonyítsuk be, hogy legfeljebb a hármasok n-2-ed részét választhatjuk ki!
 

Feladat: 19.23.
Bizonyítsuk be, hogy a 19.22. feladatban kapott becslés végtelen sok n-re pontos.
 

Feladat: 19.24.
Hány olyan különböző ( H1 , H2 , H3 ) halmazhármas van (ahol a halmazok sorrendje is lényeges), amelyek uniója az {1,2,3,4,5,6,7,8,9,10} halmaz, és a három halmaznak nincs közös eleme? (OKTV, 1991)
 

Feladat: 19.25.
a) Egy húszelemű halmaznak kiválasztottunk néhány ötelemű részhalmazát úgy, hogy semelyik kettőnek nincs egynél több közös eleme. Bizonyítsuk be, hogy legfeljebb 19 részhalmazt választottunk ki. b) Igaz marad-e az állítás akkor is, ha csak azt tudjuk, hogy minden halmaz legalább ötelemű? * c) Meg lehet-e adni egy húszelemű halmaz 19 ötelemű részhalmazát úgy, hogy semelyik kettőnek ne legyen egynél több közös pontja? d) Kiválasztottuk egy 16 elemű halmaznak néhány ötelemű részhalmazát úgy, hogy semelyik kettőnek nincs egynél több közös eleme. Bizonyítsuk be, hogy legfeljebb 12 részhalmazt választhattunk ki.
 

Feladat: 19.26.
Legyen n>5, és tegyük fel, hogy egy n elemű halmazból kiválaszható néhány ötelemű részhalmaz úgy, hogy az n elemű halmaz minden háromelemű részhalmazát a kiválasztott öteleműek közül pontosan egy tartalmazza. Bizonyítsuk be, hogy ekkor n legalább 16. (Arany Dániel-verseny, 2002K)
 

Feladat: 19.27.
Egy n elemű halmazból H kiválasztottunk néhány l elemű részhalmazt úgy, hogy bármely kettőnek legfeljebb egy közös eleme van. a) Bizonyítsuk be, hogy legfeljebb n(n-1)/l(l-1) halmazt választottunk ki. b) Tudjuk még azt is, hogy a kiválasztott halmazok a H halmaz minden elempárját pontosan egyszer fedik le. Bizonyítsuk be, hogy akkor n-1 osztható l-1-gyel és n(n-1) oszható l(l-1)-gyel.
 

Feladat: 19.28.
Hány szám választható ki az első
a) 8
 
b) 9
 
c) *10
 

számból úgy, hogy bármely két kiválasztott szám összege különböző legyen? (A számok kétszeresét is kéttagú összegnek tekintjük.)
 

Feladat: 19.29.
Legyen n pozitív egész szám. Adott k darab n-nél nem nagyobb pozitív egész szám úgy, hogy bármely kettő összege különböző. (A számok kétszeresét is kéttagú összegnek tekintjük.) Bizonyítsuk be, hogy k<2n;
 

Feladat: 19.30.
* Bizonyítsuk be, hogy a 19.29. feladatban adott becslés k<2n-1+1/2-re javítható.
 

Feladat: 19.31.
Van két azonos sugarú körünk, mindkettő fel van osztva 16 darab 22,5 -os körcikkre 16 sugárral. A körcikkek közül mindkét körben nyolc-nyolc feketére van festve, nyolc-nyolc pedig fehérre. (Nem feltétlenül váltakozva jönnek a színek!) Csak úgy helyezhetjük a két kört egymásra, hogy az egyes körcikkek fedjék egymást. (Két körcikk vagy teljesen fedi egymást, vagy nincs közös területű részük.) Bizonyítsuk be, hogy egymásra helyezhetők úgy, hogy legalább nyolc-nyolc egymást fedő körcikknek azonos legyen a színe. (Ki miben tudós? 1984)
 

Feladat: 19.32.
* [174] Egy 3n+1 tagú társaság bármely két tagja vagy teniszezni, vagy sakkozni, vagy pingpongozni szokott egymással. Mindegyiküknek n tenisz-, n sakk- és n pingpongpartnere van. Bizonyítsuk be, hogy van a társaságban három olyan ember, akik egymás között mind a három játékot játsszák. (Kürschák J. verseny, 1987)
 

Feladat: 19.33.
[183] Legfeljebb hány valós számból állhat az a sorozat, amelynek bármely hét egymás utáni tagját összeadva pozitív számot, bármely 11 egymás utáni tagját összeadva negatív számot kapunk? (IMO 1977/2)