Bundesrunde 11-13 < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 08:34 So 29.08.2004 | | Autor: | Hanno |
Hiho.
Hier mal wieder eine Bundesrundenaufgabe. Ich poste die Lösung in einem Mitteilungsartikel mit, dann kannst du (Stefan) die ja schonmal anschauen und prüfen - wenn nicht, muss ich ja auch noch weiterknobeln.
Also los:
Man bezeichne mit [mm]u(x)[/mm] den größten ungeraden Teiler der natürlichen Zahl [mm]x[/mm]. Man beweise, dass für jedes natürliche $n$ die Ungleichung
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^n}{\frac{u(i)}{i}}>\frac{2}{3}[/mm]
gilt.
Viel Spaß. Habt Geduld, meine Lösung ist ziemlich lang und nicht ohne. (EDIT: Habe sie vorher unterschätzt)
Gruß,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:01 So 29.08.2004 | | Autor: | Hanno |
Hiho.
Hier meine vermeindliche Lösung des Problems:
[mm] $\summe_{i=1}^{2^n}{\frac{u(i)}{i}}=\summe_{i=1}^{2^{n-1}}{\frac{u(2i)}{2i}}+\summe_{i=1}^{2^{n-1}}{\frac{u(2i-1)}{2i-1}}$
[/mm]
Letzterer Summand kann zu [mm] $2^{n-1}$ [/mm] zusammengefasst werden, da (wichtige Erkenntnis) u(x) für jedes ungerade $x$ gleich $x$ ist. (man bedenke, dass nicht von echten Teilern gesprochen wurde).
So ergibt sich:
[mm] $=\summe_{i=1}^{2^{n-1}}{\frac{u(2i)}{2i}}+2^{n-1}$
[/mm]
Eine weitere Aussage zu $u(x)$: $u(2x)=u(x)$. Warum? Weil nach dem höchsten ungeraden Teiler gesucht wird, welcher sich bei Multiplikation mit zwei nicht ändert (jeder Teiler ist eine Zusammenstellung aus den Primfaktoren von $x$. Durch die Verdopplung erhöht sich bloß die 2-adische Bewertung der Zahl. Da die Zwei in der Teilerzerlegung nicht vorkommen darf (denn sonst wäre der Teiler gerade), folgt, dass $u(2x)=u(x)$).
[mm] $=2^{n-1}+\frac{1}{2}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(i)}{i}}$
[/mm]
Setzen wir dies in unsere zu prüfende linke Seite der Ungleichung ein, so erhalten wir:
[mm] $\frac{1}{2^n}\summe_{i=1}^{2^n}{\frac{u(i)}{i}}=\frac{1}{2^n}\cdot(2^{n-1}+\frac{1}{2}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(i)}{i}})$
[/mm]
[mm] $=\frac{2^{n-1}}{2^n}+\frac{1}{2^n\cdot 2}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(i)}{i}}$
[/mm]
[mm] $=\frac{1}{2}+\frac{1}{2^{n+1}}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(i)}{i}}$
[/mm]
Wir setzen nun wieder unseren obigen "Äquivalenzterm" in die Gleichung ein:
[mm] $=\frac{1}{2}+\frac{1}{2^{n+1}}\cdot (2^{n-2}+\frac{1}{2}\cdot\summe_{i=1}^{2^{n-2}}{\frac{u(i)}{i}})$
[/mm]
[mm] $=\frac{1}{2}+\frac{1}{8}+\frac{1}{2^{n+2}}\cdot\summe_{i=1}^{2^{n-2}}{\frac{u(i)}{i}}$
[/mm]
Ich möchte dies nun verallgemeinern:
Wir können den Term nach unserer obigen Umformung immer weiter umformen. Jedes mal, wenn wir das tuen, wird als Summand [mm] $\frac{1}{2^{a+2}}$ [/mm] hinzutreten, wobei $a$ der Exponent des letzten Bruchsummanden ist (Beispiel [mm] $\frac{1}{2}=\frac{1}{2^1}$ [/mm] und [mm] $\frac{1}{8}=\frac{1}{2^3}=\frac{1}{2^{1+2}}$). [/mm] Das liegt daran, dass der Faktor [mm] $\frac{1}{2^{n+(k-1)}}$ [/mm] mit dem Wert [mm] $2^{n-k}$ [/mm] der Summe [mm] $\summe_{i=1}^{2^{n-k}}{\frac{u(2i-1)}{2i-1}}$ [/mm] multipliziert wird. $k$ beschreibt dabei die Nummer des Umformungsschrittes (Beispiel für $k=1$ siehe oben).
Die Umformung endet nach endlich vielen Schritten, nämlich genau nach $n$ Schritten. Dann stehen $n$ Summanden mit der oben beschriebenen Eigenschaft vor der Summe und die Summe selber lautet [mm] $\summe_{i=1}^{2^0}{\frac{u(i)}{i}}=1$. [/mm] Diese wird dann noch mit [mm] $\frac{1}{2^{n+n}}=\frac{1}{4^n}$ [/mm] multipliziert.
Zusammengefasst sollte sich also ergeben:
[mm] $\frac{1}{4^n}+\summe_{i=1}^{n}{\frac{1}{2^{2i-1}}}>\frac{2}{3}$
[/mm]
Einige Umformungen führen uns zu der geometrischen Reihe:
[mm] $\frac{1}{4^n}+\summe_{i=1}^{n}{\frac{1}{\frac{4^{i}}{2}}}>\frac{2}{3}$
[/mm]
[mm] $\gdw\frac{1}{4^n}+2\cdot\summe_{i=1}^{n}{\frac{1}{4^{i}}}>\frac{2}{3}$
[/mm]
Wie schön, dass ich meine IMO-Überlegungen aufgeschrieben habe, denn daher weiß ich ja nun, dass (Zitat von Stefan, geht schneller ;) )
$ [mm] \sum\limits_{i=1}^k \frac{1}{n^i} [/mm] $
[Formel für die endliche geometrische Reihe]
$ = [mm] \frac{1 - \frac{1}{n^{k+1}}}{1- \frac{1}{n}} [/mm] - 1 $
$ = [mm] \frac{\frac{1}{n} - \frac{1}{n^{k+1}}}{1- \frac{1}{n}} [/mm] $
$ = [mm] \frac{n^k - 1}{n^{k+1} - n^k} [/mm] $
$ = [mm] \frac{\frac{n^k-1}{n-1}}{n^k} [/mm] $.
Also
[mm] $\frac{1}{4^n}+2\cdot\summe_{i=1}^{n}{\frac{1}{4^{i}}}>\frac{2}{3}$
[/mm]
[mm] $\gdw\frac{1}{4^n}+2\cdot \frac{4^n-1}{3\cdot 4^n}>\frac{2}{3}$
[/mm]
[mm] $\gdw\frac{1}{2^{2\cdot n+1}}+\frac{4^n-1}{3}\cdot\frac{1}{4^n}>\frac{1}{3}$
[/mm]
[mm] $\gdw\frac{1}{2^{2\cdot n+1}}+\frac{4^n-1}{3}\cdot\frac{1}{4^n}>\frac{1}{3}$
[/mm]
[mm] $\gdw\frac{1}{4^n}\cdot (\frac{1}{2}+\frac{4^n-1}{3})>\frac{1}{3}$
[/mm]
[mm] $\gdw\frac{1}{4^n}\cdot (\frac{1+2\cdot 4^n}{2\cdot 3})>\frac{1}{3}$
[/mm]
[mm] $\gdw\frac{1+2\cdot 4^n}{2\cdot 4^n}>\frac{1}{1}$
[/mm]
[mm] $\gdw\frac{1}{2\cdot 4^n}+\frac{2\cdot 4^n}{2\cdot 4^n}>1$
[/mm]
[mm] $\gdw\frac{1}{2\cdot 4^n}>0$
[/mm]
Und damit ist die Aufgabe gelöst!! Juchuu 
Hoffentlich habe ich keinen Fehler in diesem Wust gemacht.
Gruß,
Hanno
|
|
|
| |
|
Hallo.
Ich werde es mal versuchen:
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^n}{\frac{u(i)}{i}}>\frac{2}{3}[/mm]
Jede zweite Zahl i ist ungerade und daher auch ihr größter ungerader Teiler, daher gilt:
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^n}{\frac{u(i)}{i}}[/mm]
[mm]= \frac{1}{2^n}\cdot\summe_{i=0}^{2^{n-1}-1}{\frac{u(2i+1)}{2i+1}}+\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(2i)}{2i}}[/mm]
[mm]= \frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-1}}{1}+\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(2i)}{2i}}[/mm]
[mm]= \frac{2^{n-1}}{2^n}+\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(2i)}{2i}}[/mm]
Wiederum ist jedes zweite i ungerade. Somit gilt für jedes zweite i [mm]u(2i)=i[/mm]
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-1}}{\frac{u(2i)}{2i}}[/mm]
[mm]= \frac{1}{2^n}\cdot\summe_{i=0}^{2^{n-2}-1}{\frac{u(2*(2i+1))}{2*(2i+1)}+\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-2}}{\frac{u(2*(2i))}{2*(2i)}}}[/mm]
[mm]= \frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-2}}{\frac{1}{2}+\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-2}}{\frac{u(2^2*i)}{2^2*i}}}[/mm]
[mm]= \frac{1}{8}+\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-2}}{\frac{u(2^2*i)}{2^2*i}}}[/mm]
Man kann feststellen, dass
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-k}}{\frac{u(2^k*i)}{2^k*i}}[/mm]
sich auf diese Weise immer auch als
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-(k+1)}}{(\frac{1}{2^k})} + \frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-(k+1)}}{\frac{u(2^{k+1}*i)}{2^{k+1}*i}}[/mm]
[mm]= \frac{1}{2^{2k+1}} + \frac{1}{2^n}\cdot\summe_{i=1}^{2^{n-(k+1)}}{\frac{u(2^{k+1}*i)}{2^{k+1}*i}}[/mm]
darstellen lässt.
Führt man das Ganze für
[mm]\frac{1}{2^n}\cdot\summe_{i=1}^{2^n}{\frac{u(i)}{i}}[/mm] weiter bis [mm]k=n[/mm], so erhält man
[mm]\summe_{i=0}^{(n-1)}\frac{1}{2^{2i+1}} +\frac{1}{2^n}\cdot\summe_{i=1}^{2^0}{\frac{u(2^n*i)}{2^n*i}}[/mm]
[mm]= \frac{1}{2}\cdot\summe_{i=0}^{(n-1)}{\frac{1}{4^i}} +\frac{1}{2^n}\cdot\summe_{i=1}^{2^0}{\frac{u(2^n*i)}{2^n*i}}[/mm]
Unter Verwendung der geometrischen Summenformel ([mm]\summe_{i=0}^{n}{x^i} = \frac{x^{n+1}-1}{x-1}[/mm], bin jetzt zu faul um sie zu beweisen  ) erhält man:
[mm]\frac{1}{2}\cdot(\frac{(\frac{1}{4})^{n}-1}{\frac{1}{4}-1})+\frac{1}{2^{2n}}[/mm]
[mm]= \frac{1}{2}\cdot(\frac{(\frac{1}{4})^{n}-1}{-\frac{3}{4}})+(\frac{1}{4})^n[/mm]
[mm]= \frac{1}{2}\cdot(\frac{4}{3}-\frac{4}{3}*(\frac{1}{4})^n)+(\frac{1}{4})^n[/mm]
[mm]= \frac{2}{3}-\frac{1}{6}*(\frac{1}{4})^{n-1}+\frac{1}{4}*(\frac{1}{4})^{n-1}[/mm]
[mm]= \frac{1}{12}*(\frac{1}{4})^{n-1}+\frac{2}{3}[/mm]
[mm]= \frac{1}{3}*(\frac{1}{4})^n+\frac{2}{3}[/mm]
[mm]= \frac{1}{3}*(\frac{1}{4})^n+\frac{2}{3}>\frac{2}{3}[/mm]
[mm]= \frac{1}{3}*(\frac{1}{4})^n>0[/mm]
Hoffentlich stimmts...
MfG
Jan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:34 Mo 30.08.2004 | | Autor: | Hanno |
Hi Jan!
Schön gemacht, jetzt passt's meiner Meinung nach!
Dann kannst du jetzt ja mal die IMO's lösen ;)
Gruß,
Hanno
|
|
|
|
