>>> Hast du diesen Monat weniger als 16 Bücher gelesen? - Dann klick hier! <<<


Themenbereiche Themenbereiche Profile Hilfe/Anleitungen Help    
Recent Posts Last 1|3|7 Days Suche Suche Tree Tree View  

Vollst. Induktion

ZahlReich - Mathematik Hausaufgabenhilfe » ---- Archiv: Klassen 12/13 » Beweisführung » Vollst. Induktion « Zurück Vor »

Autor Beitrag
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Chris
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 19. September, 2001 - 15:54:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 19. September, 2001 - 23:42:   Beitrag drucken

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
Seitenanfangvoriger Beitragnächster BeitragSeitenende Link zu diesem Beitrag

Matroid (Matroid)
Suche alle Beiträge dieser Person in dieser Hauptrubrik
Veröffentlicht am Mittwoch, den 19. September, 2001 - 23:52:   Beitrag drucken

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

Beitrag verfassen
Das Senden ist in diesem Themengebiet nicht unterstützt. Kontaktieren Sie den Diskussions-Moderator für weitere Informationen.


Und wie gehts weiter? Klick hier!
Learn-in! Mathematik Soforthilfe. Klick jetzt! Hier könnte Ihre Werbung erscheinen. Kontakt: werbung@zahlreich.de Sprachreisen. Hier kostenlosen Katalog bestellen!

ad
>>> Willst du die besten Proben und Gutscheine? - Dann klick hier! <<<

Informationen: Vollst. Induktion |  Soforthilfe Mathematik |  Online Mathebuch |  Bronstein

Administration Administration Abmelden Abmelden   Previous Page Previous Page Next Page Next Page