Sebagian pernyataan pencacahan tidak perlu tahu susunannya, hanya perlu tahu bahwa sesuatu pasti terjadi. Prinsip sarang merpati dan aturan inklusi-eksklusi adalah dua alat untuk sampai ke kesimpulan semacam itu.
Lihat dulu
LIHAT DULU
Lebih banyak merpati daripada kotak
Prinsip sarang merpati membuktikan sesuatu pasti terjadi tanpa perlu menunjukkan yang mana. Cukup bandingkan banyaknya objek dengan kotaknya.
5/5
Prinsipnya menjamin keberadaan, bukan menunjukkan yang mana, dan ia tidak memerlukan pengetahuan apa pun tentang isi kotaknya.
Konsep
Prinsip sarang merpati
Kalau ada lebih banyak objek daripada kotak, maka setidaknya satu kotak berisi lebih dari satu objek. Buktinya hanya beberapa baris: sebar objeknya semerata mungkin, satu per kotak, lalu objek terakhir tetap tidak menemukan kotak kosong. Kesimpulannya pasti benar walaupun tidak satu pun kotak bisa ditunjuk lebih dulu.
Bentuk umumnya
Kalau n objek masuk ke k kotak, maka ada kotak yang berisi paling sedikit pembulatan ke atas dari n dibagi k. Untuk 13 orang dan 12 bulan, hasilnya 2, jadi ada dua orang yang lahir di bulan yang sama. Yang perlu diperhatikan, prinsip ini hanya menjamin keberadaannya, bukan menunjukkan siapa atau kotak mana.
Inklusi-eksklusi
Untuk menghitung gabungan, jumlahkan dulu semuanya, lalu kurangi yang terhitung dua kali, lalu tambahkan kembali yang terhitung tiga kali. Aturan ini bekerja untuk dua himpunan maupun tiga, dan sering dipakai bersama sarang merpati untuk memastikan sesuatu pasti terulang.
Rumus yang dipakai
Sarang merpati
n + 1 objek, n kotak → ada kotak berisi paling sedikit 2
Kotaknya lebih sedikit daripada objeknya.
Bentuk umum
n objek, k kotak → ada kotak berisi paling sedikit ⌈n / k⌉
Pembulatan ke atas, karena sisanya tetap harus ditaruh.
Kurangi yang berpasangan, lalu tambahkan kembali yang bertiga.
Contoh pengerjaan
Dua siswa yang lahir di bulan yang sama
Di sebuah kelas ada 13 siswa. Tunjukkan bahwa pasti ada dua siswa yang lahir pada bulan yang sama.
Ada 13 siswa, tetapi hanya 12 bulan dalam setahun, jadi objeknya lebih banyak daripada kotaknya.
Andaikan setiap bulan ditempati paling banyak satu siswa.
Maka paling banyak hanya 12 siswa yang bisa ditempatkan, kurang satu dari 13.
Pengandaian itu terbantah, jadi ada bulan yang ditempati paling sedikit dua siswa.
Bentuk umumnya ⌈13 / 12⌉ = 2, dan kesimpulan ini berlaku tanpa mengetahui satu pun tanggal lahirnya.
JawabanAda bulan yang ditempati paling sedikit dua siswa
Poin penting
Objek yang lebih banyak daripada kotak memaksa ada kotak yang berisi lebih dari satu.
Bentuk umumnya memakai pembulatan ke atas dari n dibagi k.
Prinsip sarang merpati menjamin keberadaan, bukan menunjukkan yang mana.
Inklusi-eksklusi menghitung gabungan dengan mengurangi yang terhitung berulang.
Latihan singkat
MudahSoal 1 dari 3
Ada 7 kaus kaki di dalam lemari dan hanya 3 warna yang mungkin. Apa yang pasti benar?
Bagi banyaknya kaus kaki dengan banyaknya warna, lalu bulatkan ke atas.
PembahasanTujuh kaus kaki dibagi ke tiga warna memberi ⌈7 / 3⌉ = 3, jadi ada warna yang muncul paling sedikit tiga kali. Warna lain bisa saja tidak muncul sama sekali, sehingga pilihan kedua dan ketiga tidak dijamin.
SedangSoal 2 dari 3
Manakah kesimpulan yang benar menurut prinsip sarang merpati?
Prinsipnya hanya berlaku kalau objeknya lebih banyak daripada kotaknya.
PembahasanTiga kesimpulan pertama yang benar semuanya berasal dari objek yang lebih banyak daripada kotaknya. Yang ketiga salah justru karena arahnya terbalik: 4 bola ke dalam 5 kotak masih bisa disebar satu per satu tanpa ada yang berbagi.
SulitSoal 3 dari 3
Di sebuah sekolah ada 400 siswa. Berapa jumlah siswa paling sedikit yang lahir pada bulan yang sama?
Selalu bulatkan ke atas, karena sisanya tetap harus ditaruh di suatu bulan.
PembahasanAda 400 siswa dan 12 bulan, sehingga 400 ÷ 12 = 33,33. Pembulatan ke atasnya 34, jadi ada bulan yang ditempati paling sedikit 34 siswa. Membulatkan ke bawah akan memberi 33, dan itu belum menjamin apa pun.