Was zur Kombinatorik

19.10.2004, 13:38	skwobu	Auf diesen Beitrag antworten »
Was zur Kombinatorik Hallo Folgende Aufgabe: Es sei F = [a1, a2, … , an] eine Folge von n ganzen Zahlen, die nicht alle verschieden zu sein brauchen. Dann gibt es in F (mindestens) eine Teilfolge von direkt aufeinander folgenden Zahlen, deren Summe ein Vielfaches von n ist. Das soll mit HIlfe des Schubfachprinzips gelöst werden. Bzw. soll gezeigt werden, dass es bei n-1 Elementen nicht funktioniert. Ich habe nun mal angenommen, um mir das an einem Bsp zu erklkären, dass F=[3,3,4,7] ist. DAnn wäre n = 4, aber keine Teilfolge ein Vielfaches, oder? Was mach ich falsch?
19.10.2004, 20:02	Martin Ipur	Auf diesen Beitrag antworten »
RE: Was zur Kombinatorik Um zu zeigen, dass es eine Liste mit n-1 Einträgen gibt, so dass keine Teilfolge von direkt aufeinanderfolgenden Zahlen eine durch n teilbare Summe hat, genügt es, ein Gegenbeispiel anzugeben. Die Frage ist nur, ob ein n ausreicht, oder du für jedes n eins finden musst. In der Liste F = [3,3,4,7] halte ich [4] für eine erlaubte Teilfolge. Was denkst du? Ich nehme an, dass die leere Folge ausgeschlossen ist, denn sonst wäre die Behauptung trivialerweise wahr.
19.10.2004, 21:12	skwobu	Auf diesen Beitrag antworten »
RE: Was zur Kombinatorik hallo, habe auch überlegt, ob 4 vielleicht eine teilfolge ist. aber dann dachte ich mir wieder, dass zur einer Folge immer 2 Elemente gehören, oder??. ich denke, man muss davon ausgehen, dass es n-1 schubfächer für die Reste {1,2,3} gibt bei n=4. Bei n-1 Elemten wäre ja nicht gewährleistet, dass die Summe der Folgen grösser als n ist, oder? herjee, ich komm mir grad ma wieder ziemlich blöd vor wahrscheinlich lieg ich ganz falsch.
19.10.2004, 21:32	Mario Ahna	Auf diesen Beitrag antworten »
Ein Beispiel dafür, dass eine (n-1)-elementige Folge nicht ausreicht, ist [1, 1, ..., 1]. Es gibt 1-elementige Folgen, wenn sie nicht explizit verboten werden. Ob es 0-elementige Folgen gibt, ist dagegen Ansichtssache (und hängt z.B. davon ab, ob man 0 als natürliche Zahl auffasst oder nicht). Ich denke, dass eine 1-elementige Teilfolge erlaubt sein sollte, denn sonst ist die Behauptung für n=2 und [1, 2] falsch. Es sollte genügen, die Anfangsstücke zu betrachten, also die Teilfolgen, die an der ersten Stelle beginnen. Dann genügt es nämlich, entweder eine dieser Teilfolgen zu finden, die den Rest 0 lässt, oder zwei Teilfolgen, die denselben Rest lassen. Denn im letzteren Fall kannst du die Differenzfolge bilden, also die längere ohne die kürzere nehmen. Beispiel: F =[2,1,2,1] (1,1) = [2], Rest 2 (1,2) = [2,1], Rest 3 (1,3) = [2,1,2], Rest 1 (1,4) = [2,1,2,1], Rest 2 Bilde die Differenz (1,4) \ (1,1) = [1,2,1], die hat den Rest 2-2 = 0.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »