Problem B. 5328. (September 2023)
B. 5328. The number 2023 is written on the first page of a notebook. On every following page, the positive divisors of the numbers on the previous page are written (each divisor is written down \(\displaystyle n\) times if it divides \(\displaystyle n\) numbers on the previous page). How many numbers will there be on page 4?
Proposed by P.\(\displaystyle \,\)P. Pach, Budapest
(3 pont)
Deadline expired on October 10, 2023.
Sorry, the solution is available only in Hungarian. Google translation
1. megoldás. (A megoldás során osztó alatt végig pozitív osztót értünk.) A 4. lapon a 2023 osztóinak az osztóinak az osztói lesznek felsorolva, mindegyik olyan multiplicitással, ahányféleképpen megkaphatjuk. Az 5. lapon lévő 1-esek száma megegyezik a 4. lapon lévő számok számával (hiszen az 1 mindegyiknek osztója). Az 5. lapon lévő osztók száma pedig éppen a \(\displaystyle d_0=1\mid d_1\mid d_2\mid d_3\mid 2023=d_4\) osztóláncok száma. A 2023 prímtényezős felbontása \(\displaystyle 2023=7\cdot 17^2\). Tekintsük az osztóláncon belül a 7 és a 17 kitevőjét. A 7 kitevője az 1-ben 0, a 2023-ban 1, és végig monoton növekedő, így a \(\displaystyle d_0\), \(\displaystyle d_1\), \(\displaystyle d_2\), \(\displaystyle d_3\), \(\displaystyle d_4\) sorozatban négy helyen jelenhet meg először a 7-es tényező: \(\displaystyle d_1\), \(\displaystyle d_2\), \(\displaystyle d_3\), \(\displaystyle d_4\). A 17 kitevője az 1-ben 0, a 2023-ban 2, és szintén végig monoton növekedő. Két eset lehetséges:
- vagy egy darabig 17-tel nem oszthatóak, majd egy idő után \(\displaystyle 17^2\)-tel oszthatóak (ez esetben a \(\displaystyle 17^2\) megjelenése \(\displaystyle d_1\), \(\displaystyle d_2\), \(\displaystyle d_3\), \(\displaystyle d_4\) bármelyikében lehet);
- vagy van legalább egy olyan elem is, ami 17-tel osztható, de \(\displaystyle 17^2\)-nel nem (ez esetben az első és a második \(\displaystyle 17\)-es tényező megjelenése \(\displaystyle d_1\), \(\displaystyle d_2\), \(\displaystyle d_3\), \(\displaystyle d_4\) közül két helyen lehet).
Tehát a két 17-es tényezők megjelenése összesen \(\displaystyle 4+\binom{4}{2}=4+6=10\)-féleképpen lehet.
A osztóláncot egyértelműen meghatározza, hogy a 7 és a 17 kitevője hogyan alakul a sorozatban, így a megfelelő osztóláncok száma \(\displaystyle 4\cdot 10=40\). Tehát az ötödik lapon 40 darab 1-es lesz, és így a negyedik lapon 40 darab osztó lesz.
2. megoldás. Mivel \(\displaystyle 2023=7\cdot 17^2\), így mindegyik lapon az \(\displaystyle 1\), \(\displaystyle 17\), \(\displaystyle 17^2\), \(\displaystyle 7\), \(\displaystyle 7\cdot 17\), \(\displaystyle 7\cdot 17^2\) számok fognak szerepelni. Jelölje rendre \(\displaystyle a_i\), \(\displaystyle b_i\), \(\displaystyle c_i\), \(\displaystyle d_i\), \(\displaystyle e_i\), \(\displaystyle f_i\) azt, hogy az \(\displaystyle i\)-edik lapon melyikük hányszor szerepel. A feltétel szerint
\(\displaystyle a_1=b_1=c_1=d_1=e_1=0,\quad f_1=1,\)
és a feladatban írtak szerint a következő rekurziók érvényesek \(\displaystyle i\geq 1\) esetén:
$$\begin{align*} a_{i+1} &=a_i+b_i+c_i+d_i+e_i+f_i,\\ b_{i+1} &=b_i+c_i+e_i+f_i,\\ c_{i+1} &=c_i+f_i,\\ d_{i+1} &=d_i+e_i+f_i,\\ e_{i+1} &=e_i+f_i,\\ f_{i+1} &=f_i. \end{align*}$$A rekurziót használva:
\(\displaystyle a_2=1, \quad b_2=1, \quad c_2=1, \quad d_2=1, \quad e_2=1, \quad f_2=1,\)
\(\displaystyle a_3=6, \quad b_3=4, \quad c_3=2, \quad d_3=3, \quad e_3=2, \quad f_3=1,\)
\(\displaystyle a_4=18, \quad b_4=9, \quad c_4=3, \quad d_4=6, \quad e_4=3, \quad f_4=1.\)
A negyedik lapon tehát \(\displaystyle a_4+b_4+c_4+d_4+e_4+f_4=18+9+3+6+3+1=40\) osztó lesz.
Statistics:
235 students sent a solution. 3 points: 125 students. 2 points: 43 students. 1 point: 20 students. 0 point: 17 students. Not shown because of missing birth date or parental permission: 23 solutions.
Problems in Mathematics of KöMaL, September 2023