Megoldás: 14.14
Olyan
n számot keresünk, amelynek lehetőleg sok osztója van. Ha
n-nek az első
k prímszám szorzatát választjuk, akkor
d(n)=
2k
, hiszen
n összes osztóját úgy kapjuk, hogy e
k darab prímszám közül bizonyosakat összeszorzunk. Ha
n-et így választjuk, annak megvan az az előnye is, hogy az utána következő szám prímosztói mind nagyobbak a
k-adik prímnél,
pk
-nál, hiszen
n+1 relatív prím
n-hez. Ennek alapján könnyen beláthatjuk, hogy
n+1 legfeljebb
k-1 prímszám szorzata lehet. Tegyük fel ugyanis, hogy
n+1 legalább
k prím szorzata. Ezek mindegyike nagyobb
pk
-nál, tehát
n+1≥(
pk
+1
)k
+1≥
pk
k
+2≥n+2
|
| () |
volna, ami ellentmondás. (Az utolsó egyenlőtlenségnél felhasználtuk, hogy
n az első
k prímszám szorzata, tehát
k darab olyan prím szorzata, amelyek mindegyike legfeljebb
pk
.)
Ez az ellentmondás bizonyítja, hogy
n+1 legfeljebb
k-1 prímszám szorzata, így osztóinak száma is legfeljebb
2k-1
. (Egyenlőség csak akkor van, ha csupa különböző prím szorzata. Ha a prímek között azonosak is vannak, akkor még kevesebb.) Azt kaptuk, hogy
d(n)-d(n+1)=
2k
-d(n+1)≥
2k
-
2k-1
=
2k-1
.
|
Ha tehát
k-t úgy választjuk, hogy
2k-1
nagyobb legyen az előre adott
K-nál, akkor
d(n) és
d(n+1) különbsége nagyobb lesz
K-nál.