Prinsip Sangkar Burung (Pigeonhole Principle)

Prinsip sangkar burung (pigeonhole principle) menyatakan bahwa jika n burung terbang menuju m sangkar dan n > m, maka paling sedikit ada satu sangkar yang memuat dua atau lebih burung. Prinsip ini dapat diilustrasikan oleh gambar di bawah ini untuk n = 5 dan m = 4.

Ilustrasi (a) menunjukkan beberapa burung yang hinggap di sangkarnya, sedangkan ilustrasi (b) menunjukkan korespondensi antara burung dengan sangkarnya. Prinsip sangkar burung kadang-kadang disebut sebagai prinsip kotak Dirichlet (Dirichlet box principle) karena prinsip tersebut dinyatakan secara formal untuk pertama kalinya oleh J. P. G. L. Dirichlet (1805 – 1859).

Dari gambar (b) di atas, kita dapat menyatakan prinsip sangkar burung dengan bahasa yang lebih matematis, seperti berikut.

Prinsip Sangkar Burung (Pigeonhole Principle)
Suatu fungsi dari himpunan hingga ke himpunan hingga yang lebih kecil, tidak dapat satu-satu: Paling sedikit ada dua anggota domain yang memiliki bayangan yang sama di kodomain.

Sehingga, diagram panah yang menggambarkan fungsi dari himpunan hingga ke himpunan hingga yang lebih kecil harus memiliki paling sedikit dua anak panah dari domain yang menunjuk anggota yang sama di kodomain. Pada ilustrasi di atas, kita dapat melihat bahwa anak panah dari burung 4 dan 5 menunjuk sangkar burung 4.

Karena kebenaran dari prinsip sangkar burung sangat mudah diterima dengan menggunakan intuisi dasar, kita langsung saja berpindah ke penggunaan dari prinsip ini. Penerapan dari prinsip ini muncul mulai dari pemecahan masalah yang jelas sampai masalah yang lebih rumit. Berikut ini beberapa contoh penggunaan prinsip sangkar burung.

Contoh 1: Penggunaan Prinsip Sangkar Burung

Dari seluruh penduduk DKI Jakarta tahun 2013, apakah paling sedikit ada dua orang yang memiliki jumlah rambut yang sama di kepala mereka?

Pembahasan Jawabannya adalah iya. Pada contoh ini, yang menjadi burung adalah penduduk DKI Jakarta dan yang menjadi sangkar burung adalah semua kemungkinan dari jumlah rambut pada setiap kepala penduduk Jakarta. Misalkan populasi dari penduduk DKI Jakarta adalah P. Berdasarkan data dari Bappeda Jakarta tahun 2013, jumlah penduduk Jakarta adalah sekitar 9 juta jiwa. Selain itu, seperti kita ketahui jumlah rambut yang dapat tumbuh di kepala manusia paling banyak adalah 300.000. Didefinisikan suatu fungsi H dari himpunan semua penduduk DKI Jakarta {x₁, x₂, x₃, …, x_p} ke himpunan {0, 1, 2, 3, …, 300.000}, seperti berikut.

Karena jumlah penduduk DKI Jakarta lebih banyak daripada kemungkinan jumlah rambut pada kepala manusia, maka H bukan merupakan fungsi satu-satu. Sehingga, paling sedikit ada dua anak panah yang menunjuk pada bilangan yang sama. Atau dengan kata lain, paling sedikit ada dua penduduk DKI Jakarta yang memiliki jumlah rambut yang sama.

Contoh 2: Memilih Sepasang Bilangan Bulat dengan Jumlah Tertentu

Misalkan A = {1, 2, 3, 4, 5, 6, 7, 8}. Jika lima bilangan bulat diambil dari A, apakah paling sedikit ada sepasang bilangan bulat yang jumlahnya 9?

Pembahasan Jawabannya adalah iya. Kita partisi himpunan A menjadi 4 himpunan yang saling lepas, yaitu {1, 8}, {2, 7}, {3, 6}, dan {4, 5}. Perhatikan bahwa setiap bilangan bulat di A muncul tepat satu kali di empat himpunan bagian tersebut dan jumlah bilangan bulat pada masing-masing himpunan bagian tersebut adalah 9. Sehingga, jika 5 bilangan bulat diambil dari himpunan A maka, dengan menggunakan prinsip sangkar burung, dua diantaranya berasal dari himpunan bagian yang sama. Hal tersebut akan menyebabkan jumlah dua bilangan bulat tersebut adalah 9.

Untuk melihat dengan cermat bagaimana penerapan prinsip sangkar burung pada soal ini, kita misalkan lima bilangan bulat yang diambil (sebut saja a₁, a₂, a₃, a₄, dan a₅) sebagai burung dan himpunan-himpunan bagian sebagai sangkarnya. Fungsi P dari himpunan burung ke himpunan sangkar burung didefinisikan dengan memisalkan P(a_i) adalah himpunan bagian yang memuat a_i.

Fungsi P terdefinisi dengan baik karena setiap bilangan bulat a_i di domain, a_i termuat oleh satu himpunan bagian (karena gabungan himpunan-himpunan bagian tersebut adalah A) dan a_i tidak termuat oleh lebih dari satu himpunan bagian A (karena himpunan-himpunan bagian tersebut saling lepas).

Karena jumlah burung lebih banyak daripada sangkarnya, maka paling sedikit ada dua burung yang singgah di satu sangkar. Sehingga dua bilangan bulat yang berbeda akan dipasangkan kepada himpunan bagian yang sama. Hal ini akan menyebabkan bahwa dua bilangan bulat tersebut adalah dua anggota yang berbeda dari himpunan bagian, sehingga jumlahnya adalah 9. Secara lebih formal, dengan menggunakan prinsip sangkar burung, karena P bukan fungsi satu-satu, maka ada bilangan bulat a_i dan a_j sedemikian sehingga,

Tetapi kemudian, berdasarkan definisi P, a_i dan a_j dimiliki oleh himpunan bagian yang sama. Karena jumlah semua anggota dari masing-masing himpunan bagian adalah 9, maka a_i + a_j = 9. Semoga bermanfaat, yos3prens.