 |
A B. 5328. feladat (2023. szeptember) |
B. 5328. Egy füzet első lapjára leírtuk a 2023 számot. Ezután a következő lapra mindig az előzőn lévő számok pozitív osztóit írjuk le (mindegyiket annyiszor, ahány számnak osztója az előző lapról). Hány szám lesz a 4. lapon?
Javasolta: Pach Péter Pál, Budapest
(3 pont)
A beküldési határidő 2023. október 10-én LEJÁRT.
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.
Statisztika:
235 dolgozat érkezett. 3 pontot kapott: 125 versenyző. 2 pontot kapott: 43 versenyző. 1 pontot kapott: 20 versenyző. 0 pontot kapott: 18 versenyző. Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt: 22 dolgozat.
A KöMaL 2023. szeptemberi matematika feladatai