Feladat: F.3131 Korcsoport: 18- Nehézségi fok: átlagos
Megoldó(k):  Gáspár Merse Előd ,  Gerbicz Róbert ,  Gueth Krisztián ,  Hajdufi Péter ,  Horváth Gábor ,  Juhász András ,  Juhász Zsófia ,  Laczó Tibor ,  Lázár Zsófia ,  Lippner Gábor ,  Naszvadi Péter ,  Németh András ,  Nyul Gábor ,  Pálfalvi Tamás ,  Prause István ,  Szűcs Gábor ,  Tar Zsolt ,  Terék Zsolt ,  Terpai Tamás ,  Varga Attila ,  Várkonyi Péter ,  Zábrádi Gergely 
Füzet: 1997/március, 162 - 163. oldal  PDF file
Témakör(ök): Számjegyekkel kapcsolatos feladatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):Feladatok: 1996/szeptember: F.3131

Hány olyan legfeljebb n-jegyű pozitív egész szám van, amelynek négyzete ugyanarra az n jegyre végződik (esetleg az elején néhány 0-val kiegészítve)?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

 
I. megoldás. A diszkusszió egyszerűsítése érdekében először nem-negatív egészekre oldjuk meg a feladatot (tehát megengedjük a 0-t is).
Teljes indukcióval bebizonyítjuk, hogy minden n pozitív egészre pontosan négy olyan nemnegatív egész létezik, amelynek négyzete ugyanarra az n darab számjegyre végződik, továbbá a négy szám közül kettő 0 és az 1, a másik két szám utolsó jegye 5, illetve 6.
Az n=1 esetben a kilenc egyjegyű számot végigvizsgálva láthatjuk, hogy közülük valóban az 1, 5 és 6 számok megfelelők.
Tegyük fel, hogy állításunk igaz n=k-ra; ebből belátjuk n=k+1 esetére is.
Keressük a számokat x=10ka+b alakban, ahol 0a9 az első számjegy, 0b<10k pedig az utolsó k számjegyből alkotott szám. Annak kell teljesülnie, hogy x és x2 utolsó k+1 jegye megegyezzék, vagyis
10k+1|x2-x=10k+110k-1a2+10k(2b-1)a+(b2-b).

A jobb oldalon álló három tag közül az első biztosan osztható 10k+1-nel, a második pedig 10k-nal. Ezért az utolsó tagnak, (b2-b)-nek oszthatónak kell lennie 10k-nal. Az indukciós feltevés szerint négy ilyen lehetséges b létezik.
Ahhoz, hogy a jobb oldal ne csak 10k-nal, hanem 10k+1-nel is osztható legyen, szükséges és elégséges, ha (2b-1)a+b2-b10k osztható 10-zel. Mivel 2b-1 mind a négy esetben relatív prím a 10-hez, pontosan egy-egy megfelelő a található hozzájuk. Tehát mind a négy lehetséges b érték egyértelműen egészíthető ki egy-egy megfelelő, legfeljebb (k+1)-jegyű számmá. Az is látható, hogy b=0 és b=1 esetén a=0 az új jegy, de a többi esetben is az utolsó számjegy megegyezik b utolsó jegyével.
Tehát tetszőleges n-re három megfelelő pozitív egész van.
 
II. megoldás. Legyen x egy olyan legfeljebb n-jegyű pozitív egész szám (azaz 0x<10n), amelyre x és x2 utolsó n jegye megegyezik, vagyis 10n=2n5nx2-x=x(x-1). Mivel x és x-1 relatív prímek, ez pontosan akkor teljesül, ha x és x-1 közül valamelyik osztható 2n-nel, és valamelyik (esetleg ugyanaz) osztható 5n-nel. Ez összesen 4 esetet jelent.
1. eset: 2nx és 5nx. Ekkor 10nx, ami ellentmond az x-re vonatkozó feltételnek. Ilyen x tehát nincs.
2. eset: 2nx és 5nx-1. Ekkor 10nx-1, ami x=1 esetén teljesül. Ez az eset tehát egy megoldást ad, az 1-et.
3. eset: 2nx-1 és 5nx. Ekkor x=k5n valamilyen 0<k<2n egész számmal. Mivel 2n és 5n relatív prímek, a 05n, 15n, 25n, ..., (2n-1)5n számok teljes maradékrendszert alkotnak modulo 2n, következésképpen pontosan egy olyan van közöttük, amely 2n-nel osztva 1 maradékot ad. Ez nem lehet a 0. Ez az eset is egyetlen x-re lehetséges.
4. eset: 2nx és 5nx-1. Ennek a vizsgálata a 3. esettel megegyezik, csak a 2n és 5n számokat kell felcserélnünk.
A 2., 3., 4. esetekben találtunk egy-egy megoldást; összesen tehát három olyan legfeljebb n-jegyű pozitív egész van, amelynek négyzete ugyanarra az n jegyre végződik.
 
Megjegyzések. 1. A két nem triviális megoldásra Terpai Tamás explicit képletet is adott: az egyik szám 52n-nek a 10n-nel való osztási maradéka, a másik szám pedig
10n-52n+1-nek a 10n-nel való osztási maradéka. Ennek oka az, hogy
(52n)2-52n=52n(52n-1+1)(52n-2+1)...(520+1)(520-1).
A bal oldalon szereplő 52n és az n+1 darab tényező miatt ez a szám osztható 10n-nel. (A másik számra a bizonyítás hasonló.)
2. Több versenyző nem foglalkozott a 0 esettel. Ők 4 pontot kaptak.