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!

tehetseg.hu

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 on 10 March 2010.


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

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

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

&tex;\displaystyle (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}.&xet;

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

&tex;\displaystyle \frac{(p-1)!}{1},\frac{(p-1)!}{2},\ldots,\frac{(p-1)!}{p-1}&xet;

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

&tex;\displaystyle (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}.&xet;

Ezért

&tex;\displaystyle (kp+1)(kp+2)\ldots(kp+p-1)\equiv (p-1)!\pmod{p^2},&xet;

ahonnan

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

Ennek alapján pedig

&tex;\displaystyle \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=&xet;

&tex;\displaystyle =(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}.&xet;

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

&tex;\displaystyle \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},&xet;

ha pedig a &tex;\displaystyle p&xet; prím &tex;\displaystyle 6k-1&xet; alakú, akkor

&tex;\displaystyle \frac{(p+1)(p+2)}{6}=\frac{(6k)(6k+1)}{6}=6k^2+k=kp+2k\equiv \frac{p+1}{3}\pmod{p}.&xet;

Tehát annak megfelelően, hogy a &tex;\displaystyle p&xet; prím 6-tal osztva 1 vagy 5 maradékot ad, az utolsó két számjegy &tex;\displaystyle \frac{2p+1}{3}&xet; és 0, illetőleg &tex;\displaystyle \frac{p+1}{3}&xet; é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