The Pigeonhole Principle (Prinsip Sarang Merpati)

The Pigeonhole Principle (Prinsip Sarang Merpati)

Pigeonhole Principle atau Prinsip Rumah Merpati pertama kali dinyatakan oleh ahli matematika dari Jerman yang bernama Johann Peter Gustav Lejeune Dirichlet pada tahun 1834, sehingga prinsip ini juga dikenal dengan istilah Prinsip Laci Dirichlet (Dirichlet drawer principle).                     

Jika (k + 1) atau lebih obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak yang memuat dua atau lebih obyek tersebut.

Missal Jika n merpati ditempatkan pada m rumah merpati, dimana n > m, maka terdapat rumah merpati yang memuat paling sedikit dua merpati. Untuk membuktikan pernyataan Prinsip Pigeonhole ini, kita gunakan kontradiksi. Misalkan kesimpulan dari pernyataan tersebut salah, sehingga setiap rumah merpati memuat paling banyak satu merpati. Karena ada m rumah merpati, maka paling banyak m merpati yang bisa dimuat. Padahal ada n merpati yang tersedia dan n > m, sehingga kita dapatkan sebuah kontradiksi.

Contoh:::

Contoh 1: Jika terdapat 11 pemain dalam sebuah tim sepakbola yang menang dengan angka 12-0, maka haruslah terdapat paling sedikit satu pemain dalam tim yang membuat gol paling sedikit dua kali.

Contoh 2: Jika anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat, maka haruslah terdapat paling sedikit satu hari ketika anda menghadiri paling sedikit dua kelas.

Contoh 3:

Kasus A:

Misalkan di rumahmu ada sebuah laci dan di dalam laci tersebut ada kaos kaki: 12 hitam dan 10 putih yang tersebar secara acak. Suatu hari, lampu di rumahmu mati, maka berapa kaos kaki MINIMAL yang harus kamu ambil agar dapat memperoleh sepasang kaos kaki dengan warna yang sama??

Jawab:cukup 3 kaos kaki.

Kasus B:

Selidikilah kebenaran kasus di bawah ini:

1. Di antara tiga orang, maka pasti ada dua orang yang berjenis kelamin sama.

2. Dari 32 orang, pasti ada 2 orang yang memiliki tanggal lahir yang sama.

3. Jika kn + 1 kelereng didistribusikan ke dalam n kotak, maka satu kotak akan berisi paling tidak k + 1 kelereng.

4. Sebuah garis l di dalam bidang melalui sisi-sisi segitiga ABC dengan tidak melewati titik sudutnya. Maka, garis itu tidak akan melewati ketiga sisi segitiga.

Jawab:

Semua BENAR.

Perhatikan bahwa nomor 3 merupakan bentuk prm yang lebih umum. (prm yang ditulis disini diperoleh untuk k = 1).

Kasus C:

Dapatkah kamu membuktikan bahwa ada paling tidak dua orang penduduk di Bandung yang banyaknya rambut di kepala sama?

Jawab:

Sekilas, mungkin kamu akan berusaha memanggil satu demi satu penduduk di Bandung.. Kemudian, menyuruh mereka mencabuti setiap rambut mereka untuk dihitung.. Wahahaha.. Benar-benar lucu. Namun, untuk membuktikannya, kamu tidak perlu melakukan hal bodoh seperti itu. Gunakan prinsip rumah merpati di atas.

Perkirakan kemungkinan terburuk bahwa jumlah rambut terlebat adalah 1000 helai rambut per inchi persegi. Kemudian asumsikan kemungkinan terburuk bahwa rambut itu menutupi luas 1000 inchi persegi, maka jumlah helai rambut terlebat manusia ada sekitar 1000.000 helai.. (Ini sudah terburuk sekali)..

Membandingkannya dengan jumlah penduduk Bandung, yaitu sekitar 2.500.000 juta jiwa (tahun 2005, dan pasti akan terus bertambah), maka jumlah 1000.000 sekitar 2.5 kali lebih kceil dibandingkan jumlah penduduknya. Di kasus ini, kita dapat menganalogikan 2.500.000 sebagai jumlah merpati, dan 1000.000 sebagai jumlah rumah yang ada. Maka, akan ada paling tidak 2 orang yang memiliki jumlah rambut yang sama.

Kasus D:

Seperti kasus nomor A. Sekarang, di laci ada 12 kaos kaki hitam, 13 kaos kaki putih, 20 kaos kaki biru, 5 kaos kaki merah, 1 kaos kaki hijau, dan 1 kaos kaki kuning. Berapa banyak kaos kaki minimal yang harus diambil agar setidaknya:

a) terdapat 2 kaos kaki yang memiliki warna yang sama

b) terdapat 2 kaos kaki yang memiliki warna yang berbeda.

Jawaban Kasus D:

a)Kemungkinan terburuk yaitu saat mengambil 6 kaos kaki yang semuanya berbeda warna (hitam, putih, biru, merah, hijau, dan kuning). Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna sama adalah 7 buah.

b) Kemungkinan terburuk yaitu saat mengambil 20 kaos kaki yang semuanya berwarna biru. Oleh karena itu, kaos kaki minimal yang harus diambil agar setidaknya terdapat 2 kaos kaki dengan warna berbeda adalah 21 buah.