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  |  MathML
Témakör(ök):	Számjegyekkel kapcsolatos feladatok, Teljes indukció módszere, Feladat
Hivatkozás(ok):	Feladatok: 1996/szeptember: F.3131

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={10}^k\cdot a+b$ alakban, ahol $0\le a\le 9$ az első számjegy, $0\le b<{10}^k$ pedig az utolsó $k$ számjegyből alkotott szám. Annak kell teljesülnie, hogy $x$ és $x^2$ utolsó $k+1$ jegye megegyezzék, vagyis $\begin{array}{c}{\displaystyle {10}^{k+1}|x^2-x={10}^{k+1}{10}^{k-1}{a}^2+{10}^k\cdot \left(2b-1\right)a+\left(b^2-b\right)\mathrm{.}}\end{array}$ A jobb oldalon álló három tag közül az első biztosan osztható ${10}^{k+1}$-nel, a második pedig ${10}^k$-nal. Ezért az utolsó tagnak, $\left(b^2-b\right)$-nek oszthatónak kell lennie ${10}^k$-nal. Az indukciós feltevés szerint négy ilyen lehetséges $b$ létezik. Ahhoz, hogy a jobb oldal ne csak ${10}^k$-nal, hanem ${10}^{k+1}$-nel is osztható legyen, szükséges és elégséges, ha $\left(2b-1\right)a+\frac{b^2-b}{{10}^k}$ 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 $\left(k+1\right)$-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 $0\le x<{10}^n$), amelyre $x$ és $x^2$ utolsó $n$ jegye megegyezik, vagyis ${10}^n=2^n\cdot 5^n\mid x^2-x=x\left(x-1\right)$. Mivel $x$ és $x-1$ relatív prímek, ez pontosan akkor teljesül, ha $x$ és $x-1$ közül valamelyik osztható $2^n$-nel, és valamelyik (esetleg ugyanaz) osztható $5^n$-nel. Ez összesen 4 esetet jelent. 1. eset: $2^n\mid x$ és $5^n\mid x$. Ekkor ${10}^n\mid x$, ami ellentmond az $x$-re vonatkozó feltételnek. Ilyen $x$ tehát nincs. 2. eset: $2^n\mid x$ és $5^n\mid x-1$. Ekkor ${10}^n\mid x-1$, ami $x=1$ esetén teljesül. Ez az eset tehát egy megoldást ad, az 1-et. 3. eset: $2^n\mid x-1$ és $5^n\mid x$. Ekkor $x=k\cdot 5^n$ valamilyen $0<k<2^n$ egész számmal. Mivel $2^n$ és $5^n$ relatív prímek, a $0\cdot 5^n$, $1\cdot 5^n$, $2\cdot 5^n$, $\text{...}$, $\left(2^n-1\right)\cdot 5^n$ számok teljes maradékrendszert alkotnak modulo $2^n$, következésképpen pontosan egy olyan van közöttük, amely $2^n$-nel osztva 1 maradékot ad. Ez nem lehet a 0. Ez az eset is egyetlen $x$-re lehetséges. 4. eset: $2^n\mid x$ és $5^n\mid x-1$. Ennek a vizsgálata a 3. esettel megegyezik, csak a $2^n$ és $5^n$ 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 $5^{2^n}$-nek a ${10}^n$-nel való osztási maradéka, a másik szám pedig ${10}^n-5^{2^n}+1$-nek a ${10}^n$-nel való osztási maradéka. Ennek oka az, hogy $\begin{array}{c}{\displaystyle {\left(5^{2^n}\right)}^2-5^{2^n}=5^{2^n}\left(5^{2^{n-1}}+1\right)\left(5^{2^{n-2}}+1\right)\text{...}\left(5^{2^0}+1\right)\left(5^{2^0}-1\right)\mathrm{.}}\end{array}$ A bal oldalon szereplő $5^{2^n}$ és az $n+1$ darab tényező miatt ez a szám osztható ${10}^n$-nel. (A másik számra a bizonyítás hasonló.) 2. Több versenyző nem foglalkozott a 0 esettel. Ők 4 pontot kaptak.