Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 5206. (December 2021)

B. 5206. An \(\displaystyle n\)-digit number \(\displaystyle \overline{a_1a_2a_3\ldots a_n}\) is called hill type if there exists an integer \(\displaystyle 1 \le k \le n\) for which the sequence \(\displaystyle a_1,a_2,\ldots,a_k\) is strictly increasing and the sequence \(\displaystyle a_k,a_{k+1},\ldots,a_n\) is strictly decreasing. (For example, the numbers 1, 121, 1231 are of hill type, whereas 1442 or 12313 are not.) How many hill type numbers are there?

(3 pont)

Deadline expired on January 10, 2022.


Sorry, the solution is available only in Hungarian. Google translation

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\).


Statistics:

112 students sent a solution.
3 points:74 students.
2 points:11 students.
1 point:17 students.
0 point:5 students.
Unfair, not evaluated:4 solutionss.

Problems in Mathematics of KöMaL, December 2021