Prinsip Sarang Merpati: Menentukan Batas Minimum

Halo semuanya! Hari ini kita belajar Prinsip Sarang Merpati. Jika en item dimasukkan ke dalam ka sarang, dan en lebih dari ka, maka setidaknya ada satu sarang yang berisi lebih dari satu item.

Tipe satu: Menjamin kategori sama. Jika ada lima warna kaos kaki, berapa minimal yang diambil agar pasti ada sepasang warna sama? Gunakan rumus en sama dengan ka tambah satu. Kondisi terburuknya kita ambil satu dari tiap warna, maka kaos kaki keenam pasti sama dengan salah satu warna sebelumnya. Hasilnya, lima tambah satu sama dengan enam.

Sekarang tipe dua: Menjamin semua kategori. Sebuah kantong berisi sepuluh kelereng merah, tujuh kelereng biru, dan lima kelereng hijau. Berapa minimal yang diambil agar pasti ada minimal satu dari setiap warna?

Gunakan logika kasus terburuk. Pertama, ambil semua warna terbanyak yaitu sepuluh kelereng merah. Kedua, ambil semua warna terbanyak kedua yaitu tujuh kelereng biru. Ketiga, ambil satu dari warna tersisa yaitu hijau.

Totalnya adalah sepuluh tambah tujuh tambah satu, sama dengan delapan belas kelereng. Kita harus mengambil semua kelereng warna lain sebelum warna terakhir dijamin muncul.

Kesimpulannya, untuk menjamin dua item sama, en sama dengan ka tambah satu. Untuk menjamin ada item dari setiap jenis, en sama dengan jumlah item terbanyak ditambah satu. Semoga membantu!