Forum:  Olympiade-Aufgaben
Thema: 501333 Matheolympiade
Themen-Übersicht
Janek05
Junior
Dabei seit: 30.10.2018
Mitteilungen: 7
Aus:
Themenstart: 2019-02-05 20:52

Moin,
Ich bräuchte bei dieser Aufgabe einmal Hilfe:
Die Zahlenfolge x1, x2, x3, . . . ist durch x1 = 1 und die rekursive Vorschrift
x(k+1) = xk+1/xk
für k = 1, 2, . . .
definiert.
a) Man beweise, dass x501333 > 1000 gilt.
b) Man berechne den ganzzahligen Anteil von x501333.

Bei solchen Rekursionsaufgaben rechne ich eigentlich immer ein paar Werte aus und versuche dann, daraus eine explizite Formel zu machen. Hier finde ich aber irgendwie keinen geeigneten Zusammenhang zwischen k und xk.
Danke schonmal für jede Hilfe
Janek05


Ex_Senior
Neu
Dabei seit: 00.00.0000
Mitteilungen: 0
Aus:
Beitrag No.1, eingetragen 2019-02-05 22:40

Hallo Janek,

ich würde es mit folgender Idee probieren: Ist für zwei ganze Zahlen <math>k</math> und <math>s</math> die Ungleichung <math>s\leq k < s+1</math> gegeben, so kann man die nächsten <math>s</math> Folgenglieder abschätzen, da die Folge offensichtlich monoton wachsend ist und wegen <math>x_{k+i+1}-x_{k+i}=\frac{1}{x_{k+i}} \leq \frac{1}{s}</math> auch <math>x_{k+s} \leq x_k + s \cdot \frac{1}{s} < s+2</math> gilt. Umgekehrt ist dann aber auch wieder Aufgrund der Monotonität auch <math>x_{k+i+1}-x_{k+i}=\frac{1}{x_{k+i}} > \frac{1}{s+2}</math>, sodass auch <math>x_{k+s+2} > x_k + (s+2) \cdot \frac{1}{s+2} \geq s+1</math> gilt.

Mit diesen beiden Abschätzungen sollte man hier ggf. zum Ziel kommen. Ich würde es jedenfalls auf diese Art und Weise zuerst einmal probieren.

Eine kurze Bemerkung zur Heuristik, wie man an diese Aufgabe herangeht: Es ist eine dritte Aufgabe, d.h., sie ist als schwierig konzipiert. Die Fragestellung verlangt nur Abschätzungen. Also ist zu erwarten, dass eine explizite Bildungsvorschrift nicht so einfach zu finden, oder nicht einfach zu handhaben ist. "Wahrscheinlich" wird man nur mit genügend guten Abschätzungen arbeiten müssen, um die geforderten Abschätzungen durchführen zu können...


Viele Grüße
Cyrix


Kornkreis
Senior
Dabei seit: 02.01.2012
Mitteilungen: 862
Aus: Chemnitz
Beitrag No.2, eingetragen 2019-02-06 01:54

Hi,

eine sehr ästhetische Abschätzung erhält man, wenn man sich mal überlegt, ob man mit $x_k+\frac{1}{x_k}$ eine Operation durchführen kann, die das Produkt der beiden Summanden liefert. Denn damit bekommt man "+1" sowie Restglieder, die sich dann hoffentlich auch gut abschätzen lassen. Und in der Tat, wenn du den Term quadrierst, bekommst du $x_{k+1}^2 > x_{k}^2+2$, was sich iterativ bis $x_1^2$ fortsetzen lässt.

Übrigens bin ich zum ersten Mal über die Aufgabe hier gestolpert (421043), bzw. gab es eine leicht schwieriger aussehende Variante im Bundeswettbewerb (2.Runde 1992), siehe hier und hier.


Janek05
Junior
Dabei seit: 30.10.2018
Mitteilungen: 7
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2019-02-06 22:44

Erstmal danke für die beiden Antworten

@Kornkreis: Mit diesem Ansatz kann ich jetzt zwar a) zeigen( fed-Code einblenden
), aber bei b) weiß ich nicht genau wie ich da weitermachen soll.

@cyrix: Irgendwie versteh ich diese ganzen Abschätzungen nicht. Folgt aus der Voraussetzung fed-Code einblenden
mit s und k ganz nicht s=k?
Und wenn ich in die letzte Ungleichung k=s=4 einsetze, stimmt sie auch irgendwie schon nicht mehr. Könnten Sie mir das vielleicht nochmal erklären, ich blicke da nicht ganz durch.  ☹️
Danke
Janek


Kornkreis
Senior
Dabei seit: 02.01.2012
Mitteilungen: 862
Aus: Chemnitz
Beitrag No.4, eingetragen 2019-02-07 02:07

Für die b) sollst du jetzt die Restglieder nicht weglassen, sondern eine Gleichung $x_n^2=2(n-1)+1+...$ erhalten. Was ist hier "..." und wie kannst du es nach oben abschätzen?

Übrigens meinte cyrix sicherlich $s\leq x_k < s+1$.




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=240188=16
Druckdatum: 2020-10-27 07:51