A B. 4757. feladat (2015. december)

B. 4757. Tízes számrendszerben a $\displaystyle k$ darab 1-esből álló számot jelölje $\displaystyle A_k$. Hány olyan pozitív egész szám van, amely nem állítható elő az $\displaystyle A_k$ valamely többszöröse számjegyeinek összegeként?

Javasolta: Williams Kada (Szeged, Radnóti M. Gimn.)

(6 pont)

A beküldési határidő 2016. január 11-én LEJÁRT.

Megoldás. Megmutatjuk, hogy pontosan azok az $\displaystyle s$ pozitív egész számok állnak elő, mint $\displaystyle A_k$ valamely (pozitív) többszörösében a számjegyek összege, amelyek felírhatók $\displaystyle s=k\alpha+9\beta$ alakban, ahol $\displaystyle \alpha\geq 1$ és $\displaystyle \beta\geq 0$ egész számok.

Először igazoljuk, hogy ezek a számjegyösszegek megkaphatók. Ehhez elég belátni, hogy ha $\displaystyle s$ megkapható, akkor $\displaystyle s+k$ és $\displaystyle s+9$ is megkapható. Tegyük fel tehát, hogy $\displaystyle A_k|n$ és $\displaystyle n$-ben a számjegyek összege $\displaystyle s$. Ha $\displaystyle n<10^N$, akkor $\displaystyle n'=n+10^N\cdot A_k$-ban a számjegyösszeg $\displaystyle s+9$ lesz, és $\displaystyle n'$ is osztható $\displaystyle A_k$-val. Legyen $\displaystyle n$ legnagyobb helyiértéken álló jegye $\displaystyle a$, és ez a helyiérték legyen $\displaystyle 10^M$. Ekkor legyen $\displaystyle n''=n-10^M+\sum\limits_{i=1}^{10}10^{M-1+ik}$. Az $\displaystyle n''$ szám számjegyeinek összege $\displaystyle s+9$, és $\displaystyle A_k|n''$, hiszen $\displaystyle A_k|10^k-1$.

Most belátjuk, hogy más számjegyösszeg nem áll elő. Legyen $\displaystyle n=\overline{a_M\dots a_1a_0}=\sum\limits_{i=0}^M a_i10^i$. Legyen $\displaystyle 0\leq j\leq k-1$ esetén $\displaystyle x_j=\sum\limits_{l\geq 0} a_{j+lk}$. Ekkor $\displaystyle A_k|10^k-1$ miatt $\displaystyle A_k|\sum\limits_{0\leq j\leq k-1} x_j10^j$. Azt szeretnénk belátni, hogy $\displaystyle \sum\limits_{0\leq j\leq k-1} x_j$ előáll $\displaystyle k\alpha+9\beta$ alakban. Ezt az $\displaystyle s=\sum\limits_{0\leq j\leq k-1} x_j$ számjegyösszeg szerinti indukcióval bizonyítjuk. Tegyük fel, hogy azokra az esetekre, amikor a számjegyösszeg kisebb $\displaystyle s$-nél már igazoltuk ezt, és az $\displaystyle A_k$-val osztható $\displaystyle n$ szám számjegyeinek összege $\displaystyle s$. Ha $\displaystyle \min (x_0,x_1,\dots,x_{k-1})\geq 1$, akkor $\displaystyle x_i'=x_i$ választással egy $\displaystyle k$-val kisebb összeget kapunk, és az így kapott $\displaystyle s'=s-k$-nek az indukciós feltevés miatt létezik a fenti előállítása, amihez $\displaystyle k$-t adva $\displaystyle s$ megfelelő előállítását kapjuk. Feltehető tehát, hogy az $\displaystyle x_i$ számok közül valamelyik 0. Ugyancsak $\displaystyle A_k|10^k-1$ miatt az $\displaystyle x_i$-ket ciklikusan permutálva a fenti oszthatósági feltétel továbbra is teljesül, így feltehetjük, hogy $\displaystyle x_{k-1}=0$. Továbbá, ha valamelyik $\displaystyle x_j$ értéke legalább 10, akkor az $\displaystyle x_j'=x_j-10, x_{j+1}'=x_{j+1}+1$ változtatással egy szintén $\displaystyle A_k$-val osztható számhoz tartozó összeget kapunk, amelyben a számjegyösszeg $\displaystyle s'=s-9$. Az $\displaystyle s'$ szám fenti előállításához még egy 9-est hozzáadva $\displaystyle s$ kívánt előállítását nyerjük. Feltehető tehát az is, hogy $\displaystyle x_0,x_1,\dots,x_{k-1}$ mindegyike legfeljebb 9. Ekkor viszont a $\displaystyle 0<\sum\limits_{j=0}^{k-2} x_j10^j<\sum\limits_{j=0}^{k-2} 10^{j+1}=A_k-1<A_k$ egyenlőtlenség ellentmondásra vezet, ugyanis ennek az összegnek ugyanannyi az $\displaystyle A_k$-s maradéka, mint $\displaystyle n$-nek. Ezzel az állításunkat igazoltuk.

