KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 11 January 2010.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4231.
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

  • Támogatóink:   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