A B. 4231. feladat (2009. december)

B. 4231. Mutassuk meg, hogy az (x+y)ⁿ binomiális tétel szerinti kifejtésében a 3-mal nem osztható együtthatójú tagok száma nem osztható 5-tel.

(5 pont)

A beküldési határidő 2010. január 11-én LEJÁRT.

Megoldás. Jelölje a 3-mal nem osztható együtthatójú tagok számát $\displaystyle S(n)$, ekkor $\displaystyle S(1)=2$, $\displaystyle S(2)=3$. Először megmutatjuk, hogy minden $\displaystyle k$ pozitív egészre $\displaystyle S(3^k)=2$. Számoljunk az együtthatókkal modulo 3. Tekintsük $\displaystyle x$ és $\displaystyle y$ egész együtthatós polinomjait, vagyis az olyan $\displaystyle p=\sum_{i,j=0}^\infty a_{i,j}x^iy^j$ alakú összegeket, ahol minden $\displaystyle a_{i,j}$ együttható egész szám, és véges sok kivétellel minden $\displaystyle a_{i,j}$ értéke 0. Nevezzük a

$\displaystyle p= \sum_{i,j=0}^\infty a_{i,j}x^iy^j\qquad \hbox{ill.}\qquad p'=\sum_{i,j=0}^\infty a'_{i,j}x^iy^j$

polinomokat ekvivalensnek, jelölésben $\displaystyle p\equiv p'$, ha megfelelő együtthatóik megegyeznek modulo 3, vagyis ha minden $\displaystyle (i,j)$ párra $\displaystyle a_{i,j}$ és $\displaystyle a'_{i,j}$ ugyanolyan maradékot ad 3-mal osztva. Például $\displaystyle (x+y)^3=x^3+3x^2y+3xy^2+y^3\equiv x^3+y^3$, vagyis $\displaystyle S(3)=2$. Némi meggondolást igényel annak igazolása, hogy ha $\displaystyle p\equiv p'$ és $\displaystyle q\equiv q'$, akkor $\displaystyle pq\equiv p'q'$ is fennáll. Ezért

$\displaystyle (x+y)^9=((x+y)^3)^3\equiv (x^3+y^3)^3\equiv x^9+y^9,$

és $\displaystyle k$ szerinti teljes indukcióval hasonlóképpen igazolható, hogy minden $\displaystyle k$ természetes számra

$\displaystyle (x+y)^{3^k}\equiv x^{3^k}+y^{3^k},$

tehát valóban $\displaystyle S(3^k)=2$. Innen leolvasható az is, hogy

$\displaystyle (x+y)^{2\cdot3^k}\equiv (x^{3^k}+y^{3^k})^2\equiv x^{2\cdot3^k}+ 2x^{3^k}y^{3^k}+y^{2\cdot3^k},$

vagyis $\displaystyle S(2\cdot3^k)=3$.

[] Ezek után nem nehéz $\displaystyle n$ szerinti teljes indukcióval belátni, hogy minden $\displaystyle n$ pozitív egészre $\displaystyle S(n)$ értéke $\displaystyle 2^a3^b$ alakú szám, következésképpen nem osztható $\displaystyle 5$-tel. Tegyük fel, hogy az $\displaystyle n$-nél kisebb pozitív egészekre az állítást már igazoltuk, és lássuk be, hogy akkor $\displaystyle n$-re is igaz. Ha az $\displaystyle n$ szám $\displaystyle 3^k$ vagy $\displaystyle 2\cdot 3^k$ alakú, akkor fentiek szerint készen is vagyunk. Ellenkező esetben $\displaystyle n=3^k+n'$ vagy $\displaystyle n=2\cdot 3^k+n'$, ahol $\displaystyle 1\le n'<3^k<n$. Az első esetben

$\displaystyle (x+y)^n=(x+y)^{3^k}(x+y)^{n'}\equiv (x^{3^k}+y^{3^k})(x+y)^{n'}= x^{3^k}(x+y)^{n'}+y^{3^k}(x+y)^{n'}.$

Mind az $\displaystyle x^{3^k}(x+y)^{n'}$, mind az $\displaystyle y^{3^k}(x+y)^{n'}$ polinomnak ugyanannyi 3-mal nem osztható együtthatójú tagja van, mint az $\displaystyle (x+y)^{n'}$ polinomnak, továbbá $\displaystyle n'<3^k$ miatt nem lehet olyan $\displaystyle x^iy^j$ tag, amelyik mindkét polinomban nemnulla együtthatóval szerepel. Ezért ebben az esetben $\displaystyle S(n)=2S(n')$. Hasonló megfontolás alapján a második esetben az $\displaystyle S(n)=3S(n')$ összefüggésre jutunk. Ha tehát állításunk $\displaystyle n'$-re igaz volt, akkor $\displaystyle n$-re is igaz lesz.

Statisztika:

19 dolgozat érkezett.
5 pontot kapott:	Ágoston Tamás, Damásdi Gábor, Éles András, Gyarmati Máté, Karl Erik Holter, Kiss 902 Melinda Flóra, Mester Márton, Mészáros András, Perjési Gábor, Réti Dávid, Somogyi Ákos, Weisz Ágoston, Weisz Gellért.
4 pontot kapott:	Bágyoni-Szabó Attila, Strenner Péter.
2 pontot kapott:	3 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2009. decemberi matematika feladatai