Kezdőlap


Feladat:	B.3504	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Antal Ágnes , Kovács Péter , Zavarkó Gábor
Füzet:	2002/május, 287 - 289. oldal		PDF \| MathML
Témakör(ök):	Teljes indukció módszere, Számjegyekkel kapcsolatos feladatok, Feladat
Hivatkozás(ok):	Feladatok: 2001/december: B.3504

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. Írjuk fel $U_{k}^{2}$ -et annak alapján, ahogyan az írásbeli szorzást elvégezzük. Ennek során $k^{2}$ darab 1-est írunk le, $k$ sor mindegyikében $k$ darabot, soronként egy helyiértékkel eltolva. $S (U_{k}^{2})$ kiszámításakor oszloponként összeadjuk a felírt 1-eseket, majd az átvitelek figyelembevételével kapott számjegyeket összegezzük.
$S {(U_{k})}^{2} = k^{2}$ kiszámításakor soronként adjuk össze az 1-eseket, majd az így kapott $k$ darab összeg ‐ mindegyikük értéke $k$ ‐ összegét vesszük.
A különbséget az esetleges átvitelek okozzák, az első esetben ilyenkor az adott oszlopban lévő egyesek összege helyett ennek az összegnek csak az egyes helyiértéken lévő részét írjuk le, az összeg további részének $\frac{1}{10}$ -ét a következő helyiértéken álló számhoz adjuk.
Ilyen veszteség minden egyes átvitel során föllép, átvitelre pedig akkor kerül sor, ha van olyan oszlop, ahol legalább tíz darab 1-es áll, vagyis a $k$ értéke legalább 10. Ekkor tehát $S (U_{k}^{2}) < S {(U_{k})}^{2}$ . Ha viszont $k \leq 9$ , akkor éppen a fenti gondolatmenet mutatja, hogy ugyanazt a $k^{2}$ mennyiséget számoljuk ki oszloponként, illetve soronként, tehát ekkor $S (U_{k}^{2}) = S {(U_{k})}^{2}$ .

Kovács Péter (Debrecen, DE Kossuth Lajos Gyakorló Gimn., 8. évf.)

II. megoldás. A

k

darab 1-essel felírt szám jegyeinek az összege,

S (U_{k}) = k

, azért a feltétel az

S (U_{k}^{2}) = k^{2}

alakot ölti. Vizsgáljuk meg, hogy hány jegye van

U_{k}^{2}

-nek. Mivel

10^{k - 1} < U_{k} < 2 \cdot 10^{k - 1}

, azért

10^{2 k - 2} < U_{k}^{2} < 4 \cdot 10^{2 k - 2} < 10^{2 k - 1}

és így

U_{k}^{2}

jegyeinek száma

2 k - 1

. Innen felső becslést kaphatunk

S (U_{k}^{2})

értékére: mivel egy számjegy legfeljebb 9, így

S (U_{k}^{2}) \leq 9 (2 k - 1)

. Ez azt jelenti, hogy a megfelelő

k

értékekre

\begin{matrix} k^{2} = S {(U_{k})}^{2} = S (U_{k}^{2}) \leq 9 (2 k - 1) < 18 k, \end{matrix}

azaz

k < 18

.
Így öszesen 17 esetet kell megvizsgálnunk, ezeket egyenként végignézve kapjuk, hogy ha

1 \leq k \leq 9

, akkor teljesül a feltétel, ha pedig

10 \leq k \leq 17

, akkor

S (U_{k}^{2}) < S {(U_{k})}^{2}

. A megfelelő értékeket az alábbi táblázat tartalmazza:

\begin{matrix} k & S {(U_{k})}^{2} = k^{2} & S (U_{k}^{2}) \\ 1 & 1 & 1 \\ 2 & 4 & 4 \\ 3 & 9 & 9 \\ 4 & 16 & 16 \\ 5 & 25 & 25 \\ 6 & 36 & 36 \\ 7 & 49 & 49 \\ 8 & 64 & 64 \\ 9 & 81 & 81 \\ 10 & 100 & 82 \\ 11 & 121 & 85 \\ 12 & 144 & 90 \\ 13 & 169 & 97 \\ 14 & 196 & 106 \\ 15 & 225 & 117 \\ 16 & 256 & 130 \\ 17 & 289 & 145 \end{matrix}

