Potenzmenge < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei M [mm] \subset 2^{\{1,...,2n\}} [/mm] eine Menge von 2-elementigen Teilmengen. Zeigen Sie: Wenn |M| > n ist, dann existieren A,B [mm] \in [/mm] M mit A [mm] \cap [/mm] B [mm] \not= \emptyset [/mm] |
Ich versteh das glaub ich nicht richtig.
Ich mach mal ein Beispiel:
Sei n=3
Dann ist doch meine Potenzmenge [mm] 2^{\{1,2,4,6\}} [/mm] oder sehe ich das schon falsch?
Dann wäre [mm] M=\{\{1,2\}\{1,4\}\{1,6\}\{2,4\}\{2,6\}\{4,6\}\}
[/mm]
Also ist |M|=6 uns somit > n
Aber für [mm] A=\{1,2\} [/mm] und [mm] B=\{4,6\} [/mm] ist der Durchschnitt die leere Menge.
Wo liegt mein Denkfehler?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:10 Do 25.03.2010 | | Autor: | Teufel |
Hi.
Mit der Menge [mm] \{1,...,2n\} [/mm] ist sicher [mm] \{1,2,3,4,...,2n-1,2n\} [/mm] gemeint.
Für n=3 hast du also [mm] \{1, 2, 3, 4, 5, 6\}.
[/mm]
Und du sollst ja auch zeigen, dass 2 Mengen A und B aus M existieren, deren Durchschnitt nicht leer ist. Das heißt aber nicht, dass es für alle Mengen aus M gelten muss.
![[anon]](/images/smileys/anon.png "[anon]") Teufel
|
|
|
| |
|
Aber wie beweise ich das?
Mit Widerspruch?
Durch den Binomialkoeffizienten [mm] \vektor{n \\ 2} [/mm] bekomm ich raus, dass |M|= [mm] \bruch{n^{2}-n}{2} [/mm] ist.
Also ist |M| > n für alle n>2.
Irgendwie komm ich hier nicht mehr weiter. Es ist doch irgendwie offensichttlich, dass bei mehr als 3 Elementen in [mm] 2^{\{1,2,3\}} [/mm] mindestens zwei Elemete drinn sind, die geschnitten ungleich der leere Menge sind.
Nehmen wir an, es gebe keine zwei Elemente [mm] A,B\in [/mm] M für die gilt, dass [mm] a\cap B\not= \emptyset [/mm] ist.
Also muss in [mm] \bruch{n^{2}-n}{2} [/mm] verschiedene Mengen jedes Element nur einmal vorkommen.
Da es aber 2*n Elemente sind, die auf [mm] \bruch{n^{2}-n}{2} [/mm] Mengen verteilt werden, und [mm] 2*n<\bruch{n^{2}-n}{2} [/mm] ist, müssen zwangsläufig Elemente doppelt verteilt werden.
Dies ist ein Widerspruch zur Annahme.
Ist das so richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:33 Do 25.03.2010 | | Autor: | felixf |
Moin!
> Aber wie beweise ich das?
> Mit Widerspruch?
>
>
> Durch den Binomialkoeffizienten [mm]\vektor{n \\ 2}[/mm] bekomm ich
> raus, dass |M|= [mm]\bruch{n^{2}-n}{2}[/mm] ist.
Nein, du bekommst $|M| [mm] {\red\le} \frac{n^2 - n}{2}$ [/mm] raus. Da steht nicht, dass $M$ die Menge aller 2-elementigen Teilmengen ist, sondern irgendeine Menge, die nur 2-elementige Teilmengen von [mm] $\{ 1, 2, \dots, 2 n \}$ [/mm] enthaelt.
> Also ist |M| > n für alle n>2.
Nein.
Nochmal von vorne. Zeig es doch wie folgt: angenommen, fuer alle $A, B [mm] \in [/mm] M$ gilt entweder $A = B$ oder $A [mm] \cap [/mm] B = [mm] \emptyset$.
[/mm]
Schreibe $M = [mm] \{ A_1, A_2, \dots, A_k \}$ [/mm] mit [mm] $A_i \cap A_j [/mm] = [mm] \emptyset$ [/mm] fuer $i [mm] \neq [/mm] j$. Dann sollst du zeigen, dass $|M| = k [mm] \le [/mm] n$ sein muss: aus $|M| > n$ folgt also, dass es $A, B [mm] \in [/mm] M$ gibt mit $A [mm] \neq [/mm] B$ und $A [mm] \cap [/mm] B [mm] \neq \emptyset$.
[/mm]
Wenn [mm] $A_i$ [/mm] und [mm] $A_j$ [/mm] paarweise diskunkt sind, so ist ja [mm] $|A_i \cup A_j| [/mm] = [mm] |A_i| [/mm] + [mm] |A_j|$. [/mm] Insbesondere gilt also [mm] $|\bigcup_{i=1}^k A_i| [/mm] = [mm] \sum_{i=1}^k |A_i| [/mm] = 2 k$.
Jetzt ist aber [mm] $\bigcup_{i=1}^k A_i$ [/mm] eine Teilmenge von [mm] $\{ 1, 2, 3, \dots, 2n \}$, [/mm] womit [mm] $\bigcup_{i=1}^k A_i$ [/mm] hoechstens $2 n$ Elemente hat.
Also, was folgt?
LG Felix
|
|
|
| |
|
Das hat mir , so denk ich zumindest, sehr weitergeholfen. Und ich denke auch, was daraus folgt.
Ich versuch das noch mal.
Sei |M|>n. Nehmen wir an, dass für [mm] A,B\in [/mm] M entweder A=B oder [mm] A\cap B=\emptyset.
[/mm]
[mm] M=\{A_{1},\ldot,A_{k}\}
[/mm]
Da [mm] A_{i} [/mm] und [mm] A_{j} [/mm] mit [mm] i\not= [/mm] j paarweise disjunkt sind gilt, [mm] |A_{i} \cup A_{j}| [/mm] = [mm] |A_{i}|+|A_{j}|.
[/mm]
Das bedeutet, [mm] dass|\bigcup_{i=1}^{k}A_{i}|=\summe_{i=1}^{k}|A_{i}|=2k.
[/mm]
Da $ [mm] \bigcup_{i=1}^k A_i [/mm] $ eine Teilmenge von $ [mm] \{ 1, 2, 3, \dots, 2n \} [/mm] $ ist, wobei $ [mm] \bigcup_{i=1}^k A_i [/mm] $ hoechstens $ 2 n $ Elemente hat folgt:
[mm] $|\bigcup_{i=1}^{k}A_{i}| [/mm] = 2k [mm] \le [/mm] 2n$
Da M zweielementige Teilmengen sind folgt: $|M| = k < n$
Das ist ein Widerspruch zur Annahme.
Richtig?
Irgendwie hab ich jetzt das Gefühl, dass ich nur gezeigt hab, dass für $|M|<n gilt, dass [mm] $A,B\inM$ [/mm] disjunkt sind und nicht umgekehrt. Oder folgt das automatisch?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 So 28.03.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
