Problem 1797

Solution:

Wir geben einen kombinatorischen Beweis. Dazu müssen wir zuerst eine geeignete Interpretation der Funktion $f$ finden. Für natürliche Zahlen $n, k$ ist $\left\lfloor\frac{n}{k}\right\rfloor$ gleich der Anzahl natürlicher Zahlen $\leq n$, die durch $k$ teilbar sind. Oder anders formuliert, gleich der Anzahl natürlicher Zahlen $\leq n$, die $k$ als Teiler besitzen. Bezeichnet $\tau(k)$ die Anzahl positiver Teiler von $k$, dann gilt demnach
$$\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor=\sum_{k=1}^{n} \tau(k)$$
und $f(n)$ ist daher die durchschnittliche Anzahl Teiler aller natürlichen Zahlen $\leq n$. Mit Hilfe von (4) rechnet man leicht nach, was intuitiv klar ist, nämlich dass
$$f(n)>f(n+1) \quad \Longleftrightarrow \quad f(n)>\tau(n+1)$$
und analog für das umgekehrte Ungleichungszeichen.

Nach dieses Vorbereitungen ist der Rest nun einfach. Einerseits gilt $\tau(n) \geq 2$ für alle $n \geq 2$ mit Gleichheit genau dann, wenn $n$ eine Primzahl ist. Ausserdem ist $f(6)>2$ und daher $f(n)>2$ für alle $n \geq 6$. Die Ungleichung $f(m)>\tau(m+1)$ ist also sicher für jede Primzahl $m+1 \geq 7$ erfüllt, und von dieses gibt es unendlich viele.

Andererseits ist die Ungleichung $f(m)<\tau(m+1)$ sicher immer dann erfüllt, wenn die Zahl $m+1$ mehr Teiler besitzt als alle natürlichen Zahlen $\leq m$. Davon gibt es aber auch unendlich viele, denn die Funktion $\tau$ ist nicht nach oben beschränkt, zum Beispiel ist $\tau\left(2^{r}\right)=r+1$.

Solution:

Diesmal mit algebraischen Methoden. Wir zeigen zuerst, dass die Funktion $f$ nicht nach oben beschränkt ist. Es gilt nämlich $\left\lfloor\frac{n}{k}\right\rfloor>\frac{n}{k}-1$ und somit
$$f(n)=\frac{1}{n} \sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor>\frac{1}{n} \sum_{k=1}^{n}\left(\frac{n}{k}-1\right)=\left(\sum_{k=1}^{n} \frac{1}{k}\right)-1=\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{n}$$
Auf der rechten Seite steht nun die harmonische Reihe, die bekanntlich divergiert. Genauer gilt für $n=2^{m}$ die Abschätzung
$$\begin{aligned} \frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{2^{m}} & >\frac{1}{2}+\left(\frac{1}{4}+\frac{1}{4}\right)+\left(\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}\right)+\ldots+\left(\frac{1}{2^{m}}+\ldots+\frac{1}{2^{m}}\right) \\ & =\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\ldots+\frac{1}{2}=\frac{m}{2} \end{aligned}$$
Somit ist $f$ also wirklich nicht nach oben beschränkt und insbesondere existieren unendlich viele natürlichen Zahlen $n$ mit $f(n)<f(n+1)$.

Wir zeigen nun, dass auch die umgekehrte Ungleichung unendlich oft gilt. Zuerst bemerken wir, dass genau dann $\left\lfloor\frac{n+1}{k}\right\rfloor=\left\lfloor\frac{n}{k}\right\rfloor$ gilt, wenn $n+1$ nicht durch $k$ teilbar ist. Ausserdem zeigt obige Abschätzung, dass $f(n)>2$ ist für alle $n \geq 16$. Sei nun $n+1 \geq 17$ eine Primzahl, dann gilt
$$\begin{aligned} n(n+1) f(n) & =(n+1) \sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor \stackrel{(*)}{>} n \sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor+2 n \\ & =n\left(\sum_{k=1}^{n}\left\lfloor\frac{n}{k}\right\rfloor+2\right)=n \sum_{k=1}^{n+1}\left\lfloor\frac{n}{k}\right\rfloor=n(n+1) f(n+1) \end{aligned}$$
wobei wir bei $\left(^*\right) f(n)>2$ verwendet haben. Weil es unendlich viele Primzahlen $\geq 17$ gibt, ist damit alles bewiesen.