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