Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

A B. 5024. feladat értékelése még nem fejeződött be.


A KöMaL 2019. áprilisi matematika feladatai