Pembahasan Olimpiade Matematika #6

6. Ada 21 orang yang berhubungan secara rahasia dengan menggunakan frekuensi gelombang radio yang berbeda. Ada pasangan dua orang yang dapat berhubungan, dan boleh ada yang tidak dapat berhubungan. Setiap pasangan berhubungan hanya dengan satu frekuensi tertentu dan tidak bisa digunakan pasangan lain. Dari setiap tiga orang, selalu ada dua orang yang tidak dapat berhubungan. Tentukan banyaknya frekuensi maksimum.

Solusi:

Misalkan 21 orang itu adalah 21 titik pada bidang. Jika dua orang berhubungan, maka dua titiknya diberi garis. Misalkan kita beri warna tiga titik A merah, B biru, C merah, AB berhubungan dan BC juga berhubungan. Maka C dan A tidak boleh berhubungan. Maka kita bisa mewarnai semua titik dengan merah dan biru sehingga dua titik berhubungan jika dan hanya jika warnanya berbeda. Jika banyaknya warna merah adalah , banyaknya garis adalah . Jelas bahwa nilai maksimum dicapai ketika atau , yaitu 110.

Related Article to Pembahasan Olimpiade Matematika #6:

Enter your email address below to receive updates each time we publish new content :

  

Privacy guaranteed. We'll never share your info.