 |
A B. 5152. feladat (2021. február) |
B. 5152. Határozzuk meg azokat az \(\displaystyle 1\)-nél nagyobb pozitív egész számokat, amelyek összes pozitív osztóját fel lehet írni egy körvonalra úgy, hogy a szomszédos osztók hányadosa mindig prímszám legyen.
Javasolta: Lenger Dániel (Budapest) és Szűcs Gábor (Szikszó)
(5 pont)
A beküldési határidő 2021. március 10-én LEJÁRT.
Megoldás. Először vizsgáljuk azt az esetet, amikor a számnak egyféle prímosztója van, vagyis prímhatvány. Ha \(\displaystyle n=p^\alpha\), akkor az 1 szomszédja csak \(\displaystyle p\) lehet, vagyis \(\displaystyle \alpha\geq 2\) esetén nem létezik megfelelő felírás, hiszen ilyenkor az 1-nek két különböző szomszédja is van. Ha \(\displaystyle \alpha=1\), akkor az egyetlen lehetséges sorrend (\(\displaystyle 1\) és \(\displaystyle p\) a két szám a körvonalon) megfelelő. A prímhatványok közül tehát pontosan a prímek azok, melyekre van megfelelő felírás.
A továbbiakban azokat az eseteket vizsgáljuk, amikor az \(\displaystyle n\) számnak legalább két különböző prímosztója is van. Legyen a szám prímtényezős felbontása \(\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_r^{\alpha_r}\) (ahol \(\displaystyle r\geq2\)). Ha \(\displaystyle d\) az \(\displaystyle n\) szám egy pozitív osztója, akkor \(\displaystyle d=p_1^{\beta_1}p_2^{\beta_2}\dots p_r^{\beta_r}\) valamely \(\displaystyle 0\leq \beta_1 \leq \alpha_1, \dots, 0\leq \beta_r\leq \alpha_r\) kitevőkkel. Ebből következik az a jól ismert összefüggés is, hogy \(\displaystyle n\) pozitív osztóinak száma \(\displaystyle (\alpha_1+1)(\alpha_2+1)\dots(\alpha_r+1)\).
Jelölje \(\displaystyle \Omega(d)=\beta_1+\beta_2+\dots+\beta_r\) a \(\displaystyle d\) szám multiplicitással számolt prímosztóinak számát. Ha van megfelelő felírás, akkor a körvonalra írt számokon lépegetve minden lépésben 1-gyel változik a prímosztók \(\displaystyle \Omega\) száma. Így \(\displaystyle \Omega(d)\) felváltva lesz páros, illetve páratlan, egy teljes kört megtéve viszont ugyanahhoz a számhoz érünk vissza, így az osztók számának párosnak kell lennie. Tehát megfelelő felírás csak akkor lehet, ha az osztók \(\displaystyle (\alpha_1+1)(\alpha_2+1)\dots(\alpha_r+1)\) száma páros, vagyis ha legalább az egyik \(\displaystyle \alpha_i\) kitevő páratlan (azaz a szám nem négyzetszám).
Vizsgáljuk meg külön az \(\displaystyle r=2\) esetet. Legyen tehát \(\displaystyle n=p_1^{\alpha_1}p_2^{\alpha_2}\), és mondjuk \(\displaystyle \alpha_1\) páratlan. A következő sorrend megfelelő:
$$\begin{multline*} 1,p_1,p_1^2,\dots,p_1^{\alpha_1}, p_1^{\alpha_1}p_2, \dots, p_1^{\alpha_1}p_2^{\alpha_2},p_1^{\alpha_1-1}p_2^{\alpha_2},p_1^{\alpha_1-1}p_2^{\alpha_2-1},\dots,p_1^{\alpha_1-1}p_2,p_1^{\alpha_1-2}p_2,p_1^{\alpha_1-2}p_2^2,\dots,p_1^{\alpha_1-2}p_2^{\alpha_2},\\ p_1^{\alpha_1-3}p_2^{\alpha_2},\dots,p_1^{\alpha_1-3}p_2,\dots,p_1p_2,\dots,p_1p_2^{\alpha_2},p_2^{\alpha_2}, \dots, p_2. \end{multline*}$$Példaként \(\displaystyle \alpha_1=5,\alpha_2=4\) esetén a következőképpen néz ki a sorrend (a vastagított vonal mutatja, hogy milyen sorrendben kerülnek a körvonalra az osztók):
Ezzel beláttuk, hogy ha \(\displaystyle r=2\), akkor páros sok osztó esetén van megfelelő felírás (páratlan sok osztó esetén pedig nincsen).
Most belátjuk \(\displaystyle r\)-re vonatkozó teljes indukcióval, hogy ez \(\displaystyle r>2\) esetén is így van. Tegyük fel tehát, hogy az \(\displaystyle n\) számnak \(\displaystyle r>2\) különböző prímtényezője van, és legalább egyikük kitevője páratlan \(\displaystyle n\) prímtényezős felbontásában. Legyen az egyik prímhatvány \(\displaystyle n\) prímtényezős felbontásában \(\displaystyle q^\beta\), ahol \(\displaystyle q\)-t úgy választjuk meg, hogy a többi prímtényező közül legalább egyik kitevője páratlan legyen. (Például ha van páros kitevővel szerepelő prím, akkor azt választjuk \(\displaystyle q\)-nak, ha nincs, akkor pedig \(\displaystyle q\) bármelyik prímosztó lehet.) Tehát \(\displaystyle n=q^\beta n'\), ahol \(\displaystyle n'\)-nek \(\displaystyle r-1\) féle prímosztója van, és legalább egyik páratlan kitevővel szerepel \(\displaystyle n'\) prímtényezős felbontásában. Ezek alapján \(\displaystyle n'\)-nek páros sok osztója van, melyek felírhatók megfelelő módon a körvonalra, mondjuk \(\displaystyle d_1,d_2,\dots,d_{2t}\) sorrendben. Tehát itt két szomszédos \(\displaystyle d_i\) hányadosa (beleértve a \(\displaystyle d_{2t}\) és \(\displaystyle d_1\) párt is) mindig prímszám.
Az \(\displaystyle n\) szám (pozitív) osztói a \(\displaystyle d_iq^j\) alakú számok, ahol \(\displaystyle 1\leq i\leq 2t\) és \(\displaystyle 0\leq j\leq \beta\). Ezek egy megfelelő sorrendje a következő:
$$\begin{multline*} d_1,d_1q,\dots d_1q^{\beta},d_2q^{\beta},d_2q^{\beta-1},\dots,d_2, d_3, d_3q,\dots ,d_3q^\beta,d_4q^\beta,\dots,d_4,\dots,\\ d_{2t-2},d_{2t-1},d_{2t-1}q,\dots,d_{2t-1}q^\beta,d_{2t}q^\beta,\dots,d_{2t}q,d_{2t}. \end{multline*}$$Ezzel beláttuk, hogy \(\displaystyle n\) osztóinak is van megfelelő felírása.
Összefoglalva tehát, pontosan a következő esetekben van megfelelő felírás:
- ha \(\displaystyle n\)-nek legalább két prímosztója van, melyek közül legalább az egyiknek páratlan a kitevője \(\displaystyle n\) prímtényezős felbontásában (tehát \(\displaystyle n\) nem négyzetszám),
- vagy ha \(\displaystyle n\) prím.
Statisztika:
58 dolgozat érkezett. 5 pontot kapott: Bán-Szabó Áron, Baski Bence, Bencsik Ádám, Csizmadia Miklós, Duchon Márton, Farkas 512 Izabella, Fekete Richárd, Fülöp Csilla, Hegedűs Dániel, Kalocsai Zoltán, Kercsó-Molnár Anita, Kerekes Boldizsár, Kovács 129 Tamás, Kökényesi Márk Péter, Lovas Márton, Mácsai Dániel, Molnár-Szabó Vilmos, Móra Márton Barnabás, Móricz Benjámin, Nádor Benedek, Nagy 551 Levente, Németh Márton, Páhán Anita Dalma, Sándor Péter, Seres-Szabó Márton, Somogyi Dalma, Szanyi Attila, Sztranyák Gabriella, Török Ágoston, Trombitás Karolina Sarolta, Varga Boldizsár, Wiener Anna. 4 pontot kapott: Ben Gillott, Dezső Kende Barnabás, Nagy 429 Leila, Simon László Bence, Zömbik Barnabás. 3 pontot kapott: 3 versenyző. 2 pontot kapott: 5 versenyző. 1 pontot kapott: 4 versenyző. 0 pontot kapott: 8 versenyző. Nem versenyszerű: 1 dolgozat.
A KöMaL 2021. februári matematika feladatai