A B. 5024. feladat (2019. április)

B. 5024. Legyen \(\displaystyle p\) egy páratlan prímszám. A \(\displaystyle \binom{p-2}{0}, \binom{p-2}{1}, \ldots, \binom{p-2}{p-2}\) számok mindegyikét maradékosan elosztjuk \(\displaystyle p\)-vel. Hányféle különböző maradékot kapunk?

Javasolta: Gyenes Zoltán és Hujter Bálint (Budapest)

(4 pont)

A beküldési határidő 2019. május 10-én LEJÁRT.

Megoldás. A megadott számok a Pascal-háromszög \(\displaystyle (p-2)\)-edik sorában elhelyezkedő binomiális együtthatók. Ismert, hogy a Pascal-háromszög \(\displaystyle p\)-edik sorában \(\displaystyle \binom{p}{0}=1\) és \(\displaystyle \binom{p}{p}=1\) kivételével minden szám osztható \(\displaystyle p\)-vel, ugyanis \(\displaystyle 0<i<p\) esetén \(\displaystyle \binom{p}{i}=\frac{p!}{i!(p-i)!}\) számlálója osztható a \(\displaystyle p\) prímmel, nevezője viszont nem (a hányados pedig egész szám).

Ez azt jelenti, hogy a \(\displaystyle p\)-edik sorban a számok \(\displaystyle p\)-es maradéka rendre:

\(\displaystyle 1,\underbrace{0,0,\dots,0}_{p-1},1.\)

Vizsgáljuk most a \(\displaystyle (p-1)\)-edik sorban lévő binomiális együtthatók \(\displaystyle p\)-es maradékát. Mivel \(\displaystyle \binom{p-1}{0}=1\) maradéka 1, így \(\displaystyle \binom{p-1}{1}\) maradéka \(\displaystyle p-1\) kell legyen, hiszen összegük, \(\displaystyle \binom{p-1}{0}+\binom{p-1}{1}=\binom{p}{1}\), osztható \(\displaystyle p\)-vel. Ugyanígy folytatva, és felhasználva, hogy \(\displaystyle p\)-edik sorban a két szélső számot leszámítva minden \(\displaystyle p\)-vel osztható, azt kapjuk, hogy a \(\displaystyle (p-1)\)-edik sorban a binomiális együtthatók \(\displaystyle p\)-es maradéka felváltva \(\displaystyle 1\) és \(\displaystyle p-1\):

\(\displaystyle \underbrace{1,p-1,1,p-1,\dots,1,p-1,1}_{(\text{összesen \(\displaystyle p\) db szám})}.\)

Ezután már (például) balról jobbra haladva meg tudjuk határozni a \(\displaystyle (p-2)\)-edik sorban lévő binomiális együtthatók \(\displaystyle p\)-es maradékát. Nyilván a \(\displaystyle \binom{p-2}{0}=1\) szám \(\displaystyle p\)-es maradéka 1, és \(\displaystyle \binom{p-2}{0}+\binom{p-2}{1}=\binom{p-1}{1}\) alapján a \(\displaystyle \binom{p-2}{1}\) szám \(\displaystyle p\)-es maradéka \(\displaystyle p-2\), hiszen olyan maradékot keresünk, amihez 1-et adva \(\displaystyle (p-1)\)-es maradékot kapunk.

Ezután \(\displaystyle \binom{p-2}{1}+\binom{p-2}{2}=\binom{p-1}{2}\) alapján \(\displaystyle \binom{p-1}{2}\) maradékának annyinak kell lennie, amihez \(\displaystyle (p-2)\)-t adva 1 maradékot kapunk, vagyis 3-nak. Ezt így folytatjuk, és mivel a \(\displaystyle (p-1)\)-edik sorban a maradék felváltva \(\displaystyle 1\) és \(\displaystyle p-1\), ezért a \(\displaystyle (p-2)\)-edik sorban a maradékok sorozata rendre a következő lesz:

\(\displaystyle \underbrace{1,p-2,3,p-4,4,p-5,\dots, p-(p-3),p-2,p-(p-1) }_{(\text{összesen \(\displaystyle p-1\) db szám})}.\)

Az itt előforduló maradékok éppen az 1 és \(\displaystyle p-2\) közötti páratlan számok, vagyis a Pascal-háromszög szimmetriája alapján tükrös helyzetben levőkön kívül (\(\displaystyle \binom{p-2}{i}=\binom{p-2}{p-2-i}\) a szimmetria alapján) nincs más egyezés.

Tehát az előforduló maradékok: \(\displaystyle 1,3,5,\dots,p-2\), melyek száma \(\displaystyle \frac{p-1}{2}\).

Statisztika:

51 dolgozat érkezett.
4 pontot kapott:	Argay Zsolt, Baski Bence, Beke Csongor, Bencsik Ádám, Bognár 171 András Károly, Csaplár Viktor, Farkas 512 Izabella, Farkas Boróka, Fraknói Ádám, Füredi Erik Benjámin, Geretovszky Anna, Gyetvai Miklós, Győrffi Ádám György, Hegedűs Dániel, Jánosik Áron, Kerekes Boldizsár, Kitschner Bernadett, Kovács 129 Tamás, Lovas Márton, Nagy 551 Levente, Nagy Nándor, Osztényi József, Rareș Polenciuc, Sárvári Tibor, Sebestyén Pál Botond, Soós 314 Máté, Szabó 991 Kornél, Szűcs 064 Tamás, Telek Zsigmond , Terjék András József, Tiderenczl Dániel, Tot Bagi Márton, Tóth 057 Bálint, Tóth 827 Balázs, Várkonyi Zsombor, Velich Nóra, Weisz Máté, Zsigri Bálint.
3 pontot kapott:	Bánó Bulcsú, Beinschroth Ninett, Jánosik Máté, Nguyen Bich Diep, Nyárfádi Patrik, Sándor Péter, Stomfai Gergely, Tóth Ábel.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2019. áprilisi matematika feladatai