Vollständige Induktion < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:57 Di 01.11.2011 | | Autor: | s9mamajl |
| Aufgabe | Man hat eine Mannschaft mit n Spielern.Ein Spieler passt dem anderen nur, wenn er ihn mag.
Zwischen zwei Spielern A, B gilt immer eine von folgenden beiden Aussagen:A mag B oder B mag A.
Jetzt soll man mit Hilfe vollständiger Induktion zeigen,
dass es für beliebig viele Spieler n mindestens eine Pass-Stafette
(der Ball wird von einem Spieler zum anderen gepasst) existiert,
bei der jeder Spieler genau einmal den Ball hatte. |
Ich habe nun schon versucht, mit Hilfe von 2er Tupeln einen Algorithmus zu finden und auch schon eine Verbindung zu Dominosteinen gefunden, was das angeht.
Jedoch fehlt mir ein Algorithmus.
Diese Aufgabe wurde in der zweiten Woche der LinAlg Vorlesung gestellt, also dürfte die Antwort ja gar nicht schwer sein.
Ich frage mich, ob ich einfach zu kompliziert denke oder irgendwas übersehen habe.
Wenn irgendjemand Tipps oder Einfälle hat, wäre ich dem-/derjenigen sehr verbunden.
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.matheboard.de/thread.php?threadid=471297&sid=472752770aec14ad63271d27262edeef
|
|
| |
|
Hallo s9mamajl, ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
Die Aufgabe ist hier vor einigen Tagen schon einmal behandelt worden.
Schau mal hier.
Kommst Du damit erstmal weiter?
Grüße
reverend
|
|
|
| |
|
> Hallo s9mamajl,
>
> Die Aufgabe ist hier vor einigen Tagen schon einmal
> behandelt worden.
> Schau mal hier.
>
> Kommst Du damit erstmal weiter?
>
> Grüße
> reverend
>
Hallo revered und vielen Dank für die schnelle Antwort!
Nun ich habe die selbe Idee gehabt, wie donquijote, der folgendes geschrieben hat:
>> 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.
Jedoch kann es doch auch sein, dass z.B. bei 5 Spielern A, B, C, D, E, die in folgender stafette stehen: A->B->C->D->E, beim Hinzufügen eines 6. Spielers F so stehen könnten: E->C->A->F->D->B.
Aus meiner Erfahrung in Informatik (auch wenn nicht sehr groß), erinnere ich mich an einen ordnenden Algorithmus.
Der würde hierdrauf angewandt so aussehen:
Vergleiche die Spieler der "n"-ten und "n-1"ten Position der Stafette (also die letzten beiden).
Mag "n-1" "n" nicht, so vertausche die Spieler und gehe weiter zu "n-1" und "n-2".
Mag "n-1" "n" , so gehe weiter zu "n-1" und "n-2".
Wird "1" mit "0" verglichen, so gehe wieder zu "n" und "n-1"
Wird n mal die Position nicht gewechselt, so endet der Algorithmus.
Okay, jetzt habe ich einen sortierenden Algorithmus. Nur bin ich mir nicht sicher, wie die mathematisch korrekte Lösung dieser Aufgabe aussehen könnte.
Ich kenne Vollständige Induktion eigentlich aus Aufgaben mit Summengleichungen und ähnlichem, aber nicht bei soetwas.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:55 Di 01.11.2011 | | Autor: | rollroll |
Oh, noch jemand aus derselben Lin.Alg Vorlesung...
ich suche auch verzweifelt nach einem Algorithmus...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:51 Sa 05.11.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
