5. Zadatak

Prvo rješenje.

Direktnom provjerom vidimo da je za brojeve $n$ redom $1$, $2$, $3$, $4$, $5$ vrijednost $d(n)$ jednaka redom $1$, $2$, $2$, $3$, $2$, pa je zbroj brojeva djelitelja prvih $n$ prirodnih brojeva redom jednak $1$, $3$, $5$, $8$, $10$. S druge strane $n!$ redom iznosi $1$, $2$, $6$, $24$, $120$. a njihovi brojevi djelitelja su redom $1$, $2$, $4$, $8$, $16$. Vidimo da su za $n\leq5$ jedina dva rješenja $n=1$ i $n=4$, dok za $n=5$ vrijedi

$$\sum_{k=1}^{5}d(k)=10<16=d(5!).$$

Matematičkom indukcijom dokazat ćemo tvrdnju: za sve prirodne brojeve $n\geq5$ vrijedi

$$\sum_{k=1}^{n}d(k)<d(n!).$$

Time ćemo dokazati da su $n=1$ i $n=4$ jedini prirodni brojevi s traženim svojstvom.

Baza indukcije za $n=5$ je gore dokazana. Pretpostavimo da tvrdnja vrijedi za neki prirodan broj $n$. U koraku indukcije treba dokazati tvrdnju za $n+1$. Koristeći pretpostavku indukcije slijedi

$$\sum_{k=1}^{n+1}d(k)=\sum_{k=1}^{n}d(k)+d(n+1)<d(n!)+d(n+1).$$

Da bismo dokazali tvrdnju za broj $n+1$ potrebno je dokazati nejednakost

$$d(n!)+d(n+1)\leq d((n+1)!).$$

Svaki djelitelj broja $n!$ ujedno je i djelitelj broja $(n+1)!$; takvih djelitelja je $d(n!)$. Nadalje, za svaki djelitelj $r$ broja $n+1$ veći od $1$, broj $r\cdot n!$ djelitelj je broja $(n+1)!$, a nije djelitelj broja $n!$; takvih djelitelja je $d(n+1)-1$.

Konačno, neka je $p$ neki prosti djelitelj od $n+1$ i neka je $p^k$ najveća potencija broja $p$ koja dijeli $n!$. Tada $p^{k+1}$ dijeli $(n+1)!$, ali ne dijeli $n!$. Također, $p^{k+1}$ nije oblika $r\cdot n!$ jer $n!$ ima barem $2$ različita prosta faktora za $n\geq5$.

Brojeći $p^{k+1}$, pronašli smo $d(n!)+(d(n+1)-1)+1$ različitih djelitelja broja $d((n+1)!)$, čime je nejednakost $d(n!)+d(n+1)\leq d((n+1)!)$ dokazana. To dovršava korak indukcije, pa i tvrdnju indukcije. Zato su zaista jedini brojevi koji zadovoljavaju uvjete zadatka $n=1$ i $n=4$.

Drugo rješenje.

Za svaki $k\in\mathbb N$ trivijalno je zadovoljena nejednakost $d(k)\leq k$, pa vrijedi

$$\sum_{k=1}^{n}d(k)\leq\sum_{k=1}^{n}k=\frac{n(n+1)}2.$$

Za $n\geq7$, prebrojimo djelitelje broja $n!$ koji su oblika $2^{a_1}3^{a_2}5^{a_3}7^{a_4}$, za neke nenegativne cijele brojeve $a_1$, $a_2$, $a_3$ i $a_4$. Ukupan broj takvih djelitelja je jednak $(r_1+1)(r_2+1)(r_3+1)(r_4+1)$, gdje su $r_1$, $r_2$, $r_3$ i $r_4$ prirodni brojevi iz rastava broja $n!$ na proste faktore:

$$n!=2^{r_1}\cdot3^{r_2}\cdot5^{r_3}\cdot7^{r_4}\cdots,$$

budući da za svaki od takvih djelitelja treba vrijediti $0\leq a_i\leq r_i$, $i=1,2,3,4$.

Kako je svaki drugi prirodan broj paran, postoji barem $\left\lfloor\frac n2\right\rfloor\geq\frac{n-1}{2}$ parnih brojeva manjih ili jednakih $n$. Svaki od tih brojeva u umnošku $n!$ doprinosi za barem jedan u eksponentu $r_1$, pa zaključujemo $r_1\geq\frac{n-1}{2}$. Slično, kako je svaki treći prirodan broj djeljiv s $3$, zaključujemo

$$r_2\geq\left\lfloor\frac n3\right\rfloor\geq\frac{n-2}{3}.$$

Kako je $n\geq7$, znamo da je $r_3\geq1$ i $r_4\geq1$. Iz svega navedenog, slijedi

$$d(n!)\geq(r_1+1)(r_2+1)(r_3+1)(r_4+1) \geq\frac{n+1}{2}\cdot\frac{n+1}{3}\cdot2\cdot2 =\frac{2(n+1)^2}{3}.$$

Iz uvjeta zadatka i koristeći prvu nejednakost, dobivamo da nužno vrijedi

$$\frac{n(n+1)}2\geq\sum_{k=1}^{n}d(k)=d(n!)\geq\frac{2(n+1)^2}{3}.$$

Međutim, ta je nejednakost ekvivalentna s

$$\frac n2\geq\frac{2(n+1)}3,$$ $$3n\geq4n+4,$$

što očito ne vrijedi ni za koji prirodan broj $n$. Zato nam je početna pretpostavka bila kriva, pa je nužno $n\leq6$.

Kao na početku prvog rješenja direktno provjerimo vrijednosti za $n\leq5$, dok ni za $n=6$ ne dobivamo rješenje jer je suma djelitelja prvih $6$ prirodnih brojeva jednaka $14$, dok je $d(6!)=d(720)=30$.