 |
A B. 5206. feladat (2021. december) |
B. 5206. Egy \(\displaystyle n\)-jegyű \(\displaystyle \overline{a_1a_2a_3\ldots a_n}\) számot hegyszerűnek nevezünk, ha van olyan \(\displaystyle 1 \le k \le n\) egész, amelyre \(\displaystyle a_1,a_2,\ldots,a_k\) szigorúan monoton növekvő, míg \(\displaystyle a_k,a_{k+1},\ldots,a_n\) szigorúan monoton csökkenő sorozat. (Például az 1, 121, 1231 számok hegyszerűek, de az 1442 és az 12313 nem hegyszerűek.) Hány hegyszerű szám van?
(3 pont)
A beküldési határidő 2022. január 10-én LEJÁRT.
Megoldás. Számoljuk össze a (pozitív) hegyszerű számokat a legnagyobb jegyük szerint. Ha a legnagyobb jegy \(\displaystyle t\) (melyre \(\displaystyle 1\leq t\leq 9\)), akkor tudjuk, hogy \(\displaystyle t\) pontosan 1-szer szerepel, \(\displaystyle t\)-n kívül pedig csak a \(\displaystyle 0,1,\dots,t-1\) jegyek fordulhatnak elő. Ha a \(\displaystyle t\)-től balra (vagyis nagyobb helyiértéken) szereplő jegyek nagyságsorrendben \(\displaystyle b_1<\dots<b_i\) és a \(\displaystyle t\)-től jobbra (kisebb helyiértéken) szereplő jegyek \(\displaystyle c_1<\dots<c_j\), akkor a szám \(\displaystyle \overline{b_1\dots b_i t c_j \dots c_1}\), speciálisan, \(\displaystyle t\)-től balra nem szerepelhet a 0 (vagyis \(\displaystyle b_1\ne 0\)), mert 0-val nem kezdődhet a szám. Tehát elég ismernünk, mely jegyek szerepelnek \(\displaystyle t\)-től balra, és melyek \(\displaystyle t\)-től jobbra, ez a két halmaz már egyértelműen meghatározza a hegyszerű számot. Az \(\displaystyle 1,2,\dots,t-1\) tetszőleges részhalmaza szerepelhet \(\displaystyle t\)-től balra, és a \(\displaystyle 0,1,2,\dots,t-1\) tetszőleges részhalmaza szerepelhet \(\displaystyle t\)-től jobbra, így a lehetőségek száma \(\displaystyle 2^{t-1}2^t=2^{2t-1}\). Ezt \(\displaystyle t\) szerint összegezve:
\(\displaystyle \sum\limits_{t=1}^9 2^{2t-1}=2(1+4+4^2+\dots+4^8)=2\cdot \frac{4^9-1}{4-1}=174\,762.\)
Tehát \(\displaystyle 174\,762\) (pozitív) hegyszerű szám van.
Ha a \(\displaystyle 0=\overline{0}\)-t is számoljuk, akkor pedig ennél 1-gyel több, vagyis \(\displaystyle 174\,763\).
Statisztika:
112 dolgozat érkezett. 3 pontot kapott: 74 versenyző. 2 pontot kapott: 11 versenyző. 1 pontot kapott: 17 versenyző. 0 pontot kapott: 5 versenyző. Nem versenyszerű: 4 dolgozat.
A KöMaL 2021. decemberi matematika feladatai