Diskrete Mathe/kombinatorik < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:40 Di 25.04.2006 | | Autor: | Sunny85 |
| Aufgabe | | Wir möchten möglichst viele Teilmengen von (n) (um das n sollen eigentlich eckige Klammern stehen) auswählen, so dass je zwei der ausgewählten mengen mindestens ein Element gemeinsam haben. Was ist di größte Anzahl von Teilmengen, die wir auswählen können? |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
(n) bedeutet: die Menge der Zahlen von 1,2,....,n (formal gehören um die Zahlen geschweift Klammern). Ich glaube, das die Antwort n-1 ist, bin mir aber nicht sicher und weiß auch nicht wie ich das zeigen kann.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:05 Di 25.04.2006 | | Autor: | DirkG |
Ich gehe mal von [mm] $n\geq [/mm] 2$ aus.
Die Antwort lautet nicht $n-1$, sondern [mm] $2^{n-1}$. [/mm] Dass es nicht mehr sein können, sieht man folgendermaßen: Von zwei Teilmengen $A$ und [mm] $A^c$ [/mm] kann höchstens eine in der bewussten Teilmengenauswahl sein, denn wenn beide drin wären, hätte die Auswahl wegen [mm] $A\cap A^c=\emptyset$ [/mm] nicht mehr die geforderte Eigenschaft. Damit kann höchstens die Hälfte aller [mm] $2^n$ [/mm] Teilmengen in der Auswahl sein.
Für ungerade $n$ ist die Auswahl nun besonders einfach: Wir nehmen einfach alle Teilmengen mit Mächtigkeit [mm] $\geq \frac{n+1}{2}$.
[/mm]
Für gerade $n$ ist es etwas schwieriger: Wir nehmen alle Teilmengen mit Mächtigkeit [mm] $\geq \frac{n}{2}+1$, [/mm] und von den Teilmengen mit Mächtigkeit [mm] $\frac{n}{2}$ [/mm] nehmen wir gerade die "Hälfte", und zwar so, dass nicht gleichzeitig $A$ und [mm] $A^c$ [/mm] in der Auswahl sind. Die Begründung dafür, dass das immer möglich ist, überlasse ich mal dir.
|
|
|
|
