FPI matek szakkör 8. évf.
4. szakkör
órai feladatok megoldásokkal
4. szakkör, 2004. október. 20. Az órai feladatok megoldása Most csak három önmagában nem nehéz feladatot kapsz, és a feladatot magadnak kell általánosítani, szisztematikusan adatot gyűjteni, általános sejtést megfogalmazni, majd esetleg bizonyítani is. 1.9 Bontsd fel a zárójelet! (a + b)4 = Megoldás (a konkrét feladaté) (a + b)2⋅(a + b)2 = (a2 + 2ab + b2)⋅(a2 + 2ab + b2) = a4 + 4a3b + 6a2b2 + 4ab3 + b4. Megoldás (szisztematikus építkezés, adatgyűjtés) a+b=a+b (a + b)2 = a2 + 2ab + b2 (a + b)3 = a3 + 3a2b + 3ab2 + b3 (a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4 (a + b)5 = a5 + 5a4b + 10a3b2 + 10a2b3 + 5ab4 + b5 (a + b)6 = a6 + 6a4b + ... Ismerősek ezek a számok a Pascal háromszögből.
1a6
1a5 +
1a 1a2 + 3 + 3a2b 1a 1a4 + 4a3b + 4 + 5a b + 10a3b2 6a5b + 15a4b2 +
1 + 1b 2ab + 1b2 2 + 3ab + 1b3 6a2b2 + 4ab3 + 1b4 2 3 4 + 10a b + 5ab + 1b5 20a3b3 + 15a2b4 + 6ab5 + 1b6
... Úgy tűnik, hogy ha (a + b)n –t kifejtjük – azaz felbontjuk a zárójelt -, és a tagokat a kitevője szerint csökkenő sorrendben írjuk fel (an, an-1b2 , an-2b2, ..., bn ), akkor az együtthatók épp a Pascal háromszög n-edik sorának számai lesznek abban a sorrendben, ahogy ott következnek. Tehát: Binomiális tétel n n n n n 2 n −2 n 1 n −1 n n a b + a b + b , (a + b )n = a n + a n−1b1 + a n− 2 b 2 + a n−3b 3 + ... + 0 1 2 3 n − 2 n − 1 n n n n n n n n ahol , , , ,..., , , a Pascal háromszög n-edik sorának, 0., 1., 2., 3., 0 1 2 3 n − 2 n − 1 n n ..., (n-2)-edik, (n-1)-edik, n-edik elemét jelöli, tehát a Pascal háromszög n-edik sorának kk adik eleme.
1/6
FPI matek szakkör 8. évf.
4. szakkör
órai feladatok megoldásokkal
I. megjegyzés A „binomiális tétel” elnevezést így fordíthatnánk le: „a két tagra vonatkozó tétel” azaz a kéttagú összeg – (a + b) – hatványára vonatkozó összefüggés. II. megjegyzés n -t binomiális együtthatónak is nevezik. A Pascal háromszögre vonatkozó ismereteink k alapján n n ⋅ (n − 1) ⋅ (n − 2) ⋅ ... ⋅ (n − k + 1) n n! = = . A 3. szakkör 1.3. feladata alapján az k ⋅ (k − 1) ⋅ (k − 2) ⋅ ... ⋅ 1 k!⋅(n − k )! k k a szám, ahányféleképpen n (különböző) dologból kiválasztható k, ha nem számít a kiválasztás sorrendje. A binomiális tétel I. bizonyítása (rekurzió) Nézzük meg, hogyan számoljuk ki (a + b)2-t! Tényleg a Pascal háromszög második sorában lesznek az együtthatók? (a + b)2 = (a + b)⋅(a + b) = a⋅(1a + 1b) + b⋅(1a + 1b) . A beszorzást a Pascal háromszögben is nyomon követhetjük:
Az a-val való szorzás „balra lefelé visz”, míg a b-vel való szorzás „jobbra lefelé visz”. Az 1a2-et az 1a-ból, annak a-val való megszorzásából nyertük, míg a 2ab-ból az egyik ab az előző sorban található 1b-nek az a-val való szorzatából, a másik ab az előző sorban levő 1anak a b-vel való szorzatából adódott. Végül 1b2 az 1b tag b-vel való szorzatából jön ki. Így jön ki (a + b)3 is az (a + b)2 –re vonatkozó eredményből: (a + b)3 = (a + b) ⋅ (a + b)2 = a⋅(1a2 + 2ab + 1b2) + b⋅(1a2 + 2ab + 1b2), és a beszorzásban, összegzésben a Pascal háromszög segít:
Így haladhatunk tovább, (a + b)n együtthatói épp úgy számolhatók ki (a + b)n együtthatóiból, ahogy a Pascal háromszög n-edik sorának számai kiszámolhatók a Pascal háromszög (n-1)esik sorának számaiból. Ez igazolja a binomiális tételt. A binomiális tétel II. bizonyítása (kombinatorikus értelmezés) (a + b)n felbontásához az (a + b)⋅(a + b)⋅(a + b)⋅ ...⋅(a + b) n-tényezős szorzatban kellene felbontani a zárójeleket. Hogyan kerül a felbontásba an? Úgy, hogy a beszorzáskor mindegyik tényezőből az a tagot választjuk. Hogyan kerül a felbontásba an-2b2? Pld úgy, hogy az első (n-2) tényezőből az a tagot, az utolsó 2 tényezőből a b tagot választjuk. De úgy is, hogy az n tényező közül bármelyik 2-ből a 2/6
FPI matek szakkör 8. évf.
4. szakkör
órai feladatok megoldásokkal
b tagot, a többiből az a tagot választjuk ki. Ezért an-2b2 együtthatója a felbontásban annyi lesz n ahányféleképpen az n tényező közül kiválasztható 2, azaz . 2 n Ehhez hasonlóan an-kbk együtthatója lesz, hiszen a n tényező közül ennyiféleképpen k választható ki az a k db, amelyből a b tagot választjuk ki a beszorzáskor (a többiből az a tagot választjuk). A tételt bebizonyítottuk. 1.10. Hány megoldása van az x + y + z = 6 egyenletnek a nemnegatív egész szám(hármas)ok halmazán? (Az x = 0, y =0, z = 6 és az x = 6, y =0, z = 0 megoldások most különbözőnek számítanak. Megoldás (a konkrét feladaté) Alább táblázatban szedtük össze a megoldásokat. A legnagyobb lehetséges x értékkel kezdtük, majd fokozatosan csökkentettük. Az x adott értéke mellett az y értékek is csökkenő sorban következnek (lexikografikusan csökkenő elrendezés). x 6 5 5 4 4 4 3 3 3 3 2 2 2 2 2 1 1 1 1 1 1 0 0 0 0 0 0 0 y 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0 5 4 3 2 1 0 6 5 4 3 2 1 0 z 0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5 0 1 2 3 4 5 6 28 megoldást kaptunk. Az x = 6 értékhez 1, az x = 5 értékhez 2, az x = 4 értékhez 3, ... az x = 0 értékhez 7 megoldás tartozik így is kijön az 1 + 2 + 3 + ... + 7 = 28 megoldás. Megoldás (szisztematikus építkezés, adatgyűjtés) Oldjuk meg sorra az x + y + z = 0, x + y + z = 1, x + y + z = 2, ... egyenleteket! Az eredmények a táblázatból leolvashatók. Látható, hogy az x+y+z=n egyenlet megoldásainak száma x = n –re 1, x = (n – 1)-re 2, x = (n – 2)-re 3, ..., x = 0-ra (n + 1), tehát összesen 1 + 2 + 3 + ... + (n + 1) = (n+1)(n+2)/2 megoldás van.
x y z x+y+z=0 0 0 0
1
x+y+z=1 1 0 0 0 1 0 0 0 1
3
x+y+z=2 2 1 1 0 0 0
0 1 0 2 1 0
0 0 1 0 1 2
6
x+y+z=3 3 2 2 1 1 1 0 0 0 0
0 1 0 2 1 0 3 2 1 0
0 0 1 0 1 10 2 0 1 2 3
3/6
x x+y+z=4 4 3 3 2 2 2 1 1 1 1 0 0 0 0 0
y 0 1 0 2 1 0 3 2 1 0 4 3 2 1 0
z 0 0 1 0 1 2 0 1 15 2 3 0 1 2 3 4
FPI matek szakkör 8. évf.
4. szakkör
órai feladatok megoldásokkal
Megjegyzés A feladat eredménye, pontosabban az x + y + z = n egyenlet megoldásainak száma (x, y, z nemnegatív egészek és számít a sorrendjük) is megtalálható a Pascal háromszögben, az alább vastagon szedett átlóban: 1 1 2
1 1 1 1 1 1 1 1
6
8 9
4 15
28 36
20
1 7
21 56
126
1 6
15 35
70 126
1 5
10
35 56
84
1 4
6 10
21
1 3
3
5
7
1
8
28 84
1
36
1 9
1
1.10.1. a) Magyarázzuk meg a Pascal háromszög alapján, miért a fent jelölt átlóban van az x+y+z=n egyenlet megoldásainak száma minden nemnegatív egész n esetén? b) Hány megoldása van az x + y + z + t = 6 egyenletnek a nemnegatív egész szám(négyesek)ek halmazán? I. megoldás a) Lépjünk vissza egy kicsit! Legyen először csak egy ismeretlenünk! „Vizsgáljuk” az z = 0, z = 1, z = 2, ... „egyenletek” megoldásainak számát! Természetesen mindegyiknek 1 megoldása van, mondhatjuk ezek a megoldásszámok állnak a Pascal háromszög szélső átlójában. Nevezzük ezt a 0- átlónak. Legyen most két ismeretlenünk, azaz nézzük az y + z = 0, y + z = 1, y + z = 2, ... egyenleteket! Válasszuk ki pld az y + z = 6 egyenletet. Ebben y-nak 7-féle értéke lehet (0-tól 6-ig) és bármelyik értéket választjuk mindig egy egyváltozós „egyenletünk” marad, amelynek mindig egy megoldása van. Összesen tehát 7 megoldás lesz. Ehhez hasonlóan az y + z = n egyenletnek (n + 1) megoldása van. y + z = 0, y + z = 1, y + z = 2, ... egyenletek megoldásszámai a Pascal háromszög első átlójában sorakoznak. Ha három ismeretlenünk van, tehát az x + y + z = n egyenletet vizsgáljuk, akkor x értékét nnek, (n-1)-nek, ..., 1-nek, 0-nak választhatjuk. Az egyes választások mellett egy-egy kétváltozós egyenletet kapunk. Ezek megoldásai a Pascal háromszög első átlójában fölülről egyesével sorakoznak: 1, 2, ..., n, (n + 1). A 3. szakkör 1.6. feladatban láttuk, hogy a Pascal háromszög bármely átlójában az elemek összege a legfölső elemtől valamelyik elemig egyenlő a legutolsó elemtől a Pascal háromszögben balra lejjebb található számmal. Így a jelen esetben az eredmény a második átlóba kerül. b) Az x + y + z + t = 6 egyenletben x értéke lehet 6, 5, 4, 3, 2, 1 és 0. Az egyes értékek választása után rendre az
4/6
FPI matek szakkör 8. évf.
4. szakkör
órai feladatok megoldásokkal
y + z + t = 0, y + z + t = 1, y + z + t = 2, y + z + t = 3, y + z + t = 4, y + z + t = 5, y + z + t = 6 egyenleteket kell megoldanunk. Ezek megoldásainak száma a Pascal háromszög második átlójában olvasható le, rendre 1, 3, 6, 10, 15, 21 és 28. Ezek összege, a 3. szakkör 1.6. feladata alapján a Pascal háromszögben a 28-tól balra lefelé található szám, azaz 84. Ehhez hasonlóan, ha k db változó összege n, és a nemnegatív megoldásokat keressük, akkor a megoldások számát a Pascal háromszög (k-1)-edik átlójából olvashatjuk le, mégpedig ott az nedik elem a megoldásszám (ha a 0. elemtől számolunk). II. megoldás (kezdemény) Ábrázoljuk 6 felbontásait a számegyenesen!
Az ábrán három példa látható. Először felmértük az origótól x-et, majd annak végpontjából yt, és 6-ig a maradék lesz z. Egy-egy nagy „pöcköt” helyeztünk el x és y, illetve y és z közé. A 7 7 ⋅ 6 két pöcköt hét helyre tehetjük, ez = = 21 lehetőség. A két pöcök még lehet 2 2 ugyanazon a helyen is (ezek felelnek meg az y = 0 esetnek), ami további 7 lehetőség, tehát összesen 28. ... 1.11. Hányféleképpen mehetünk fel egy hatfokú lépcsőn, ha egy lépéssel egy vagy két fokot mehetünk feljebb?
5/6
FPI matek szakkör 8. évf.
4. szakkör
órai feladatok megoldásokkal
I. megoldás Csoportosítsuk a lehetőségeket aszerint, hogy hányszor lépünk két fokot! lépések a 6. fokig lehetőségek 2-es 1-es összes 6 = 1 0 6 6 0 1
4
5
2
2
4
3
0
3
összesen:
5 = 5 1 4 = 6 2 3 = 1 3 13
Hasonlóan végigszámolhatjuk a lehetőségeket, ha az 1., 2., 3., 4., 5. vagy 7. fokig megyünk. Ha fn jelöli az n-edik fokra való eljutás lehetőségeinek számát, akkor f1 = 1, f2 = 2, f3 = 3, f4 = 5, f5 = 8, f6 = 13, f7 = 21. Megjegyzés Az f1, f2, f3, f4, f5, f6, ... számok az I. megoldás alapján kiolvashatók a Pascal háromszögből:
Így logikus f0-nak az 1-et tekinteni. II. megoldás Észrevehetjük, hogy a kapott sorozatban bármelyik elem az előző kettő összege (amennyiben van előző kettő), azaz fn = fn-1 + fn-2 , ha n>2. Ezt így magyarázhatjuk meg: az n-edik lépcsőfokra vagy az (n-1)-edik fokról lépünk fel egyes lépéssel, vagy az (n-2)-edik fokról egy kettes lépéssel. Más lehetőség nincs. Így az n-edik fokra annyiféleképpen juthatunk fel, mint az (n-1)-edik fokra és az (n-2)-edik fokra összesen. Az 1. lépcsőfokra 1-féleképpen, a 2. lépcsőfokra 2-félekéépen juthatunk el, innentől kezdve pedig már használhatjuk a képletet.
6/6