Aufgabe #112 (COMB),(PolM) < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 12:25 Mi 28.12.2005 | | Autor: | Hanno |
| Aufgabe | | An einem Schachturnier nehmen 2n Spieler teil. Je zwei Spieler spielen höchstens ein Mal gegeneinander. Zeige: wenn es keine drei Spieler gibt, sodass unter diesen dreien jeder gegen jeden gespielt hat, dann wurden höchstens [mm] $n^2$ [/mm] Spiele gespielt. |
Viel Spaß!
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:57 Mo 02.01.2006 | | Autor: | Cool-Y |
Hallo ihr Matheräumler! 
Ich beweise folgende, zur Behauptung in der Aufgabenstellung äquivalente Aussage (wegen [mm] ((A)\Rightarrow(B))\gdw(\neg(B) \Rightarrow \neg(A))):
[/mm]
Wenn mit 2n Spielern unter den Vorraussetzungen der Aufgabenstellung mehr als [mm] n^{2} [/mm] Spiele gespielt wurden, dann gibt es drei Spieler, sodass unter diesen dreien jeder gegen jeden gespielt hat.
Der Beweis erfolgt durch vollständige Induktion nach n:
Induktionsanfang:
n=1
Es gibt also zwei Spieler. Da je zwei Spieler höchstens ein Mal gegeneinander spielen, gibt es höchstens [mm] 1=n^{2} [/mm] Spiele.
Induktionsannahme:
n>1
Wenn mit 2(n-1) Spielern unter den Vorraussetzungen der Aufgabenstellung mehr als [mm] (n-1)^{2} [/mm] Spiele gespielt wurden, dann gibt es drei Spieler, sodass unter diesen dreien jeder gegen jeden gespielt hat.
Induktionsschritt durch Widerspruch:
n>1
Es sei ein Schachtunier mit 2n Spielern und insgesamt mindestens [mm] (n^{2}+1) [/mm] Spielen, bei dem es es keine drei Spieler gibt, sodass unter diesen dreien jeder gegen jeden gespielt hat. Nun muss es wegen dem Schubfachprinzip mindestens einen Spieler [mm] S_{1} [/mm] geben, der mindestens (n+1) Spiele spielen muss. Jeder Spieler, der gegen [mm] S_{1} [/mm] spielt, kann außer [mm] S_{1} [/mm] nur noch gegen die übrigen (2n-(n+1)-1)=(n-2) Spieler spielen. Insgesamt kann ein solcher Spieler also höchstens (n-1) Spiele spielen. Wegen n>1 gibt es mindestens 2 solche Spieler. Diese spielen dann insgesamt zusammen höchstens 2*(n-1). Wenn man das gleiche Tunier ohne diese beiden Spieler und die von ihnen bestrittenen Spielen ausrichten würde, gäbe es natürlich immernoch keine keine drei Spieler, sodass unter diesen dreien jeder gegen jeden gespielt hat. Außerdem hätte dieses Tunier (2n-2)=2(n-1) Spieler und es würden mindestens [mm] ((n^{2}+1)-2*(n-1))=(n^{2}+1-2*n+2)=((n-1)^{2}+2) [/mm] Spiele gespielt. Das wäre ein Widerspruch zur Induktionsannahme. q.e.d.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:35 Di 03.01.2006 | | Autor: | Stefan |
Hallo Mario!
Eine sehr starke Lösung!! ![[respekt]](/images/smileys/respekt.gif "[respekt]")
Liebe Grüße
Stefan
|
|
|
|
