KöMaL - Középiskolai Matematikai és Fizikai Lapok
Sign In
Sign Up
 Magyar
Information
Contest
Journal
Articles

 

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 11 January 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.

Our web pages are supported by:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley