KöMaL - Mathematical and Physical Journal for Secondary Schools
Hungarian version Information Contest Journal Articles News
Conditions
Entry form to the contest
Problems and solutions
Results of the competition
Problems of the previous years

 

 

Order KöMaL!

Ericsson

Google

Emberi Erőforrások Minisztériuma

Emberi Erőforrás Támogatáskezelő

Oktatáskutató és Fejlesztő Intézet

ELTE

Competitions Portal

B. 4251. Let p>3 be a prime number. Determine the last two digits of the number


\sum_{i=1}^{p} \binom{i\cdot p}{p}\cdot\binom{(p-i+1)p}{p}

written in base-p numeral system.

(Based on the idea of G. Mészáros, Kemence)

(5 points)

Deadline expired.


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

A megoldáshoz szükségünk lesz a következő észrevételre: ha két p-vel nem osztható egész szám p-vel osztva ugyanannyi maradékot ad, a hányadosuk pedig egész szám, akkor az p-vel osztva 1 maradékot ad. Vagyis, ha az a,b,x egész számokra ax\equiv b\pmod{p} és a\equiv b\not\equiv0\pmod{p}, akkor x\equiv 1\pmod{p}. Ugyanis ha a(x-1)=ax-a osztható p-vel, akkor x-1 is osztható kell legyen p-vel. Ugyanígy látható, hogy ha a nem osztható p-vel, akkor c_1\not\equiv c_2\pmod{p} esetén ac_1\not\equiv ac_2\pmod{p}. Ugyanezek az állítások akkor is igazak maradnak, ha p-vel nem osztható számok esetén a maradékokat modulo p2 tekintjük.

Legyen most k tetszőleges nemnegatív egész szám. Ekkor a (kp+1)(kp+2)\ldots(kp+p-1) szorzatot teljesen kibontva, abban majdnem minden tag osztható lesz p2-tel, vagyis

(kp+1)\ldots(kp+p-1)\equiv (p-1)!+
kp(p-1)!\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{p-1}\right)\pmod{p^2}.

Mivel (p-1)! nem osztható p-vel, és az 1,2,\ldots,p-1 számok p-vel osztva mind különböző maradékot adnak, azért a p-vel nem osztható

\frac{(p-1)!}{1},\frac{(p-1)!}{2},\ldots,\frac{(p-1)!}{p-1}

számok is mind különböző maradékot adnak, vagyis

(p-1)!\left(\frac{1}{1}+\frac{1}{2}+\ldots+\frac{1}{p-1}\right)\equiv
1+2+\ldots+(p-1)\equiv 0\pmod{p}.

Ezért

 (kp+1)(kp+2)\ldots(kp+p-1)\equiv (p-1)!\pmod{p^2},

ahonnan

{{(k+1)p}\choose{p}}
={\frac{(k+1)p}{p}}\cdot{{kp+p-1}\choose{p-1}}\equiv k+1\pmod{p^2}.

Ennek alapján pedig

\sum_{i=1}^{p} {{ip}\choose{p}}\cdot{{(p-i+1)p}\choose{p}}
\equiv\sum_{i=1}^p i(p+1-i)=(p+1)\sum_{i=1}^pi-\sum_{i=1}^pi^2=

=(p+1)\cdot\frac{p(p+1)}{2}-\frac{p(p+1)(2p+1)}{6}=p\cdot\frac{(p+1)(p+2)}{6}
\pmod{p^2}.

A p>3 feltétel miatt (p+1)(p+2) osztható 6-tal. Innen látszik, hogy a szám maga p-vel osztható, vagyis p alapú számrendszerben az utolsó számjegy 0. Az utolsó előtti számjegy meghatározásához azt kell megnézni, hogy a \frac{(p+1)(p+2)}{6} szám milyen maradékot ad p-vel osztva. Ha p 6-tal osztva 1 maradékot ad, vagyis alkalmas k pozitív egész számmal p=6k+1, akkor

\frac{(p+1)(p+2)}{6}=\frac{(6k+2)(6k+3)}{6}=6k^2+5k+1=pk+4k+1
\equiv \frac{2p+1}{3}\pmod{p},

ha pedig a p prím 6k-1 alakú, akkor

\frac{(p+1)(p+2)}{6}=\frac{(6k)(6k+1)}{6}=6k^2+k=kp+2k\equiv 
\frac{p+1}{3}\pmod{p}.

Tehát annak megfelelően, hogy a p prím 6-tal osztva 1 vagy 5 maradékot ad, az utolsó két számjegy \frac{2p+1}{3} és 0, illetőleg \frac{p+1}{3} és 0.


Statistics on problem B. 4251.
19 students sent a solution.
5 points:Ágoston Tamás, Cséke Balázs, Damásdi Gábor, Éles András, Janzer Olivér, Kovács 729 Gergely, Márkus Bence, Mester Márton, Perjési Gábor, Somogyi Ákos, Strenner Péter, Szabó 928 Attila, Weisz Ágoston, Weisz Gellért, Zsakó András.
4 points:Mészáros András, Nagy Balázs, Nagy Róbert.
3 points:1 student.


  • Problems in Mathematics of KöMaL, February 2010

  • Our web pages are supported by: Ericsson   Google   SzerencsejátĂ©k Zrt.   Emberi ErĹ‘források MinisztĂ©riuma   Emberi ErĹ‘forrás TámogatáskezelĹ‘   OktatáskutatĂł Ă©s FejlesztĹ‘ IntĂ©zet   ELTE   Nemzeti TehetsĂ©g Program