Problem B. 5024. (April 2019)

B. 5024. Let \(\displaystyle p\) denote an odd prime. If each of the numbers \(\displaystyle \binom{p-2}{0}, \binom{p-2}{1}, \ldots, \binom{p-2}{p-2}\) are divided by \(\displaystyle p\), how many different remainders are obtained?

Proposed by Z. Gyenes and B. Hujter, Budapest

(4 pont)

Deadline expired on May 10, 2019.

Sorry, the solution is available only in Hungarian. Google translation

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}\).

Statistics:

51 students sent a solution.
4 points:	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 points:	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 points:	2 students.
1 point:	2 students.
0 point:	1 student.

Problems in Mathematics of KöMaL, April 2019