USAMO $1989$, Problem $2$

Question

Problem $2$ z USAMO, $1989$: The $20$ członkowie lokalnego klubu tenisowego dokładnie zaplanowali $14$gry dwuosobowe między sobą, przy czym każdy członek gra w co najmniej jednej grze. Udowodnij, że w tym harmonogramie musi być zestaw sześciu gier z$12$ różni gracze.

Moja próba rozwiązania: ponieważ istnieją$20$ graczy, z których każdy rozegrał przynajmniej jedną grę, najmniejsza liczba meczów, które należy zorganizować, aby pomieścić wszystkich graczy, byłaby $10$. Teraz,$4$pozostało więcej meczów, które można rozegrać najwyżej $8$ tych $20$gracze. A więc przynajmniej $12$ graczy nie może grać więcej niż $1$mecz, a zatem musi istnieć zestaw sześciu gier z$12$różni gracze . Wierzę, że będzie to naczelna zasada rygorystycznego dowodu.

Mam następujące wątpliwości:

1. Czy moje rozumowanie jest rozsądne, tj. Wolne od jakichkolwiek pułapek?
2. Jeśli to prawda, jak ująć powyższe rozumowanie w matematycznie rygorystyczny dowód?

Edycja: Jak zauważył Ben w komentarzach, stwierdzenie kursywą jest nieuzasadnione. Wydaje się, że przeoczyłem wiele możliwości podczas kadrowania tego dowodu. Dlatego chciałbym uzyskać kilka wskazówek, aby przejść do bardziej rozsądnego dowodu.

Answer 1

Obawiam się, że jest pułapka. Jeśli spróbujesz udowodnić, że jest 6 gier z 12 różnymi graczami spośród tych, którzy rozegrali dokładnie 1 grę, poniesiesz porażkę. Oto przykład:

$$ 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$$

Chociaż istnieje 6 gier z 12 różnymi graczami, tylko 5 gier jest między graczami z dokładnie jedną grą.

Podpowiedź: podziel graczy na dwie grupy, tych z jedną grą i tych z większą liczbą. Następnie sparuj graczy z jedną grą, po sparuj graczy z jedną grą z graczami z większą liczbą gier i wreszcie z graczami z większą liczbą gier.

EDYCJA : drugie podejście

Jeśli każda osoba jest postrzegana jako wierzchołek, a każda gra jako przewaga, pytanie ma na celu udowodnienie, że istnieje co najmniej dopasowanie rozmiaru $6$. Równoważnie możemy udowodnić, że wielkość maksymalnego dopasowania$MM$ ma co najmniej rozmiar $6$. Zauważ, że maksymalne dopasowanie dzieli wierzchołki na dwa zestawy, jeden z krawędziami w formacie$MM$, wielkości $2\cdot |MM|$i jeden bez rozmiaru $20 - 2\cdot |MM|$dla naszego problemu. Ponieważ wszystkie wierzchołki mają co najmniej stopień$1$dochodzimy do wniosku, że są co najmniej $20 - 2\cdot |MM|$krawędzie między dwiema przegrodami. Teraz,

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