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ő:

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ő:

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