16. FEJEZET: A teljes indukció
Feladat: 16.1. (M)
A Bergengóc Agyvelőfejlesző Iskola tanévzáró
értekezletén többen felvetették, hogy
általában a tanév első napján semmit nem lehet
még tanítani, ezért javasolták, hogy ez a
tanítási nap maradjon el. Mi következik ebből?
Feladat: 16.2. (M)
Repülő Rezső magasugróbajnok így
emlékezett vissza pályafutásának kezdetére:
,,Életem legelső edzésén sikerült átugrani
a 10 cm-es magasságot. Majd észrevettem, hogy ha egy
x
cm-es magasságot sikerül átugrani, akkor kicsit
alaposabb koncentrálással, nagyobb nekifutással az
(
x+1) cm-es magasságot is át tudom ugrani."
Mire következtethetünk ez alapján?
Feladat: 16.3. (M)
a) Felvágható-e egy négyzet 10 négyzetre?
A darabok lehetnek különböző méret?ek.
b) Felvágható-e egy négyzet 1234567 darab
négyzetre?
Feladat: 16.4. (M)
Felvágható-e egy háromszög
n
háromszögre, melyek az eredetihez hasonlók, ha
n>5?
Feladat: 16.5.
A
10 mely hatványai állíthatók elő két pozitív négyzetszám
összegeként?
Feladat: 16.6. (M)
A síkot néhány egyenes tartományokra osztja.
Kiszínezhetők-e ezek két színnel úgy, hogy a
közös határszakasszal rendelkező tartományok
különböző szín?ek legyenek?
Feladat: 16.7. (M)
A körmérkőzéses iskolai ping-pong bajnokságot követően,
vacsoraosztás előtt a versenyzőket libasorba
szeretnénk állítani úgy, hogy mindenki előtt, kivéve
persze a sorban legelsőt, olyan ember álljon, akitől
kikapott. Megtehetjük-e ezt minden esetben?
Feladat: 16.8. (M)
Az 1, 2, ...,
n számok egy sorrendjében két
szám
inverzióban áll, ha a nagyobb
megelőzi a kisebbet. Például
n=5 esetén a 42513
sorrendben az inverzióban álló párok a 4-2, 4-1,
4-3, 2-1, 5-1, 5-3. Az összes inverzió száma 6 és
például a 2 két másik számmal áll
inverzióban.
a) Igazoljuk, hogy
n=7 esetén van olyan sorrend,
amikor minden szám két másikkal áll
inverzióban.
b) Mely
n esetén van olyan sorrend, amikor minden
szám 3 másikkal áll inverzióban?
Feladat: 16.9. (M)
Hány részhalmaza van egy
n elem? halmaznak?
Feladat: 16.10. (M)
Mutassuk meg, hogy minden
n>0 esetén egy
n elem?
halmaznak ugyanannyi páros elemű részhalmaza van, mint
páratlan elem?.
Feladat: 16.11. (M)
Egy
n elem? halmaz részhalmazai elhelyezhetők-e egy
kör mentén úgy, hogy két szomszédos
részhalmaz legfeljebb egyetlen elemben
különbözzön?
Feladat: 16.12. (M)
Legyen
H={2,3,…,n}. Tekintsük
H nem üres
részhalmazaiban az elemek szorzatát. Mennyi ezen
számok reciprokösszege? Pl.
n=4 esetén
1
2
+
1
3
+
1
4
+
1
6
+
1
8
+
1
12
+
1
24
=
3
2
|
Feladat: 16.13. (M)
Függönyt szeretnénk felcsipeszelni. Akkor
könny? egyenletesen elosztani a csipeszeket, ha
először felcsiptetjük a két szélét, majd a
közte levő részt felezzük, aztán a csipeszek
közötti részeket tovább felezzük és
így tovább.
Hány csipesz legyen a karnison, hogy ez a módszer
m?ködjön?
Feladat: 16.14. (S)
Bontsunk fel egy háromszöget kis háromszögekre úgy, hogy bárhogyan
kiválasztva három pontot a felbontást adó háromszögek csúcsai
közül azok ne essenek egy egyenesre. Igazoljuk, hogy a
felbontásban szereplő kis háromszögek száma csak páratlan szám
lehet.
Feladat: 16.15. (M)
n≥4 idős hölgy mindegyike tud egy pletykát,
azonban csak telefonon tudnak beszélni egymással. Mutassuk
meg, hogy
2n-4 hívással megoldható, hogy mindenki
ismerje mindegyik pletykát.
Feladat: 16.16. (M)
Mutassuk meg, hogy az 1, 2, ..., 3
k
számok
közül kiválasztható 2
k
különböző szám úgy, hogy bármely
két kiválasztott szám számtani közepe ne
legyen kiválasztott.
Feladat: 16.17. (M)
a) Mely páros számok írhatók fel két
pozitív, páros, összetett szám
összegeként?
b) Mely páros számok írhatók fel
három pozitív, páratlan, összetett szám
összegeként?
Feladat: 16.18. (M)
Igazoljuk, hogy:
a)
∑i=1
ni=
n(n+1)
2
;
b)
∑i=1
n
i2
=
n(n+1)(2n+1)
6
;
c)
∑i=1
n
i3
=
(
n(n+1)
2
)2
.
Feladat: 16.19. (M)
Igazoljuk, hogy:
a)
∑i=1
ni(i+1)=
n(n+1)(n+2)
3
;
b)
∑i=1
n
1
i(i+1)
=1-
1
n+1
.