Jump to content
Elbert

PERTENGKARAN

Recommended Posts

Ada 799 tim. masing masing tim bertengkar dengan 1 tim masing masing sekali. Buktikan ada himpunan A dan B di mana di mana banyak  anggota himpunan A dan B adalah 7 sehingga setiap tim di himpunan A menang terhadap setiap tim di himpunan B

  • Upvote 1

Share this post


Link to post
Share on other sites

Untuk menyelesaikan soal ini, buat sebuah complete graph dengan semua 799 tim sebagai titik verteks dan jika tim X mengalahkan tim Y, maka dibuat sisi terarah dari X ke Y. Untuk menyelesaikan soal ini, akan diobservasi suatu struktur yang kita namankan "Bintang Tujuh" dan kita hitung banyaknya struktur ini di graf yang kita miliki.

Suatu struktur "Bintang Tujuh" (selanjutnya kita sebut bintang untuk kemudahan penulisan) didefinisikan sebagai suatu tim X dengan 7 sisi terarah dari X ke 7 tim lainnya. Jika X mengalahkan $n$ tim, maka dapat dibentuk $\binom{n}{7}$ bintang berbeda yang berpusat di X.

Misalkan $V$ adalah himpunan semua tim. Perhatikan bahwa banyaknya bintang yang ada di graf adalah jumlah semua $\binom{n_i}{7}$ dimana $n_i$ adalah banyaknya tim yang dikalahkan oleh tim $i$, dengan jumlahnya meliputi semua $i$ di $V$. Karena setiap pasang tim bertengkar tepat satu kali, maka ada tepat $\binom{799}{2} = 318801$ pertandingan. Akibanya, jumlah semua kemenangan dari setiap tim akan bernilai tepat $318801$. Berdasarkan ketaksamaan Jensen, nilai dari jumlah dari semua $\binom{n_i}{7}$ pasti lebih besar dari $799 \times \binom{399}{7}$. 

Perhatikan juga bahwa banyaknya sub-himpunan 7 tim dari V adalah $\binom{799}{7}$. Berdasarkan prinsip sarang burung merpati, ada suatu sub-himpunan 7 tim yang menjadi bagian dari setidaknya $\lceil \frac{799 \times \binom{399}{7}}{\binom{799}{7}} \rceil = 7$ bintang. Akibatnya, 7 tim yang menjadi bagian dari sub-himpunan tersebut dikalahkan oleh 7 tim lain yang menjadi pusat dari 7 bintang yang bersangkutan. Ambil sub-himpunan tersebut menjadi B, dan 7 tim lain yang mengalahkan semua tim di B menjadi A. Kita dapatkan A dan B sesuai yang diinginkan.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


×