Összeszámlálási alapproblémák

Feladat: Az alábbiakban egy döntés/cselekvés elé állítjuk a megoldót. Feladata, hogy sorolja fel az elõtte álló lehetõségeket:

1. Állítson sorba három játékfigurát (mondjuk a három figura: egy cowboy, egy indián és egy lovag).
2. Válasszon ki az elõzõ három figurából kettõt.
3. Húzzon ki egyesével az elõzõ három figurából kettõt (a húzásnál nem csak a kihúzott figurák számítanak, de az is, hogy melyiket huzza ki elõször, melyiket másodiknak).
4. Válasszon ki az elõzõ három figurából valahányat (esetleg mind a hármat, esetleg egyet sem).
5. Húzzon ki valahányat az elõzõ három figurából.
6. Állítson sorba négy játékfigurát (mondjuk a négy figura: egy cowboy, egy huszár, egy indián és egy lovag),
7. Válasszon ki az elõzõ négy figurából kettõt.
8. Húzzon ki egyesével az elõzõ négy figurából kettõt (a húzásnál nem csak a kihúzott figurák számítanak, de az is, hogy melyiket húzza ki elõször, melyiket másodiknak).
9. Válasszon ki az elõzõ négy figurából valahányat (esetleg mind a négyet, esetleg egyet sem).
10. Húzzon ki az elõzõ négy figurából néhányat.
11. 5 szaloncukort osszon el 3 tányérra (a cukrok, tányérok teljesen egyformák, lehet üres tányér is).
12. 7 szaloncukort osszon el 3 tányérra (a cukrok, tányérok teljesen egyformák, lehet üres tányér is).
13. 10 szaloncukort osszon el 3 tányérra (a cukrok, tányérok teljesen egyformák, lehet üres tányér is).
14. 5 szaloncukort osszon el télapó csomagokba (a cukrok teljesen egyformák, akár egy cukor is alkothat egy csomagot).
15. 7 szaloncukort osszon el télapó csomagokba (a cukrok teljesen egyformák, akár egy cukor is alkothat egy csomagot).
16. 10 szaloncukort osszon el télapó csomagokba (a cukrok teljesen egyformák, akár egy cukor is alkothat egy csomagot).
17. Állítsa sorba az 1,2,3,4,5,6 számokat úgy, hogy ne legyen három egymást követõ szám, amelyek monoton sorozatot alkotnak.
18. Állítsa sorba az 1,2,3,4,5,7 számokat úgy, hogy ne legyen három egymást követõ szám, amelyek monoton sorozatot alkotnak.
19. Állítsa sorba az 1,2,3,4,5,8 számokat úgy, hogy ne legyen három egymást követõ szám, amelyek monoton sorozatot alkotnak.
20. Egy 4x4-es táblázat (fehér papírlap) 16 mezõjét a mezõket határoló vonalak mentén két egyenlõ területû (8-8 mezõnyi) részre vágjuk. A két résznek összefüggõnek kell lenni. Két vágást nem tekintunk különbözõnek, ha a kapott két alakzatpár egymásba vihetõ (esetleg megfordítva). Soroljuk fel a lehetõségeket.
21. Milyen lehetõségeink vannak, ha az elõzõ vágást úgy szeretnénk elvégezni, hogy a kapott két alakzat egybevágó legyen?
22. Egy nyugat-keleti egyenes országutat egy északon eredõ, délre haladó kanyargós folyó 5-ször átmetsz. A 5 hidat számozzuk meg az országút mentén nyugatról keletre az 1,2,3,4,5 számokkal. A folyón északról délre utazva írjuk fel milyen sorrendben utazunk el a hidak alatt.
23. Egy nyugat-keleti egyenes országutat egy északon eredõ, délre haladó kanyargós folyó 7-szer átmetsz. A 7 hidat számozzuk meg az országút mentén nyugatról keletre az 1,2,3,4,5,6,7 számokkal. A folyón északról délre utazva írjuk fel milyen sorrendben utazunk el a hidak alatt.
24. Egy nyugat-keleti egyenes országutat egy északon eredõ, délre haladó kanyargós folyó 9-szer átmetsz. A 9 hidat számozzuk meg az országút mentén nyugatról keletre az 1,2,3,4,5,6,7,8,9 számokkal. A folyón északról délre utazva írjuk fel milyen sorrendben utazunk el a hidak alatt.

