USAMO $1989$, Masalah $2$
Masalah $2$ dari USAMO, $1989$: Itu $20$ anggota klub tenis lokal telah menjadwalkan dengan tepat $14$permainan dua orang di antara mereka sendiri, dengan setiap anggota bermain dalam setidaknya satu permainan. Buktikan bahwa dalam jadwal ini harus ada satu set dengan enam pertandingan$12$ pemain yang berbeda.
Upaya saya mencari solusi: Karena ada$20$ pemain, yang masing-masing telah memainkan setidaknya satu pertandingan, jumlah pertandingan paling sedikit yang harus diatur untuk mengakomodasi semua pemain $10$. Sekarang,$4$lebih banyak pertandingan yang tersisa, yang dapat dimainkan oleh paling $8$ ini $20$pemain. Dengan demikian, setidaknya $12$ pemain bisa bermain tidak lebih dari $1$cocok, dan karenanya harus ada satu set enam game dengan$12$pemain yang berbeda . Ini, saya yakin, akan menjadi prinsip panduan dari bukti yang kuat.
Saya memiliki keraguan berikut yang mengaburkan pikiran saya:
- Apakah alasan saya sehat, yaitu bebas dari jebakan?
- Jika benar, bagaimana cara membingkai penalaran di atas dalam bukti matematis yang ketat?
Edit: Seperti yang ditunjukkan oleh Ben di komentar, pernyataan yang dicetak miring tidak bisa dibenarkan. Sepertinya saya mengabaikan banyak kemungkinan saat membingkai bukti ini. Jadi, saya ingin mendapatkan beberapa petunjuk untuk melanjutkan dengan bukti yang lebih masuk akal.
Jawaban
Saya khawatir ada jebakan. Jika Anda mencoba membuktikan bahwa ada 6 game dengan 12 pemain berbeda di antara mereka yang telah memainkan tepat 1 game, Anda akan gagal. Berikut contohnya:
$$ 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$$
Meskipun ada 6 game dengan 12 pemain berbeda, hanya 5 game di antara pemain dengan satu game saja.
Jadi, inilah petunjuknya: bagi pemain menjadi dua kelompok, mereka yang memiliki satu permainan dan mereka yang memiliki lebih banyak. Kemudian pasangkan pemain dengan satu game, setelah memasangkan pemain dengan satu game dengan pemain dengan lebih banyak dan terakhir pemain dengan lebih banyak game.
EDIT : Pendekatan kedua
Jika setiap orang dilihat sebagai puncak dan setiap permainan sebagai tepi, pertanyaan menanyakan untuk membuktikan bahwa ada kecocokan ukuran setidaknya $6$. Secara ekivalen, kita bisa membuktikan bahwa ukuran itu paling pas$MM$ berukuran setidaknya $6$. Perhatikan bahwa pencocokan maksimum membagi simpul menjadi dua set, satu dengan tepi di$MM$, dari ukuran $2\cdot |MM|$, dan satu tanpa, ukuran $20 - 2\cdot |MM|$untuk masalah kita. Karena semua simpul setidaknya memiliki derajat$1$, kami menyimpulkan bahwa setidaknya ada $20 - 2\cdot |MM|$tepi antara dua partisi. Sekarang,
$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$