Pigeonhole Principle

Pigeonhole Principle

Pigeonhole Principle:

             Jika k + 1 merpati dimasukkan ke dalam k rumah, maka ada satu rumah yang berisi paling tidak 2 merpati.

             Jika ada 9 kotak, dan  ada 10 merpati. Merpati yang ke-10 yang ditempatkan di rumah manapun menyebabkan rumah itu berisi minimal 2 merpati..
            Jumlah k+1 itu tidak wajib. Asalkan jumlah merpati lebih besar dari jumlah rumahnya, maka prinsip ini selalu berlaku.
            Pigeonhole principle sering disebut juga sebagai prm (prinsip rumah merpati) ataupun Dirichlet drawer principle. Nama Dirichlet muncul karena dipercaya pertama kali dinyatakan oleh matematikawan Jerman bernama Gustav Lejeune Dirichlet pada tahun 1834.

Selidikilah kebenaran kasus di bawah ini:

Kasus 1
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 2
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 3
            Jika dari barisan bilangan 1,2,3,4,5,...,400 diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling tidak ada dua bilangan yang koprima (faktor pembagi terbesarnya 1).
Jawab:
             Konon, Erdos pernah mengundang makan siang seorang anak ajaib, Lajos Posa. Di tengah makan siang Erdos bertanya ”Bagaimana kamu membuktikan bahwa jika kita mengambil n+1 bilangan dari himpunan bilangan 1, 2, 3, ..., 2n, maka ada dua bilangan yang koprima?”
            Sesaat pertanyaan tersebut tidak cukup jelas. Namun, argumentasi Lajos yang dikemukakan sesaat setelah pertanyaan selesai membuat pertanyaan Erdos lebih jelas: dalam n + 1 bilangan yang terpilih pasti ada dua bilangan yang berbeda satu alias saling berurutan dan dua bilangan tersebut koprima.

Kasus 4
            Jika dari barisan bilangan 1,2,3,4,5,...,400 diambil 201 bilangan, maka buktikanlah bahwa dari 201 bilangan tersebut paling tidak ada dua bilangan dimana bilangan yang satu yang membagi bilangan yang lain.
Jawab:
            Masalah di bawah ini mirip dengan masalah sebelumnya:
Dari himpunan bilangan bulat 1, 2, 3, ..., 2n, ambil n + 1 bilangan, sebutlah himpunan ini A. Maka selalu ada dua bilangan di A sehingga bilangan yang satu membagi bilangan yang lain. Masalah ini berhasil dibuktikan pula oleh Lajos.
            Kita dapat menulis kembali setiap anggota dalam himpunan A dalam bentuk: . Tentunya, karena yang diminta di soal adalah bilangan yang membagi bilangan lain, maka asumsikan bahwa anggota-anggota dalam himpunan A tidak boleh mengandung nilai m yang membagi satu sama lain. Dalam hal ini, m adalah bilangan ganjil yang mungkin dari 1,2,3,..., 2n. Artinya, m maksimal ada sebanyak n buah.

            Perhatikan bahwa karena kita mengambil n+1 bilangan, maka artinya pernyataan di atas adalah kontradiksi. Akibatnya, pasti akan ada 2 bilangan dengan nilai m yang sama. Artinya, kedua bilangan itu dapat membagi bilangan yang lain.