Problem B. 4231. (December 2009)
B. 4231. Show that the number of terms with coefficients not divisible by 3 in the binomial expansion of (x+y)n is not divisible by 5.
(5 pont)
Deadline expired on January 11, 2010.
Sorry, the solution is available only in Hungarian. Google translation
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.
Statistics:
19 students sent a solution. 5 points: Á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 points: Bágyoni-Szabó Attila, Strenner Péter. 2 points: 3 students. 0 point: 1 student.
Problems in Mathematics of KöMaL, December 2009