USAMO $1989$, Problem $2$

Question

Problem $2$ von USAMO, $1989$: Das $20$ Mitglieder eines örtlichen Tennisclubs haben genau geplant $14$Zwei-Personen-Spiele untereinander, wobei jedes Mitglied in mindestens einem Spiel spielt. Beweisen Sie, dass es innerhalb dieses Zeitplans einen Satz von sechs Spielen mit geben muss$12$ verschiedene Spieler.

Mein Lösungsversuch: Da gibt es$20$ Spieler, von denen jeder mindestens ein Spiel gespielt hat, die geringste Anzahl von Spielen, die organisiert werden müssen, um alle Spieler aufzunehmen, wäre $10$. Jetzt,$4$weitere Spiele sind links, die durch wiedergegeben werden können höchstens $8$ von diesen $20$Spieler. Also zumindest $12$ der Spieler dürfen nicht mehr als spielen $1$Match, und daher muss es einen Satz von sechs Spielen mit existieren$12$verschiedene Spieler . Ich glaube, dies wird das Leitprinzip eines strengen Beweises sein.

Ich habe die folgenden Zweifel, die meinen Geist trüben:

1. Ist meine Argumentation vernünftig, dh frei von Fallstricken?
2. Wenn dies richtig ist, wie kann man die obigen Überlegungen in einen mathematisch strengen Beweis einordnen?

Bearbeiten: Wie von Ben in den Kommentaren ausgeführt, ist die kursive Aussage nicht gerechtfertigt. Ich habe viele Möglichkeiten übersehen, als ich diesen Beweis aufgestellt habe, wie es scheint. Daher möchte ich einige Hinweise erhalten, um mit vernünftigeren Beweisen fortzufahren.

Answer 1

Ich fürchte, es gibt eine Falle. Wenn Sie versuchen zu beweisen, dass es 6 Spiele mit 12 verschiedenen Spielern unter denen gibt, die genau 1 Spiel gespielt haben, werden Sie scheitern. Hier ist ein Beispiel:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

Während es 6 Spiele mit 12 verschiedenen Spielern gibt, sind nur 5 Spiele zwischen den Spielern mit genau einem Spiel.

Hier ist ein Hinweis: Teilen Sie die Spieler in zwei Gruppen auf, die mit einem Spiel und die mit mehr. Dann koppeln Sie Spieler mit einem Spiel, nachdem Sie Spieler mit einem Spiel mit Spielern mit mehr und schließlich Spieler mit mehr Spielen gepaart haben.

EDIT : Zweiter Ansatz

Wenn jede Person als Scheitelpunkt und jedes Spiel als Rand gesehen wird, muss die Frage beweisen, dass es mindestens eine Größenanpassung gibt $6$. Gleichermaßen können wir beweisen, dass die Größe der maximalen Übereinstimmung$MM$ ist mindestens so groß $6$. Beachten Sie, dass eine maximale Übereinstimmung die Scheitelpunkte in zwei Gruppen unterteilt, eine mit Kanten in der$MM$von Größe $2\cdot |MM|$und eine ohne Größe $20 - 2\cdot |MM|$für unser Problem. Da alle Eckpunkte mindestens graduell sind$1$schließen wir, dass es zumindest gibt $20 - 2\cdot |MM|$Kanten zwischen den beiden Partitionen. Jetzt,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$