Már csak azt kell megvizsgálnunk, hány olyan pozitív egész szám van, amely nem áll elő $\displaystyle k\alpha+9\beta$ alakban (ahol $\displaystyle \alpha\geq 1$ és $\displaystyle \beta\geq 0$ egész számok). Ha $\displaystyle 3|k$, akkor nyilván végtelen sok, hiszen csak 3-mal oszthatók állnak elő. A továbbiakban feltesszük, hogy $\displaystyle 3\nmid k$. Ekkor $\displaystyle 9$ és $\displaystyle k$ relatív prímek, így a $\displaystyle k,2k,3k,\dots,9k$ számok 9-es maradéka páronként különböző. Legyen $\displaystyle 1\leq i\leq 9$. Az $\displaystyle ik$ számmal azonos 9-es maradékot adó számok közül pontosan azoknak létezik a kívánt előállítása, amelyek felírhatók $\displaystyle ik+9\beta$ alakban (ahol $\displaystyle \beta\geq 0$), így ebből a maradékosztályból $\displaystyle \lfloor \frac{ik}{9} \rfloor$ nemnegatív egész szám marad ki. A kívánt alakban nem felírható nemnegatív egészek száma így

$\displaystyle \sum\limits_{i=1}^9 \left\lfloor \frac{ik}{9} \right\rfloor =\sum\limits_{i=1}^9 \frac{ik}{9} -\sum\limits_{i=1}^9 \left\{ \frac{ik}{9} \right\}=5k-\sum\limits_{j=0}^8 \frac{j}{9}=5k-4,$

hiszen a $\displaystyle \left\{ \frac{k}{9} \right\},\left\{ \frac{2k}{9} \right\},\dots,\left\{ \frac{9k}{9} \right\}$ számok a $\displaystyle \frac{0}{9},\frac{1}{9},\dots,\frac{8}{9}$ számok valamilyen sorrendben.

Tehát azoknak a pozitív egész számoknak a száma, amelyek nem állnak elő $\displaystyle A_k$ egy többszörösében a számjegyek összegeként $\displaystyle 5k-5$ (hiszen az előbb a 0-t is számoltuk), ha $\displaystyle 3\nmid k$ és végtelen, ha $\displaystyle 3\mid k$.

Statisztika:

39 dolgozat érkezett.
6 pontot kapott:	Baran Zsuzsanna, Borbényi Márton, Bukva Balázs, Csorba Benjámin, Czirkos Angéla, Döbröntei Dávid Bence, Gáspár Attila, Imolay András, Klász Viktória, Kovács 246 Benedek, Molnár-Sáska Zoltán, Nagy Dávid Paszkál, Nagy Kartal, Tóth Viktor.
5 pontot kapott:	Lajkó Kálmán, Matolcsi Dávid, Várkonyi Dorka.
4 pontot kapott:	4 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	8 versenyző.

A KöMaL 2015. decemberi matematika feladatai