USAMO $1989$, Problème $2$
Problème $2$ de USAMO, $1989$: Le $20$ les membres d'un club de tennis local ont programmé exactement $14$jeux à deux entre eux, chaque membre jouant à au moins un jeu. Prouvez que dans ce calendrier, il doit y avoir une série de six matchs avec$12$ acteurs distincts.
Ma tentative de solution: puisqu'il y a$20$ joueurs, dont chacun a joué au moins un match, le moins de matchs qui doivent être organisés pour accueillir tous les joueurs serait $10$. Maintenant,$4$il reste plus de matchs, qui peuvent être joués par au plus $8$ de ces $20$joueurs. Ainsi, au moins $12$ des joueurs ne peuvent jouer plus de $1$match, et donc il doit exister un ensemble de six jeux avec$12$acteurs distincts . Ce sera, je crois, le principe directeur d'une preuve rigoureuse.
J'ai les doutes suivants qui obscurcissent mon esprit:
- Mon raisonnement est-il sain, c'est-à-dire exempt de tout piège?
- S'il est correct, comment encadrer le raisonnement ci-dessus dans une preuve mathématiquement rigoureuse?
Edit: Comme l'a souligné Ben dans les commentaires, la déclaration en italique est injustifiée. J'ai négligé beaucoup de possibilités en encadrant cette preuve, semble-t-il. Ainsi, j'aimerais avoir quelques indices pour procéder à des preuves plus raisonnables.
Réponses
J'ai peur qu'il y ait un écueil. Si vous essayez de prouver qu'il y a 6 parties avec 12 joueurs distincts parmi ceux qui ont joué exactement 1 partie, vous échouerez. Voici un exemple:
$$ 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$$
Bien qu'il y ait 6 jeux avec 12 joueurs distincts, seuls 5 jeux sont entre les joueurs avec exactement un jeu.
Voici donc un indice: divisez les joueurs en deux groupes, ceux avec un match et ceux avec plus. Ensuite, associez les joueurs à un jeu, après avoir jumelé des joueurs avec un jeu avec des joueurs avec plus et enfin des joueurs avec plus de jeux.
EDIT : Deuxième approche
Si chaque personne est vue comme un sommet et chaque jeu comme un bord, la question demande de prouver qu'il y a au moins une correspondance de taille $6$. De manière équivalente, nous pouvons prouver que la taille de la correspondance maximale$MM$ est de taille au moins $6$. Notez qu'une correspondance maximale partitionne les sommets en deux ensembles, l'un avec des arêtes dans le$MM$, de taille $2\cdot |MM|$, et un sans, de taille $20 - 2\cdot |MM|$pour notre problème. Puisque tous les sommets sont de degré au moins$1$, nous concluons qu'il y a au moins $20 - 2\cdot |MM|$bords entre les deux cloisons. Maintenant,
$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$