Aufgabe #72 (IrMO),(Folgen) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 01:26 Mi 27.07.2005 | | Autor: | Hanno |
Hallo an alle!
Die Folge [mm] $(a_n)$ [/mm] ist durch [mm] $a_1=1, a_{2n}=a_n$ [/mm] und [mm] $a_{2n+1}=a_{2n}+1$ [/mm] definiert. Finde den maximalen Wert unter den Gliedern [mm] $a_1,...,a_{1989}$ [/mm] und die Anzahl, wie oft er auftritt.
Liebe Grüße,
Hanno
|
|
| |
|
Hallo Hanno!
> Die Folge [mm](a_n)[/mm] ist durch [mm]a_1=1, a_{2n}=a_n[/mm] und
> [mm]a_{2n+1}=a_{2n}+1[/mm] definiert. Finde den maximalen Wert unter
> den Gliedern [mm]a_1,...,a_{1989}[/mm] und die Anzahl, wie oft er
> auftritt.
In der Menge [mm]\{a_1,a_2,...,a_{2^n-1}\}[/mm] sind genau diejenigen Folgenglieder n-1, deren Index eine Darstellung als [mm]2^n-1-2^j[/mm] mit [mm]0 \le j < n[/mm] hat. Desweiteren ist [mm]a_{2^n-1}=n[/mm]. Alle weiteren Folgenglieder sind kleiner.
Beweis:
Ind.-Anfang:
[mm]\{a_1,a_2,a_3\}=\{1,1,2\}[/mm]
Ind.-Schritt:
Für [mm]\{a_1,a_2,...,a_{2^n-1}\}[/mm] gelte die Voraussetzung.
[mm]a_{2^{n+1}-1}=a_{2\cdot{}(2^n-1)+1}=a_{2^n-1}+1=n+1[/mm]
[mm]a_{2^{n+1}-1-2^0}=a_{2^{n+1}-2}=a_{2\cdot{}(2^n-1)}=a_{2^n-1}=n[/mm]
[mm]a_{2^{n+1}-1-2^n}=a_{2^n-1}=n[/mm]
Für [mm]0 < k < 2^{n-1}[/mm] ist
[mm]a_{2^{n+1}-2-2k}=a_{2\cdot{}(2^{n}-1-k)}=a_{2^{n}-1-k} \le (n-1)[/mm].
und
[mm]a_{2^{n+1}-2-2k+1}=a_{2\cdot{}(2^{n}-1-k)+1}=a_{2^{n}-1-k}+1[/mm]
Ist k keine 2er-Potenz, so ist der Term kleiner oder gleich n-1.
Für 2er Potenzen ergibt sich [mm]a_{2^{n+1}-1-2^{j+1}}=a_{2\cdot{}(2^{n}-1-2^j)+1}=a_{2^{n}-1-2^j}+1=n[/mm]
([mm]1\le j+1 < n+1[/mm])
Damit sind alle Folgenglieder in [mm]\{a_1,a_2,...,a_{2^{n+1}-1}\}[/mm] abgedeckt. Die Bedingung gilt somit auch für n+1.
Der maximale Wert in [mm]\{a_1,a_2,...,a_{2^{11}-2}\}[/mm] ist folglich 10.
Für alle j mit [mm]6 \le j \le 10[/mm] liegt [mm]a_{2^{11}-1-2^j}[/mm] in dem fraglichen Bereich. Daher kommt die 10 genau [mm]10-6+1=7[/mm] mal vor.
Ganz schön umständlich, muss ich zugeben, aber die Aufgabe ist auch nicht einfach.
Könnte sein, dass ein paar Flüchtigkeitsfehler dabei sind, aber prinzipiell müsste es so funktionieren.
MfG
Jan
|
|
|
|
![[huepf]](/images/smileys/huepf.gif "[huepf]"){kind=small}
