Übergangs-Marathon Mathematik - Seite 3

02.09.2014, 14:01

tmo

Wirklich tolle Aufgabe, finde ich Freude

Das ist genau die Art Aufgabe, wie sie hier hingehört. Elementar lösbar, aber trotzdem kein Einzeiler und wahrscheinlich sogar so "selten", dass die meisten (so wie ich z.B.) noch nie drüber nachgedacht haben.

Die Lösung ist:

Ist $\begin{align*} N=\lfloor \sqrt a \rfloor \end{align*}$ die eindeutig betimmte natürliche Zahl mit $\begin{align*} N \leq \sqrt{a} < N+1 \end{align*}$ , so wird die Folge schließlich konstant $\begin{align*} N \end{align*}$ sein, außer $\begin{align*} a=(N+1)^2-1 \end{align*}$ (D.h. a fehlt nur eine einzige Zahl zur nächsten Quadratzahl), dann pendelt die Folge schließlich zwischen den beiden Zahlen $\begin{align*} N \end{align*}$ und $\begin{align*} N+1 \end{align*}$ .

Beweis:

Zunächst mal folgende Überlegungen:

Es gilt für jede reelle Zahl x: $\begin{align*} \lfloor x \rfloor > x-1 \end{align*}$ .
Und für jede natürliche Zahl x gilt: $\begin{align*} \lfloor \frac{x}{2} \rfloor \geq \frac{x}{2}-\frac{1}{2} \end{align*}$ .

Dies liefert $\begin{align*} x_{n+1} \geq \frac{1}{2}\lfloor x_n+\frac{a}{x_n} \rfloor - \frac{1}{2} > \frac{1}{2}\left( x_n+\frac{a}{x_n}-1 \right) - \frac{1}{2} = \frac{1}{2}\left( x_n+\frac{a}{x_n} \right) -1 \geq \sqrt{a}-1 \geq N-1 \end{align*}$ , also $\begin{align*} x_{n+1} \geq N \end{align*}$ (Wegen der Ganzzahligkeit - man bemerke, dass eine Ungleichung der Kette echt ist). Also ist die Folge ab dem zweiten Folgenglied größergleich N.

Nun schauen wir uns an, was passiert, wenn $\begin{align*} x_n \geq N+1 \end{align*}$ gilt: Dann gilt $\begin{align*} \frac{a}{x_n} < \sqrt{a} < N+1 \end{align*}$ , also $\begin{align*} \lfloor \frac{a}{x_n} \rfloor \leq N \end{align*}$ und somit $\begin{align*} x_n + \lfloor \frac{a}{x_n} \rfloor \leq x_n+N < 2x_n \end{align*}$ , also $\begin{align*} x_{n+1} < x_n \end{align*}$ , d.h. die Folge wird echt kleiner.

Zusammen mit obiger Überlegung folgt nun, dass die Folge schließlich den Wert $\begin{align*} N \end{align*}$ erreichen wird. Die Frage ist nun nur noch, ob sie dann konstant bleibt.

Dort unterscheiden wir nun:

1. Fall: $\begin{align*} a = (N+1)^2-1 = N(N+2) \end{align*}$ .

Dann gilt $\begin{align*} \frac{a}{N} = N+2 \end{align*}$ , also sind in $\begin{align*} \frac{1}{2}\left(N+\frac{a}{N} \right) = N+1 \end{align*}$ alle Divisionen schon ganzzahlig, d.h. die Folge pendelt tatsächlich zwischen $\begin{align*} N \end{align*}$ und $\begin{align*} N+1 \end{align*}$ .

2. Fall $\begin{align*} a < (N+1)^2-1 = N(N+2) \end{align*}$ .

Dann gilt $\begin{align*} \frac{a}{N} < N+2 \end{align*}$ , also $\begin{align*} \lfloor \frac{a}{N} \rfloor \leq N+1 \end{align*}$ , also $\begin{align*} N+\lfloor \frac{a}{N} \rfloor \leq 2N+1 \end{align*}$ , also $\begin{align*} \lfloor \frac{1}{2}\left( N+\lfloor \frac{a}{N} \rfloor \right)\rfloor \leq N \end{align*}$ , d.h. die Folge bleibt konstant.

02.09.2014, 19:57

Leopold

Übergangs-Marathon Mathematik - Seite 3

Verwandte Themen