 |
A B. 5212. feladat (2021. december) |
B. 5212. Igazoljuk, hogy létezik olyan pozitív egész szám, amely legalább 2021-féleképpen állítható elő úgy, hogy egy (tízes számrendszerben felírt) pozitív egész számhoz hozzáadjuk a számjegyeinek összegét.
Javasolta: Sándor Csaba (Budapest)
(6 pont)
A beküldési határidő 2022. január 10-én LEJÁRT.
Megoldás. Az \(\displaystyle n\) számra vonatkozó teljes indukcióval bizonyítjuk, hogy van olyan pozitív egész szám, ami legalább \(\displaystyle n\)-féleképpen áll elő egy pozitív egész szám és annak számjegyeinek összegeként. A \(\displaystyle k\) szám számjegyeinek összegét jelölje \(\displaystyle S(k)\).
Az \(\displaystyle n=1\) eset triviális, \(\displaystyle n=2\)-re a 101 megfelelő, hiszen \(\displaystyle k=91\) és \(\displaystyle k=100\) esetén egyaránt \(\displaystyle k+S(k)=101\).
Az indukciós lépést először \(\displaystyle 2\to 3\)-ra mutatjuk meg (ugyanez a módszer működni fog nagyobb \(\displaystyle n\)-re is). Mivel
\(\displaystyle 91+S(91)=100+S(100)=101,\)
ezért világos, hogy az
\(\displaystyle a:=\overline{1\underbrace{00\dots0}_{t}100}\)
és
\(\displaystyle b:=\overline{1\underbrace{00\dots0}_{t}091}\)
számokra
\(\displaystyle a+S(a)=b+S(b)=\overline{1\underbrace{00\dots0}_{t}102},\)
bárhogyan is választjuk meg \(\displaystyle t\) értékét. Keressünk egy
\(\displaystyle c:=\overline{\underbrace{99\dots9}_{t}99r}\)
alakú számot (itt \(\displaystyle r\) a \(\displaystyle c\) szám utolsó jegyét jelöli), melyre szintén
\(\displaystyle c+S(c)=\overline{1\underbrace{00\dots0}_{t}102}.\)
Ahhoz, hogy ez teljesüljön az kell, hogy \(\displaystyle 9(t+2)+r=(10-r)+102\), vagyis
\(\displaystyle 9(t+2)=112-2r\)
legyen. Az \(\displaystyle r\) számjegyet úgy kell megválasztani, hogy \(\displaystyle 9\mid 112-2r\) teljesüljön, \(\displaystyle r=2\) a megfelelő választás. Ekkor \(\displaystyle 9(t+2)=108\)-ból \(\displaystyle t=10\). Tehát a \(\displaystyle \overline{1\underbrace{00\dots0}_{10}102}=10\,000\,000\,000\,102\) szám háromféleképpen is előáll:
\(\displaystyle a=10\,000\,000\,000\,100,\)
\(\displaystyle b=10\,000\,000\,000\,091,\)
\(\displaystyle c=9\,999\,999\,999\,992\)
mellett
\(\displaystyle a+S(a)=b+S(b)=c+S(c)=10\,000\,000\,000\,102.\)
Most az általános indukciós lépést igazoljuk. Tegyük fel, hogy az \(\displaystyle a_1,a_2,\dots,a_n\) különböző számokra
\(\displaystyle s=a_1+S(a_1)=a_2+S(a_2)=\dots=a_n+S(a_n).\)
Az \(\displaystyle s\) szám jegyeinek száma legyen \(\displaystyle N\). Világos, hogy ha \(\displaystyle M>N\), akkor az \(\displaystyle a_i'=10^M+a_i\) számra
\(\displaystyle a_i'+S(a_i')=10^M+a_i+S(a_i)+1=10^M+s+1=:s'.\)
Az \(\displaystyle s'\) számnak tehát van \(\displaystyle n\) különböző előállítása \(\displaystyle a_i'+S(a_i')\) alakban, az összes \(\displaystyle a_i'\) szám 1-essel kezdődik. Megfelelő \(\displaystyle M\) mellett \(\displaystyle c=10^M-(10-r)\) alakban keresünk olyan számot, melyre szintén \(\displaystyle c+S(c)=s'\), ez egy \(\displaystyle (n+1)\)-edik előállítást szolgáltat majd, hiszen a \(\displaystyle c\) szám 9-essel kezdődik. Itt \(\displaystyle 1\leq r\leq 9\), és \(\displaystyle c\) az a szám, melynek utolsó jegye \(\displaystyle r\), a többi \(\displaystyle M-1\) jegye pedig 9-es, azaz \(\displaystyle S(c)=9(M-1)+r\). Tehát az
\(\displaystyle s'=10^M-(10-r)+9(M-1)+r\)
feltételnek kell teljesülnie, ami ekvivalens az
\(\displaystyle s=9(M-2)+2r-2\)
feltétellel. Válasszuk meg \(\displaystyle 1\leq r\leq 9\) értékét úgy, hogy \(\displaystyle 9\mid s-2r+2\) legyen, és legyen
\(\displaystyle M:=\frac{s-2r+2}{9}+2.\)
Mivel a \(\displaystyle 2,4,6,8,10,12,14,16,18\) számok 9-es maradéka páronként különböző, ezért \(\displaystyle r\)-re pontosan egy megfelelő választás van.
Ezzel az indukciós lépést igazoltuk.
Ebből tehát következik, hogy olyan szám is van, melynek legalább 2021-féle előállítása is van.
Megjegyzés. Az indukciós lépés valójában \(\displaystyle n=1\)-ről \(\displaystyle n=2\)-re is működik. \(\displaystyle a_1=1\) mellett \(\displaystyle s=a_1+S(a_1)=2\), vagyis \(\displaystyle N=1\). Ekkor \(\displaystyle 1<M\)-re \(\displaystyle s'=10^M+1+S(10^M+1)=10^M+3\), és \(\displaystyle c\)-t \(\displaystyle c=10^M-(10-r)\) alakban keressük. \(\displaystyle 9\mid s-2r+2=4-2r\) akkor teljesül, ha \(\displaystyle r=2\). Ekkor \(\displaystyle M=\frac{s-2r+2}{9}+2=2\), vagyis \(\displaystyle c=100-8=92\). Ekkor \(\displaystyle 101+S(101)=92+S(92)=103\).
Statisztika:
42 dolgozat érkezett. 6 pontot kapott: Bálint Béla, Baski Bence, Ben Gillott, Bencsik Dávid, Bencz Benedek, Bényei Borisz, Bognár 171 András Károly, Chrobák Gergő, Csonka Illés, Diaconescu Tashi, Duchon Márton, Foris Dávid, Fülöp Csilla, Han Ziying, Jánosik Máté, Kalocsai Zoltán, Lovas Márton, Melján Dávid Gergő, Molnár István Ádám, Móricz Benjámin, Németh Márton, Nguyen Kim Dorka, Rareș Polenciuc, Sági Mihály, Sebestyén József Tas, Simon László Bence, Szabó 810 Levente, Szanyi Attila, Tarján Bernát, Tran Dávid, Varga Boldizsár, Virág Rudolf, Wiener Anna, Zömbik Barnabás. 5 pontot kapott: Juhász-Molnár Erik. 4 pontot kapott: 3 versenyző. 3 pontot kapott: 2 versenyző. 0 pontot kapott: 1 versenyző. Nem versenyszerű: 1 dolgozat.
A KöMaL 2021. decemberi matematika feladatai