Hi, ich übe gerade etwas mit dem Schubfachprinzip. Jetzt hab ich hier eine Aufgabe (siehe Anhang). Ich habe mir eine Menge S für die Studierenden und eine Menge G für die Menge an Gruppen die ein Studierender hat definiert . Es gilt |S| = n. Nun definiere ich eine Abbildung f: S-> G. Für die Menge G weiß man , dass gilt : |G| > n/4 und , wenn man sich Beispiele aufzeichnet |G| < n/2 -1 . Wenn ich jetzt die stärkere Form des Schubfachprinzips anwende (sei j eine Element aus A) , komme ich auf f^-1(j) >= 3.... wo liegt mein Fehler ? Gruß
Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
Ich halte die Behauptung für falsch:
Für Studierende und Gruppen gibt es folgendes Gegenbeispiel:
1.Gruppe: 1,2,3 2.Gruppe: 1,4,5 3.Gruppe: 1,6,7 4.Gruppe: 2,4,6 5.Gruppe: 2,5,7 6.Gruppe: 3,4,7
Anzahlen an Gruppen, in denen die 7 Studierenden sind: 3,3,2,3,2,2,3
D.h. Anzahl 2 ist dreimal vertreten, und Anzahl 3 viermal - also KEINE Anzahl mindestens fünfmal. :(
EDIT: Verdammt, ich habe das " gerade" überlesen. Na zumindest zeigt das obige Beispiel, dass das anscheinend eine wichtige Voraussetzung ist.
----------------------------------------------
Ok, ich hab es: Betrachten wir den Studenten mit der maximalen Anzahl an Gruppen, in denen er drin ist. In jeder dieser Gruppen sind je zwei andere Stundenten, und all diese Studenten müssen voneinander verschieden sein und aus der Gruppe der "anderen" Studenten stammen, damit ist , wegen gerade heißt das .
Andererseits gilt für alle Anzahlen . Das macht insgesamt Schubfächer für die Anzahlen...
|