Feladat: Legyen H és H' két azonos elemszámú halmaz. Bizonyítsuk be, hogy

• H részhalmazainak halmaza és H' részhalmazainak halmaza is azonos elemszámú.
• H k elemû részhalmazainak halmaza és H' k elemû részhalmazainak halmaza is azonos elemszámú.
• H elemeinek sorbaállításait tartalmazó halmaz és H' elemeinek sorbaállításait tartalmazó halmaz is azonos elemszámú.
• H és H' elemeit betûknek képzelve, a H elemeibõl elõállítható 3 hosszú betûsorozatok halmaza és a H' elemeibõl elõállítható 3 hosszú betûsorozatok halmaza is azonos elemszámú.

Feladat:

1. Bizonyítsuk be, hogy 1.000.000-ig ugyanannyi természtes szám van, amelyek csak az 1, 2 és 5 számjegyeket használják, mint amelyek csak a 3, 8 és 9 -es számjegyeket használják.
2. 1.000.000-ig mely természetes számokból van több: amelyek csak az 1, 2 és 5 számjegyeket tartalmazzák, illetve azokból, amelyek csak a 3, 8 és 0 számjegyeket tartalmazzák.

Feladat: Írjuk fel az alábbi rekurziók által definiált sorozatok elsõ 20 elemét:

• a₀=0, a_k+1=a_k+2,
• b₀=0, b_k+1=b_k+2k+1,
• c₀=1, c_k+1=c_k+ c_k-1+...+c₀,
• d₀=0, d_k+1=d_k-1, ha k páros és d_k+1=-d_k, ha k páratlan,
• e₀=0, e₁=1, e_k+2=e_k+2, ha k páros, e_k+2=2e_k, ha k páratlan,
• f₀=f₁=1, f_k+2=f_k+1+f_k,
• g₀=1, g_k+1=g₀g_k+ g₁g_k-1+g₁g_k-2+ ...+ g_k-1g₁+g_kg₀,
• G₀=1, G_k+1=(4k-2)/(k+1) G_k,
• h₀=1, h_k+1=2^h_k.

Feladat: Írjuk fel az alábbi rekurziókkal definiált két paraméteres számseregek minél több értékét kis pozitív paraméter-értékekre:

• B(0,n)=B(n,0)=1 minden n természetes számra, B(n+1,k+1)= kB(n+1,k)+B(n,k+1),
• C(0,n)=C(n,0)=1 minden n természetes számra, C(n+1,k+1)= C(n+1,k)+nC(n,k+1),
• D(0,n)=D(n,0)=1 minden n természetes számra, D(n+1,k+1)=kD(n+1,k)+nD(n,k+1),
• E(0,n)=E(n,0)=1 minden n természetes számra, E(n+1,k+1)=E(n+1,k)+n+1,
• O(0,n)=O(n,0)=n minden n természetes számra, E(n+1,k+1)=E(n+1,k)+1,
• S(0,n)=S(n,0)=0 minden n természetes számra, S(n+1,k+1)=S(n+1,k)+n+1,
• A(1,n)=2n, A(n,1)=2 minden n természetes számra, A(n+1,k+1)= A(n,A(n+1,k)).

Feladat: Egy üres papírlapra 20 másodperc alatt írjunk fel egy minél nagyobb természetes számot leíró definíciót. Hasonlítsuk össze számunkat az elõzõ feladatban definiált A(5,5) számmal.