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