Autor |
Beitrag |
Chris
| Veröffentlicht am Mittwoch, den 19. September, 2001 - 15:54: |
|
Suche dringenst problemlösung: 1.Beweise: Eine Menge mit n Elementen Besitzt 2^n Teilmengen 2.Zeige: Zwischen n Telefonteilnehmern bestehen n/2*(n-1) Verbindungen Ich wäre euch sehr dankbar für eure Hilfe Ich sag schon mal danke. Chris |
Matroid (Matroid)
| Veröffentlicht am Mittwoch, den 19. September, 2001 - 23:42: |
|
Hi Chris, hier die 1. Induktionsanfang: n=0, d.h. eine Menge mit 0 Elementen, also die leere Menge. Die leere Menge hat nur die leere Menge als Teilmenge. Die Anzahl der Teilmengen einer 0-elementigen Teilmenge ist 1. Und 20 ist auch 1. Der Induktionsanfang ist damit gezeigt. Induktionsschluß: Sei M eine Menge mit n+1 Elementen gegeben. Betrachte (im Geiste) alle Teilmengen dieser Menge. Wähle nun von den n+1 Elementen ein einzelnes aus. Dieses nenne ich a. Dann gilt: Man kann die Teilmenge von M aufteilen in solche, die a enthalten und solche die a nicht enthalten. Die Aufteilung ist disjunkt. Wieviele Teilmengen von M gibt es, die a enthalten? Nun, man kann aus allen diesen Teilmengen das a entfernen und erkennt, daß man genau die Teilmengen einer n-elementigen Menge vor sich hat. Also, die Anzahl der Teilmengen von M, die a enthalten ist 2n. Wieviele Teilmengen von M gibt es, die a nicht enthalten? Das sind auch 2n, denn weil alle diese Teilmengen a nicht enthalten, sind es zugleich auch die Teilmengen der Mengen M-{a}. M-{a} ist eine Menge mit n Elementen. Insgesamt: Die Anzahl der Teilmengen von M ist 2n+2n = 2n+1. Und das war zu beweisen. Nun die 2: Vorweg: fehlt hier nicht ein "höchstens"? Es ist technisch machbar, aber sicherlich wenig kommunikativ, wenn gleichzeitig jeder Teilnehmer mit jedem anderen Teilnehmer spricht. Aber egal. Induktionsanfang: Zwischen 0 Teilnehmer existieren 0 Verbindungen. Ok. Induktionsschluß: Es sind n+1 Teilnehmer gegeben. Der letzte Teilnehmer heiße a. a hat mit jedem der anderen Teilnehmer eine Verbindung. Das sind dann n Verbindungen. Die übrigen n Teilnehmer haben untereinander (also ohne Verbindungen zu a) genau n*(n-1)/2 Verbindungen. Insgesamt sind das n*(n-1)/2 + n Verbindungen. n*(n-1)/2 + n = n*[(n-1)/2+1] = n*(n+1)/2 qed. Gruß Matroid |
Matroid (Matroid)
| Veröffentlicht am Mittwoch, den 19. September, 2001 - 23:52: |
|
PS: die Aufgabe 2 kennt man auch ohne Geschichte drum herum als schlichte Formel: Sn k=0 k = n*(n+1)/2 oder auch, weil k=0 ja keinen Beitrag ergibt: Sn k=1 k = n*(n+1)/2 |
|