0 Daumen
974 Aufrufe

Kann mir jemand helfen und die lösungsschritte zeigen, da ich es nicht verstanden habe

(a) Sei M = {1; 2; 3; 4; 5; 6} und X = (M über 3) die Menge aller 3-elementigen Teilmengen von M. Die Aquivalenzrelation  X X ist wie folgt deniert: {a1; a2; a3} ~ {b1; b2; b3} ⇔ a1 + a2 + a3 = b1 + b2 + b3

Wieviele Aquivalenzklassen hat die Relation?

Geben Sie ein Reprasentanten- system der Relation an und bestimmen Sie die Aquivalenzklassen [  f1; 2; 5g]und [f1; 3; 6g]Hinweis: Uberlegen Sie welche Summen sich  uber 3-elementigen Teilmengen von M ergeben konnen.

(b) Wieviele Aquivalenzklassen hat die Relation  , wenn man die Menge M durchdie Menge aller Zahlen von 1 bis n ersetzt? Begrunden Sie, dass es in diesem Fall mindestens eine Aquivalenzklasse geben muss, in der mindestens ln(n1)18mTeilmengen von X liegen.

Gefragt von

1 Antwort

0 Daumen

 

(a) Sei M = {1; 2; 3; 4; 5; 6} und X = (M über 3) die Menge aller 3-elementigen Teilmengen von M. Die Äquivalenzrelation ~ ⊆  X X ist wie folgt definiert: {a1; a2; a3} ~ {b1; b2; b3} ⇔ a1 + a2 + a3 = b1 + b2 + b3

Wieviele Äquivalenzklassen hat die Relation?

Es kommen als Summe alle natürlichen Zahlen von 1+2+3=6       bis 4+5+6=15 vor.

Somit gibt's 10 Äquivalenzklassen

Aufzählung legt dies nahe und ist gleich ein Repräsentantensystem für diese Klassen

1 2 3 Summe 6

1 2 4 Summe 7

1 2 5 Summe 8

1 2 6 Summe 9

1 3 6 Summe 10

1 4 6 Summe 11

1 5 6 Summe 12

2+5+6 Summe 13

3+5+6 Summe 14

4+5+6 Summe 15

Die beiden gesuchten Äquivalenzklassen:   Bitte Klammern… selbst ergänzen und eventuell vergessene Summen von 3 verschiedenen Summanden die die angebene Summe ergeben. Die Folgenden sind alle, die mit einfallen:

Klasse 1:            1 2 5 hat Summe 8 geht auch mit 1 3 4

Klasse 2:             1 3 6 hat Summe 10 geht auch mit 1 4 5,  2 3 5

Geben Sie ein Repräsentanten- system der Relation an und bestimmen Sie die Aquivalenzklassen [  f1; 2; 5g]und [f1; 3; 6g]Hinweis: Uberlegen Sie welche Summen sich  uber 3-elementigen Teilmengen von M ergeben konnen.

(b) Wieviele Aquivalenzklassen hat die Relation  , wenn man die Menge M durchdie Menge aller Zahlen von 1 bis n ersetzt? Begrunden Sie, dass es in diesem Fall mindestens eine Aquivalenzklasse geben muss, in der mindestens n(n-1)/18 Teilmengen von X liegen.

Die Summen können von 1+2+3 = 6 bis (n-2) + (n-1) +n = 3n-3 variieren.

Deshalb gibt es (3n-3) - 6 + 1 = 3n - 8 Äquivalenzklassen.

Probe: Oben war n=6. 3*6 - 8 = 10. ok.

Es gibt n! / (3! (n-3)!) = n(n-1)(n-2)/6    dreielementige Teilmengen von einer Menge mit n Elementen.

Nun teile ich mal diese Zahl durch die Zahl der Äquivalenzklassen  (Schubfachprinzip in mindestens einer von s Schubladen müssen sich x/s der  x Gegenstände befinden)

n(n-1)* (n-2)/(6*(3n -8))

= n(n-1)     * (n-2)/(18n-48) > n(n-1)/18        Ungleichung gilt für n> 8/3 und n muss ja minsdestens 3 sein, da es sich um Mengen nit 3 Elementen handelt.

Beweis der Ungleichung

(n-2)/(18n-48) > 1/18              |*Hauptnenner    n≥ 3

18(n-2) > 18n - 48

18n - 36 > 18n -48

-36 > -48 ok.

Beantwortet von 142 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...