Zavarkó Gábor (Miskolc, Földes Ferenc Gimn., 12. évf.)

Megjegyzés. Némi ügyeskedéssel tovább korlátozható a ,,kézzel'' ellenőrzött

k

értékek száma. Backhausz Ágnes, a budapesti Fazekas Mihály Gimnázium 11. osztályos tanulója a következőképpen okoskodott:
Az

U_{n + k} = U_{k} + 10^{k} U_{n}

azonosságból következik, hogy

\begin{matrix} U_{n + k}^{2} = U_{k}^{2} + 2 \cdot 10^{k} U_{k} U_{n} + 10^{2 k} U_{n}^{2} . \end{matrix}

Ez azt jelenti, hogy

U_{n + k}^{2}

és

U_{k}^{2}

utolsó

k

számjegye egyenlő. Kiszámolva

U_{12}^{2}

értékét az utolsó 12 számjegy

320 987 654 321

, ezek összege pedig 50. Ez azt jelenti, hogy ha

k \geq 12

, akkor

U_{k}^{2} = ... 320 987 654 321

alakú, ebben az esetben pedig a

(2 k - 1)

-jegyű

U_{k}^{2}

jegyeinek az összege legfeljebb

50 + (2 k - 1 - 12) \cdot 9 = 18 k - 67

. Innen az

S {(U_{k})}^{2} = S (U_{k}^{2})

fennállásához szükséges

k^{2} \leq 18 k - 67

feltételt kapjuk, ahonnan

k < 13

adódik. Ez pedig azt jelenti, hogy a feladat feltétele nem teljesülhet, ha

k \geq 13

III. megoldás. Ha

a

és

b

nemnegatív egészek, akkor az összeadás algoritmusa következményeként kapjuk, hogy

\begin{matrix} S (a + b) \leq S (a) + S (b) . \end{matrix}

(1)

Mivel

U_{k} = 10 U_{k - 1} + 1

, ezért

U_{k}^{2} = 100 U_{k - 1}^{2} + 20 U_{k - 1} + 1

. Innen (1) felhasználásával

\begin{matrix} \begin{matrix} S (U_{k}^{2}) & \leq S (100 U_{k - 1}^{2}) + S (20 U_{k - 1}) + 1 = S (U_{k - 1}^{2}) + S (2 U_{k - 1}) + 1 = \\ = S (U_{k - 1}^{2}) + 2 (k - 1) + 1, \end{matrix} \end{matrix}

azaz

\begin{matrix} S (U_{k}^{2}) \leq S (U_{k - 1}^{2}) + 2 k - 1. \end{matrix}

(2)

Innen egyrészt a

k

-ra vonatkozó teljes indukcióval nyomban adódik, hogy

\begin{matrix} S (U_{k}^{2}) \leq k^{2} . \end{matrix}

(3)

Másrészt ha egy adott

k

-ra

S (U_{k}^{2}) = k^{2}

, akkor (2) szerint

\begin{matrix} k^{2} = S (U_{k}^{2}) \leq S (U_{k - 1}^{2}) + 2 k - 1, \end{matrix}

azaz

S (U_{k - 1}^{2}) \geq k^{2} - 2 k + 1 = {(k - 1)}^{2}

, amit (3)-mal egybevetve

\begin{matrix} S (U_{k - 1}^{2}) = {(k - 1)}^{2} . \end{matrix}

Ez azt jelenti, hogy ha van olyan

k_{0}

, amelyre (3)-ban egyenlőség teljesül, akkor ugyanez minden

k < k_{0}

esetén is igaz.
Hasonlóan kapjuk (2) fölhasználásával, hogy ha van olyan

k_{0}

, amelyre (3)-ban határozott egyenlőtlenség áll, akkor ugyanez minden

k > k_{0}

esetén is teljesül.
Ha kiszámoljuk, akkor

S (U_{9}^{2}) = 9^{2}

és

S (U_{10}^{2}) = 82 < 10^{2}

. A fentiek szerint ez azt jelenti, hogy

\begin{matrix} S (U_{k}^{2}) = S {(U_{k})}^{2}, ha 1 \leq k \leq 9 és S (U_{k}^{2}) < S {(U_{k})}^{2}, ha 10 \leq k . \end{matrix}

Antal Ágnes (Budapest, Apáczai Csere János Gimn., 12. évf.)