Feladat: Gy.2854 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bárány Kristóf ,  Deli Tamás 
Füzet: 1994/március, 116 - 117. oldal  PDF  |  MathML 
Témakör(ök): Osztók száma, Gyakorlat
Hivatkozás(ok):Feladatok: 1993/szeptember: Gy.2854

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Ha egy n szám prímtényezős felbontása p1α1⋅p2α2⋅...⋅pnαn, akkor osztóinak a száma (α1+1)⋅(α2+1)⋅...⋅(αn+1); egy osztó ugyanis p1β1⋅p2β2⋅...⋅pnβn alakú, ahol 0≤βi≤αi, vagyis p1 kitevője éppen (α1+1)-féle lehet, p2-é (α2+1)-féle és így tovább. Ezt felhasználva először meghatározzuk, hogy legfeljebb hány osztója lehet egy kétjegyű számnak.
Mivel 2⋅3⋅5⋅7>100, azért egy kétjegyű számnak 1-, 2- vagy 3-féle prímosztója lehet. Az előbbiek szerint pa⋅qb⋅rc⋅ és 2a⋅3b⋅5c osztóinak száma megegyezik, s az utóbbi, feltéve, hogy p<q<r, nem nagyobb az előbbinél; vagyis a keresett maximum biztos, hogy a 2a⋅3b⋅5c alakú kétjegyű számok között is fellép. Vizsgáljuk ezeket!
Ha egy ilyen alakú számnál fellép a maximum, akkor 2(a+1)⋅3b⋅5c, minthogy az előbbinél több osztója van, szükségképpen már háromjegyű. Elegendő tehát azokat a számokat tekinteni, amelyekben a 2 kitevője az adott b és c mellett a lehető legnagyobb.
Minthogy 53≥100, így szükségképpen c≤2. Ha c=2, akkor 2a⋅3b<4, azaz a 2a⋅3b⋅5c alakú kétjegyű számok közül a 2⋅52 és a 3⋅52 rendelkezik a legtöbb osztóval, mégpedig 6-tal.
Ha c=1, akkor 2a⋅3b≤19, vagyis az itteni maximum lehetőségek:

b=2→2⋅32⋅5,  hiszen  22⋅32⋅5≥100; osztói száma 12b=1→22⋅3⋅5,  osztói száma 12b=0→24⋅5,  osztói száma 10.

Ha pedig c=0, akkor b≤4, a lehetőségek tehát (zárójelben az osztók száma):

b=4→34,(5)b=3→2⋅33,(8)b=2→23⋅32,(12)b=1→25⋅3,(12)b=0→26,(7)

Megállapítottuk, hogy egy kétjegyű számnak legfeljebb 12 osztója lehet, s rögtön látjuk, hogy a 2⋅32⋅5=90, 22⋅3⋅5=60, 23⋅32=72, 25⋅3=96, számoknak éppen ennyi osztója van. Keressük meg a többi ilyen számot.
Nézzük először a 3-féle prímosztóval rendelkezőket. Ezek pa⋅qb⋅rc alakúak, ahol a≥b≥c≥1 és (a+1)⋅(b+1)⋅(c+1)=12, ami csak úgy lehet, ha a=2, b=c=1. Tehát a keresett számok p2qr alakúak. Mivel p, q, r különböző prímek, azért a legkisebb közülük legalább 2, a középső legalább 3, a legnagyobb legalább 5, azaz p2qr≥p⋅2⋅3⋅5=30p. Ez viszont p2qr≤99 miatt csak úgy lehet, ha p=2 vagy 3. A p=3 esetben 32qr≤99, amiből qr≤11, ez csak q=2, r=5 (vagy fordítva) mellett lehetséges. A p=2 esetben qr=24. Feltehető, hogy q<r, ekkor r≥5 s így q<5, vagyis q=3. Emellett r=5 vagy 7 állhat. Kaptuk tehát a 32⋅2⋅5, 22⋅3⋅5 és a 22⋅3⋅7 eseteket.
Nézzük most a paqb alakúakat, ahol a≥b≥1. Az előzőekhöz hasonló megfontolással látható, hogy akkor a=3, b=2 vagy a=5, b=1 léphet csak föl. Az a=5 esetben szükségképpen p=2, így q≤9932, azaz q=3. Az a=3 esetben p2q2≥22⋅32=36, vagyis 99≤p3q2≥36p, amiből p≤2,75, azaz p=2; valamint q≤998, ami q=3 esetén teljesülhet. Tehát a 25⋅3 és a 23⋅32 eseteket kaptuk.
A pn alakú számok esetén, ha az osztók száma 12, akkor a=11. Ez azonban p11≥211>99 miatt nem lehetséges. Összefoglalva, a keresett számok a következők:
2⋅32⋅5=90,22⋅3⋅5=60,22⋅3⋅7=84,25⋅3=96,23⋅32=72.

Megjegyzés. Igen sok beküldő megelégedett az általunk is eredményül kapott számok (vagy ezek némelyikének) felsorolásával, minden további magyarázat, indoklás nélkül (miért ennyi a maximum; van-e még más szám, amelynek szintén ennyi osztója van). Ezek a dolgozatok ─ a pontversenyre érvényes ,,az eredmények puszta közlése nem elegendő a megoldáshoz'' elvnek megfelelően ─ az elérhető maximális pontszámnak csak egy részét kapták meg.