Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:55 Sa 29.10.2011 | | Autor: | rollroll |
| Aufgabe | Eine Basketballmannschaft mit n (n>1) Spielern hat ein sehr außergewöhnliches Beziehungsgeflecht: für je zwei
Spieler A und B gilt immer nur genau eine der beiden Aussagen:
- Spieler A kann Spieler B gut leiden.
- Spieler B kann Spieler A gut leiden.
Bei einer Übung im Training ist nur ein Ball im Spiel, der von einem Spieler zum anderen gepasst werden soll (,,Pass-
Staffete''). Allerdings passen die Spieler immer nur zu denen, die sie selbst gut leiden können.
Zeigen Sie m.H. der Vollständigen Induktion, dass es unabhängig von der Anzahl n der Spieler eine Pass-Staffete gibt, bei der jeder Spieler genau einmal
den Ball hat. |
Also das allgemeine Beweisverfahren der Vollst. Ind. ist mir klar. ich hab auch kein problem damit, Summenformeln oder Teilbarkeiten zu beweisen.
Aber hier weiß ich i.wie gar nicht, wie ich ansetzen soll...
|
|
| |
|
> Eine Basketballmannschaft mit n (n>1) Spielern hat ein
> sehr außergewöhnliches Beziehungsgeflecht: für je zwei
> Spieler A und B gilt immer nur genau eine der beiden
> Aussagen:
> - Spieler A kann Spieler B gut leiden.
> - Spieler B kann Spieler A gut leiden.
> Bei einer Übung im Training ist nur ein Ball im Spiel,
> der von einem Spieler zum anderen gepasst werden soll
> (,,Pass-
> Staffete''). Allerdings passen die Spieler immer nur zu
> denen, die sie selbst gut leiden können.
> Zeigen Sie m.H. der Vollständigen Induktion, dass es
> unabhängig von der Anzahl n der Spieler eine Pass-Staffete
> gibt, bei der jeder Spieler genau einmal
> den Ball hat.
> Also das allgemeine Beweisverfahren der Vollst. Ind. ist
> mir klar. ich hab auch kein problem damit, Summenformeln
> oder Teilbarkeiten zu beweisen.
> Aber hier weiß ich i.wie gar nicht, wie ich ansetzen
> soll...
Beweisidee: Induktionsanfang für n=2....
Induktionsschritt (das ist nix zum "rechnen" mit Summenformeln etc.)
Betrachte eine "zulässige" Passstaffete [mm] P_n [/mm] und einen n+1-ten Spieler C.
Es müssen mehrere Fälle unterschieden werden:
Wenn es A und B gibt, sodass:
A kann C gut leiden,
C kann B gut leiden,
A passt in [mm] P_n [/mm] zu B,
so kann C zwischen A und B "eingebaut" werden, d.h. aus A->B in [mm] P_n [/mm] wird A->C->B in [mm] P_{n+1}
[/mm]
Ist dies nicht der Fall, so kann man sich überlegen, dass entweder
C den ersten Spieler der Staffete [mm] P_n [/mm] gut leiden kann und somit an den Anfang von [mm] P_{n+1} [/mm] gesetzt werden kann, oder
der letzte Spieler von [mm] P_n [/mm] C gut leiden kann und somit C ans Ende gesetzt werden kann.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:44 Sa 29.10.2011 | | Autor: | donquijote |
> > Eine Basketballmannschaft mit n (n>1) Spielern hat ein
> > sehr außergewöhnliches Beziehungsgeflecht: für je zwei
> > Spieler A und B gilt immer nur genau eine der beiden
> > Aussagen:
> > - Spieler A kann Spieler B gut leiden.
> > - Spieler B kann Spieler A gut leiden.
> > Bei einer Übung im Training ist nur ein Ball im Spiel,
> > der von einem Spieler zum anderen gepasst werden soll
> > (,,Pass-
> > Staffete''). Allerdings passen die Spieler immer nur zu
> > denen, die sie selbst gut leiden können.
> > Zeigen Sie m.H. der Vollständigen Induktion, dass es
> > unabhängig von der Anzahl n der Spieler eine Pass-Staffete
> > gibt, bei der jeder Spieler genau einmal
> > den Ball hat.
> > Also das allgemeine Beweisverfahren der Vollst. Ind.
> ist
> > mir klar. ich hab auch kein problem damit, Summenformeln
> > oder Teilbarkeiten zu beweisen.
> > Aber hier weiß ich i.wie gar nicht, wie ich ansetzen
> > soll...
> Beweisidee: Induktionsanfang für n=2....
> Induktionsschritt (das ist nix zum "rechnen" mit
> Summenformeln etc.)
> Betrachte eine "zulässige" Passstafette [mm]P_n[/mm] und einen
> n+1-ten Spieler C.
> Es müssen mehrere Fälle unterschieden werden:
> Wenn es A und B gibt, sodass:
> A kann C gut leiden,
> C kann B gut leiden,
> A passt in [mm]P_n[/mm] zu B,
> so kann C zwischen A und B "eingebaut" werden, d.h. aus
> A->B in [mm]P_n[/mm] wird A->C->B in [mm]P_{n+1}[/mm]
> Ist dies nicht der Fall, so kann man sich überlegen, dass
> entweder
> C den ersten Spieler der Staffete [mm]P_n[/mm] gut leiden kann und
> somit an den Anfang von [mm]P_{n+1}[/mm] gesetzt werden kann, oder
> der letzte Spieler von [mm]P_n[/mm] C gut leiden kann und somit C
> ans Ende gesetzt werden kann.
>
Vielleicht noch ein bisschen einfacher:
Ist [mm] P_n [/mm] die Stafette [mm] A_1->A_2->...->A_n, [/mm] so kann man unterscheiden:
Kann C [mm] A_1 [/mm] gut leiden, so setze ihn an den Anfang,
Kann C niemanden gut leiden, so setze ihn ans Ende,
Ansonsten sei [mm] A_k [/mm] mit k>1 der erste Spieler in [mm] P_n, [/mm] den C gut leiden kann. In diesem Fall kann C zwischen [mm] A_{k-1} [/mm] und [mm] A_k [/mm] eingebaut werden.
|
|
|
| |
|
Hallo rollroll,
hattest Du schon Graphentheorie? Diese Aufgabe ist eine Form des ![[]](/images/popup.gif) Hamiltonkreisproblems im gerichteten Graphen.
Dafür gibt es eine ganze Reihe möglicher hinreichender Kriterien, auch mehrere notwendige.
So stellt ein Spieler, der alle anderen mag, aber eben von niemandem gemocht wird, ja ein Problem dar (ebenso wie umgekehrt). Er muss am Anfang der Kette stehen.
Unlösbar wäre die Aufgabe, wenn es zwei Spieler gäbe, die von niemandem gemocht werden. Das ist aber einfach auszuschließen.
Ansonsten hier noch ein Tipp: im vorliegenden Graphen ist jeder Knoten mit jedem andern durch genau eine gerichtete Kante verbunden.
Ich höre hier mal auf, weil das alles für Dich nutzlos ist, wenn Du noch gar keine Graphentheorie hattest.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:31 Sa 29.10.2011 | | Autor: | rollroll |
Hi reverend, nein, graphentheorie hatte ich noch nicht gehabt... soll i-wie mit induktion gehen
|
|
|
| |
|
Hallo nochmal,
> Hi reverend, nein, graphentheorie hatte ich noch nicht
> gehabt... soll i-wie mit induktion gehen
Dann lassen wir diesen Pfad mal. 
Verfolge doch die Tipps von donquijote, damit kannst Du zum Ziel kommen.
Grüße
reverend
PS: Denk mal über folgendes nach: in gemittelt drei Viertel aller Fälle wird man einen neu hinzukommenden Spieler an den Anfang oder das Ende der Kette setzen können. Wenn das aber beides nicht möglich ist, wie kann man dann garantieren, dass er irgendwo in der Mitte der Kette eingefügt werden kann?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:16 Mo 31.10.2011 | | Autor: | rollroll |
Hi, bin leider in letzter zeit nicht dazu gekommen, mir gedanken zu machen. werde das morgen nochholen...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:52 Di 01.11.2011 | | Autor: | rollroll |
Er kann doch dann problemlos eingefügt werden, wenn der spieler den nachfolgenden spieler leiden kann, oder??
Ich habe auch donquijote's Ausführungen gelesen und eigentlich auch verstanden, aber auf einen Algorithmus komme ich trotzdem nicht...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:29 Di 01.11.2011 | | Autor: | rollroll |
Weiß jemand was?
|
|
|
| |
|
Hallo rollroll,
In seiner Mitteilung hat quijote doch einen
Algorithmus formuliert, mit dem man eine vorliegende
Pass-Stafette von n Spielern zu einer Stafette der Länge
n+1 erweitern kann, wenn ein zusätzlicher Spieler C
dazu kommt, dessen Relationen zu jedem der n schon
vorhandenen Spieler klar sind:
Ist $ [mm] P_n [/mm] $ die Stafette $ [mm] A_1->A_2->...->A_n, [/mm] $ so kann man
unterscheiden:
Kann C $ [mm] A_1 [/mm] $ gut leiden, so setze ihn an den Anfang:
$\ (\ [mm] Ergebnis:\quad P_{n+1}\ [/mm] =\ [mm] C->A_1->A_2->...->A_n\ [/mm] ) $
Kann C niemanden gut leiden, so setze ihn ans Ende,
$\ (\ [mm] Ergebnis:\quad P_{n+1}\ [/mm] =\ [mm] A_1->A_2->...->A_n->C\ [/mm] ) $
Ansonsten sei $ [mm] A_k [/mm] $ mit k>1 der erste Spieler in $ [mm] P_n, [/mm] $ den
C gut leiden kann. In diesem Fall kann C zwischen
$ [mm] A_{k-1} [/mm] $ und $ [mm] A_k [/mm] $ eingebaut werden:
$\ (\ [mm] Ergebnis:\quad P_{n+1}\ [/mm] =\ [mm] A_1->A_2->...->A_{k-1}->C->A_k->...->A_n\ [/mm] ) $
LG Al-Gorismi
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:07 Mi 02.11.2011 | | Autor: | rollroll |
Ok, aber selbst wenn ich das als Algorithmus annehme, wie soll ich das beweisen??
|
|
|
| |
|
> Ok, aber selbst wenn ich das als Algorithmus annehme, wie
> soll ich das beweisen??
Hallo [mm] roll^2
[/mm]
natürlich ist keineswegs gemeint, dass du dies einfach
annehmen sollst, ohne es zu durchschauen.
Der Induktionsbeweis soll ja über die Anzahl n der
Spieler erfolgen. Die Verankerung bei n=2 ist ganz
leicht zu formulieren. Wenn du willst, kannst du z.B.
auch noch etwa n=3 und n=4 durch einfache Über-
legungen und Diagramme klar machen.
Für den allgemeinen Induktionsschritt von n auf n+1
benützt du dann die angegebene Idee von donquijote.
Darin wird ja ausführlich erklärt, wie man aus einer
vorgegebenen Pass-Sequenz [mm] P_n [/mm] für eine Gruppe von
n Spielern eine Sequenz [mm] P_{n+1} [/mm] konstruieren kann für
den Fall, dass ein weiterer Spieler dazu kommt (Spieler
Nummer (n+1) oder Spieler C), für welchen (nach der
Voraussetzung der ganzen Aufgabe) auch schon fest
steht, wie seine Relationen zu jedem anderen Spieler
aussehen: stets entweder [mm] C\to{A_k} [/mm] oder [mm] A_k\to{C} [/mm] ).
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:06 Mi 02.11.2011 | | Autor: | rollroll |
Was donquijote geschreiben hat, versteje ich ja auch soweit. Aber das ist doch noch nicht der beweis , oder?
|
|
|
| |
|
> Was donquijote geschreiben hat, verstehe ich ja auch
> soweit. Aber das ist doch noch nicht der beweis , oder?
Nein. Aber es ist ein ganz wesentlicher Bestandteil davon.
Wenn du auch meine Anmerkungen gelesen hast, so hast
du alles Nötige für einen sehr schönen Beweis beisammen.
Den letzten Schritt, nämlich das Zusammenfügen aller
vorliegenden Hilfen zum Verfassen des Beweises über-
lassen wir dir aber selber.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:51 Mi 02.11.2011 | | Autor: | rollroll |
Ok, ich versuch's dann mal zusammenzufügen und morgen hier zu posten.
Könntest du dann zur Kontrolle bitte nochmal drüber gucken??
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:19 Do 03.11.2011 | | Autor: | rollroll |
Mein ,,Beweisversuch'':
In.anfang:
für n = 2 Spieler A und B gilt:
Fall 1: A kann B gut leiden --> A passt zu B
Fall 2: B kann A gut leiden --> B passt zu A Staffete möglich
Ind.behauptung
Unabhängig von der Anzahl n (n [mm] \in [/mm] IN >1 fest) gibt es eine Pass-Staffete, sodass jeder Spieler ganeu einmal den Ball hatte.
Ind.schritt:
Algorithmus für den Fall, dass eine Pass-Staffete mit n Spielern zu einer Staffete der Länge n+1 erweitern wird, wenn ein zusätzlicher Spieler C
dazu kommt, dessen Relationen zu jedem der n schon
vorhandenen Spieler klar sind:
Ist [mm] P_{n} [/mm] die Staffete A1--> A2--> ... --> [mm] A_{n}, [/mm] so kann man
unterscheiden:
Kann C A1 gut leiden, so setze ihn an den Anfang:
$ \ (\ [mm] Ergebnis:\quad P_{n+1}\ [/mm] =\ [mm] C->A_1->A_2->...->A_n\ [/mm] ) $
Kann C niemanden gut leiden, so setze ihn ans Ende,
$ \ (\ [mm] Ergebnis:\quad P_{n+1}\ [/mm] =\ [mm] A_1->A_2->...->A_n->C\ [/mm] ) $
Ansonsten sei [mm] A_{k} [/mm] mit k>1 der erste Spieler in [mm] P_{n} [/mm] den
C gut leiden kann. In diesem Fall kann C zwischen [mm] A_{k-1} [/mm] und [mm] A_{k}
[/mm]
eingebaut werden:
$ \ (\ [mm] Ergebnis:\quad P_{n+1}\ [/mm] =\ [mm] A_1->A_2->...->A_{k-1}->C->A_k->...->A_n\ [/mm] ) $
Unter der Vorausstzung, dass die Relation des neu hinzukommenden Spielers zu den anderen so aussieht: [mm] C-->A_{k} [/mm] bzw. [mm] A_{k}--> [/mm] C
Ist das der ganze Beweis???
|
|
|
| |
|
> Mein ,,Beweisversuch'':
>
> In.anfang:
>
> für n = 2 Spieler A und B gilt:
> Fall 1: A kann B gut leiden --> A passt zu B
> Fall 2: B kann A gut leiden --> B passt zu A Staffete
> möglich
>
> Ind.behauptung
>
> Unabhängig von der Anzahl n (n [mm]\in[/mm] IN >1 fest) gibt es
> eine Pass-Staffete, sodass jeder Spieler ganeu einmal den
> Ball hatte.
>
> Ind.schritt:
>
> Algorithmus für den Fall, dass eine Pass-Staffete mit n
> Spielern zu einer Staffete der Länge n+1 erweitern wird,
> wenn ein zusätzlicher Spieler C
> dazu kommt, dessen Relationen zu jedem der n schon
> vorhandenen Spieler klar sind:
>
> Ist [mm]P_{n}[/mm] die Staffete A1--> A2--> ... --> [mm]A_{n},[/mm] so kann
> man
> unterscheiden:
> Kann C A1 gut leiden, so setze ihn an den Anfang:
> [mm]\ (\ Ergebnis:\quad P_{n+1}\ =\ C->A_1->A_2->...->A_n\ )[/mm]
>
> Kann C niemanden gut leiden, so setze ihn ans Ende,
> [mm]\ (\ Ergebnis:\quad P_{n+1}\ =\ A_1->A_2->...->A_n->C\ )[/mm]
>
> Ansonsten sei [mm]A_{k}[/mm] mit k>1 der erste Spieler in [mm]P_{n}[/mm] den
> C gut leiden kann. In diesem Fall kann C zwischen [mm]A_{k-1}[/mm]
> und [mm]A_{k}[/mm]
> eingebaut werden:
>
> [mm]\ (\ Ergebnis:\quad P_{n+1}\ =\ A_1->A_2->...->A_{k-1}->C->A_k->...->A_n\ )[/mm]
>
> Unter der Vorausstzung, dass die Relation des neu
> hinzukommenden Spielers zu den anderen so aussieht:
> [mm]C-->A_{k}[/mm] bzw. [mm]A_{k}-->[/mm] C
>
> Ist das der ganze Beweis???
nur ein paar Bemerkungen:
1.) die Behauptung gehört an den Anfang, dann Verankerung
("Induktionsanfang"), dann Induktionsschritt, dann die
den Beweis abschließende Zusammenfassung
2.) den Text
> Algorithmus für den Fall, dass eine Pass-Staffete mit n
> Spielern zu einer Staffete der Länge n+1 erweitern wird,
> wenn ein zusätzlicher Spieler C
> dazu kommt, dessen Relationen zu jedem der n schon
> vorhandenen Spieler klar sind:
solltest du anders (verständlich) formulieren
3.) die Voraussetzung, die du erst ganz am Schluss erwähnst,
sollte eher am Anfang des Beweises bzw. des Induktionsschrittes
stehen
Mach dir den logischen Gang des Beweises nochmals klar,
indem du den Text laut liest ...
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:32 Do 03.11.2011 | | Autor: | rollroll |
Ok, wenn ich das beherzigt habe, kann ich aber ein qed daruntersetzen und bin fertig, oder?
|
|
|
| |
|
> Ok, wenn ich das beherzigt habe, kann ich aber ein qed
> daruntersetzen und bin fertig, oder?
OK, beherzige und setze !
|
|
|
| |
|
Hi,
also ich beschäftige mich auch gerade mit dieser Aufgabe und hab mir als Hilfe die Beiträge hier durchgelesen.
Nun aber eine wichtige Frage :
Hier ist ja der Tipp mit der Fallunterscheidung gegeben worden.
In der Aufgabenstellung steht aber man soll zeigen, dass unabhänig von der Zahl der Spieler immer eine Staffete existiert, bei der jeder Spieler genau einmal den Ball hat. Reicht es dann nicht, einen Fall herauszunehmen bei dem das zutrifft und dann zuziegen, dass dieser unabhänig von der Spielerzahl existiert.
Beispiel: Ich habe die zulässige Staffete Pn: { a1,a2,...,an} und es kommt ein Spieler an+1 hinzu, der keinen leiden kann, den setze ich dann ans Ende der Staffete. Es folgt ja: Alle Spieler a1-an können ihn leiden, sitzt er am Ende der Staffete gibt es dann genau eine Passfolge bei dem jeder Spieler einmal angespielt wird.
Ich bin mir nur nicht ganz sicher, wie ich das zeigen kann.
hoffe ihr könnt mir weiterhelfen
mfg ConstantinJ
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:00 Do 03.11.2011 | | Autor: | rollroll |
Hmm, stimmt, es soll ja unabhängig zahl der spieler sein... Stimmt der beweis dann trotzdem noch?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:22 Do 03.11.2011 | | Autor: | leduart |
Hallo
Das genau beweist man doch mit Indukion, wo hängt dein Beweis denn von der genauen Zahl der Sp. ab?
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:44 Do 03.11.2011 | | Autor: | rollroll |
Also ist der beweis weiterhin richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:40 Fr 04.11.2011 | | Autor: | leduart |
Hallö
Du sollst einen Beweis nicht "glauben" weil in irgendnem forum jemand sagt er sei richtig! Er muss jedem -also auch dich- überzeugen. Wenn du an einer stelle Zweifel hast, formulier die möglichst genau. entwede<font class="ForumMessage" color="#666666"> http://img254.imageshack.us/img254/5140/1234um.jpg
</font>
hst du dann selbst, was den Zweifel aufhebt, oder du hast das Gegenteil überzeugend bewiesen, oder jemand hie zeigt dir, warum deine Zweifel nicht berechtigt sind und danach bist du überzeugt.
das ist doch genau das tolle an Mathe:Nicht immer kommt man selbst auf nen einfachen beweis, aber wenn man ihn vorgeführt kriegt und nachvollzi[#000000]ht ist er eben richtig) überzeugendoder falsch bzq.unvollständig.
gruss leduart
[/#000000]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:19 Do 03.11.2011 | | Autor: | leduart |
Hallo
ich versteh nicht ganz, wie du das meinst. Auch du setzest vorraus dass es eine Staffel mit n gibt. dann nimmst du einen sehr speziellen (Allehasser) hinzu und hast ne n+1 Staffel.
damit hast du doch nicht gezeigt, dass es sicher ne n+1 Staffel gibt. denn du brauchst ja unbedingt den Allehasser.
Was willst du denn zeigen? Dass immer nur Alleshasser dazukommen ?
Vielleicht hab ich deine Idee aber nicht verstanden? Willst du ne Induktion oder irgendwas anderes?
Gruss leduart
|
|
|
| |
|
Hallo zusammen,
um auch anschaulich zu verifizieren, dass der erarbeitete
Algorithmus stets eine Stafette durch einen vollständigen
gerichteten einfachen Graph mit n Knoten liefert, habe
ich den Algorithmus durch ein Programm realisiert.
Der Graph wird zunächst durch eine Matrix A aus Nullen
und Einsen mit [mm] A_{ii}=0 [/mm] und [mm] A_{ik}+A_{ki}=1 [/mm] (i≠k) definiert,
welche durch Zufallszahlen erzeugt wird.
Am Schluss wird das Ergebnis graphisch dargestellt.
Ein Beispiel:
[Dateianhang nicht öffentlich]
Sollte jemand am Programm interessiert sein, kann er
oder sie mich per PN anfragen. Das Programm ist in
Pascal verfasst.
LG Al-Chw.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
|
