Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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