Folgen in den ersten < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 12:19 Sa 21.05.2005 | | Autor: | DaMenge |
Hallo,
Zu beweisen ist, dass wenn man die ersten 101 Zahlen beliebig anordnet, dass immer eine Folge mit 11 Gliedern existiert, die entweder auf- oder absteigend ist.
[Hinweis : zwischen den Gliedern der Folge können auch andere Zahlen der Anordnung stehen und eine Anordnung könnte auch eine absteigende und eine aufsteigende Folge mit 11 GLiedern haben, gefragt ist nur die Existenz in jeder Anordnung]
Beispiel, dass eine Anordnung von 100 Zahlen keine solche Folge bringt :
91 , 92 , 93 , ... , 100
81 , 82 , 83 , ... , 90
71 , 72 , 73 , ... , 80
.
.
.
1 , 2 , 3 , ... , 10
Allgemein soll gelten : Um eine auf- oder absteigende Folge mit (n+1) Gliedern immer in einer beliebigen Anordnung der Zahlen zu finden, braucht man (n²+1) Zahlen !
Hat jemand eine Idee?
Das soll hier nur Just For Fun sein....
MFG
DaMenge
SPOILER - Warnung :
(P.S. : Im BUCH der Beweise steht die Lösung, also nicht schummeln! )
[Es stehen auch überall sonst Beweise dazu - einen hatte ich ![[]](/images/popup.gif) auf dem MathePlaneten schon geschrieben]
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:31 So 22.05.2005 | | Autor: | jbulling |
Hi Du,
falls ich das jetzt richtig verstanden habe, dann ist die Aussage nicht richtig.
Man kann doch eine Zahlenfolge konstruieren, für die es keine aufeinanderfolgenden Glieder gibt. Auch wenn man Lücken und die umkehrung der Reihenfolge ausser Acht lässt nicht:
Wenn man die Zahlen so verteilt, dass man die 1 auf Position 51 setzt. Die zwei auf 52, die drei auf 50, die 4 auf 53. Also ungefähr so
[mm] a_k=x [/mm] für k=51 + [x/2] * [mm] (-1)^x [/mm] für alle 1 [mm] \le [/mm] x [mm] \le [/mm] 101
dann gibt es nur Folgen mit zwei Zahlen, die auf- oder absteigend sind (auch wenn man die Lücken wegläßt).
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:55 So 22.05.2005 | | Autor: | DaMenge |
Hi,
schön, dass du dich für diese (durchaus nicht leichte) Aufgabe interessierst.
eine aufsteigende Folge muss nicht aufeinanderfolgende Zahlen haben, eine solche Folge (mit 11 Gliedern) ist zum Beispiel auch:
2,4,6,8,10,12,14,16,18,20,22
oder
4,7,13,25,56,66,88,89,91,99,101
erstere Folge kommt in deiner Anordnung vor, wenn ich dich jetzt richtig verstanden habe.
(absteigende Folgen müssen ebenso wenig aufeinanderfolgende Zahlen als Folgeglieder haben - es meint den mathem. Folgebegriff)
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:55 So 22.05.2005 | | Autor: | jbulling |
Hallo DaMenge,
kannst Du nochmal genauer darauf eingehen, was Du unter einer Folge verstehst?
Eine Folge ist im Sinne der Mathematik eine Abbildung der natürlichen Zahlen auf eine andere Menge. In Deinem Fall wieder auf die natürlichen Zahlen. Damit ist 1,1,1,1,...... genauso eine Folge, wie eine beliebig angeordnete Menge von Zufallszahlen.
Wenn ich Dich jetzt richtig verstanden habe, forderst Du tatsächlich in Deiner Aufgabe nur, dass es 1 [mm] \le n_1, n_2, [/mm] ..., [mm] n_{11} \le [/mm] 101 gibt mit
[mm] a_{n_1} [/mm] < [mm] a_{n_2} [/mm] < ... < [mm] a_{n_{11}}
[/mm]
Dabei ist [mm] a_1, a_2,... a_{101} [/mm] die Zahlenreihe.
wobei entweder gilt
[mm] n_1 [/mm] < [mm] n_2 [/mm] < .... < [mm] n_{11}
[/mm]
oder
[mm] n_1 [/mm] > [mm] n_2 [/mm] > .... > [mm] n_{11}
[/mm]
aber es muss sonst keinen weiteren Zusammenhang geben und auch keine funktionale Abhängigkeit der [mm] n_1,.... n_{11} [/mm] und auch nicht der [mm] a_{n_1},...a_{n_{11}}.
[/mm]
Stimmt das so?
Irgendwie klingt das erst mal trivial, aber ist es wahrscheinlich doch nicht, oder?!
Naja wenn die Lösung im Buch der Beweise steht, dann ist es wahrscheinlich nicht trivial zu beweisen. Irgendwie klingt das ganze ganz verdächtig nach Permutationen und besonders nach Signaturen davon,
Gruß
Jürgen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:23 So 22.05.2005 | | Autor: | DaMenge |
Hallo Jürgen,
du kommst ein wenig mit den Indezies durcheinander.
Bist du sicher, dass du es vollkommen mathematisch beschrieben haben willst?
Na gut:
sei $ [mm] (a_1 [/mm] , [mm] a_2 [/mm] , ... , [mm] a_{101} [/mm] ) $ eine beliebige Anordnung der 101 ersten Zahlen, also [mm] a_i [/mm] ist eine natürliche Zahl und i beschreibt nur die Stellung innerhalb der Anordnung.
zu beweisen ist, dass es darunter jetzt ein Teilfolge gibt, also dass es $ [mm] n_1 [/mm] < .. < [mm] n_{11} [/mm] $ als INDEX gibt, also $ [mm] n_i\in \{ 1,..101 \} [/mm] $ , so dass
$ [mm] a_{n_1} [/mm] < [mm] a_{n_2} [/mm] < ... < [mm] a_{n_{11}} [/mm] $ eine (aufsteigende) Folge oder
$ [mm] a_{n_1} [/mm] > [mm] a_{n_2} [/mm] > ... > [mm] a_{n_{11}} [/mm] $ eine (absteigende) Folge ist.
Ich denke so sollte es nun mathematisch sein
(bitte überprüfen^^)
ich mach mal ein Beispiel mit den ersten 20 Zahlen:
eine Anordnung:
5 , 9 ,7 ,3, 8,13,19,2,1,20,4,6,10,18,11,17,12,15,14,16
dann wäre eine aufsteigende Teilfolge mit 8 Gliedern
5,7,8,10,11,12,14,16
eine absteigende mit 5 Gliedern:
19,18,17,15,14
(keine Ahnung, ob es wirklich die größten auf- bzw. absteigenden Folgen sind, aber ich sehe gerade keine größeren)
und trivial ist die Aussage nicht unbedingt. bei einer bestimmten Anordnung der ersten 100 Zahlen, gibt es keine solche Folge der Länge 11... Es soll ja für ALLE möglichen Anordnungen gelten.
btw : beweise doch lieber gleich die allgemeine Aussage über n - nicht beschränkt auf 101
viel Spaß dabei
DaMenge
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:36 So 22.05.2005 | | Autor: | jbulling |
Danke für die Antwort.
Nö so hab ich das mit den Indices auch gemeint :o)
Naja aber Buch-Beweise sind mir dann im Moment doch eine Nummer zu hoch.
Das Buch hab ich hier übrigens auch stehen, aber ich werd noch ein bischen drüber nachdenken, bevor ichs nachschlage.
Gruß
Jürgen
|
|
|
|
