Prinsip Sangkar Burung

Hayoo Siapa yang suka PHP disini? Yuk kita belajar tentang PHP. Apa itu?
PHP yaitu PigeonHole Principle atau dikenal sebagai prinsip sangkar burung. Hmm apa lagi tu...

Dalam matematika prinsip sangkar burung atau Pigeonhole Principle menyatakan kalau ada $x$ buah burung atau lebih ditempatkan ke $x-1$ buah sangkar burung, maka pasti ada sangkar burung yang berisi lebih dari $1$ burung. Materi ini merupakan materi kombinatorika.
Untuk lebih memahami nya perhatikan gambar berikut

Pada gambar diatas ada satu burung yang tidak menempati kotak. Karenanya maka mau tidak mau harus ada yang berisi setidaknya $2$ dalam satu kotak.

Oke, Apakah sampai sekarang sudah paham? atau masih belum jelas?
Baik, kurasa kalian sudah memahaminya, karena itu logika yang sangat sederhana. Sebagai contoh dalam $13$ orang manusia pasti ada dari mereka yang lahir di bulan yang sama.
Teorema Pigeon Hole Principle (PHP)
1. Jika $x$ objek didistribusikan ke $y$ buah tempat, dan jika $x>y$ maka ada tempat yang terisi oleh lebih dari $1$ objek.
2. Untuk sebarang bilangan bulat positif $k$ dan $y$, jika $ky+1$ atau lebih objek didistribusikan ke $y$ buah tempat maka setidaknya ada satu tempat yang berisi lebih dari $k$ objek.
3. Jika rata-rata $n$ bilangan positif adalah $x$, maka setidaknya salah satu angka lebih besar atau sama dengan $x$. Lebih lanjut, setidaknya salah satu angka kurang dari atau sama dengan $x$.
4. Misalkan $q_1, q_2, ..., q_n$ merupakan bilangan bulat positif. Jika $\left(\displaystyle \sum_{i = 1} ^ n q_i -n + 1 \right)$ objek dimasukkan ke dalam $n$ kotak, maka baik itu kotak pertama berisi setidaknya $q_1$ objek, atau kotak kedua berisi setidaknya $q_2$ objek, ..., atau kotak ke $n$ berisi setidaknya $q_n$  benda.

Contoh soal

• Buktikan bahwa dari setiap himpunan $1000$ bilangan bulat terdapat salah satu bilangan yang habis dibagi $1000$ atau beberapa bilangan yang jumlahnya habis dibagi $1000$

Jawab : Kita tulis $1000$ bilangan tersebut sebagai $\{x_1,x_2,x_3,\cdots ,x_{1000}\}$.
Misal $1000$ himpunan bagian dari himpunan tersebut adalah $\{x_1,\{x_1,x_2\},\cdots ,\{x_1,\cdots ,x_{1000}\}\}$
dan untuk masing-masing himpunan bagian ini, hitung jumlahnya. Jika tidak ada jumlah ini yang dapat dibagi dengan $1000$, maka ada $1000$ jumlah dan $999$ kelas residu mod $1000$ (tidak termasuk $0$). Karenanya dua dari jumlah ini ada yang memiliki sisa yang sama jika dibagi $1000$, katakanlah $x_1 + \cdots + x_i \equiv x_1 + \cdots + x_j \pmod {1000}$ (dengan $i<j$). Kemudian $x_ {i + 1} + \cdots + x_j \equiv 0 \pmod {1000}$, dan subset $\{x_ {i + 1}, \cdots, x_j \}$ sudah memenuhi.

• Tunjukkan bahwa dari $13$ siswa di kelas terdapat setidaknya $2$ siswa yang mempunyai bulan kelahiran yang sama

Jawab : Kita tahu bahwa banyaknya bulan dalam setahun itu ada $12$. Karena terdapat $13$ siswa, maka menurut Pigeon Hole Principle pasti ada setidaknya $2$ siswa yang mempunyai bulan kelahiran yang sama.

• Terdapat $8$ orang siswa akan menyelesaikan $8$ buah soal. Tiap soal dapat dijawab oleh paling sedikit $5$ siswa. Buktikan bahwa kita dapat mengambil $2$ orang siswa diantara $8$ orang siswa itu sehingga $8$ buah soal yang ada dapat diselesaikan oleh paling sedikit $1$ orang siswa diantara $2$ orang siswa yang diambil.

Jawab : Total ada minimal $40$ soal yang berhasil dijawab (tidak harus beda). Ambil siswa dengan jumlah soal terjawab tertinggi misalkan $X$.
  -) Jika dia bisa $8$, kita selesai.
  -) Jika dia bisa $7$, misal soal no $1-7$, tapi soal no $8$ pasti ada yang bisa menyelesaikan, misal $Y$, pilih $X$ dan $Y$
  -) Jika dia bisa $6$, misal soal no $1-6$, lalu soal no $7-8$ kan dijawab minimal masing masing $5$ siswa, padahal tersisa $7$ siswa jadi menurut Pigeon Hole Principle pasti ada setidaknya $3$ orang yang bisa menjawab soal no $7$ dan $8$. Misal salah satu darinya $Z$, berarti pilih $X$ dan $Z$.
  -) Jika dia bisa $5$, karena jumlah soal minimal yang berhasil dijawab $40$ dan yang lain harus menjawab $\leq 5$ soal (karena definisi tadi $X$ merupakan siswa dengan jumlah soal terjawab tertinggi). Berarti total soal yang bisa dijawab $\leq 40$. Kesamaan terjadi, artinya masing masing siswa yang lain juga bisa mengerjakan $5$ soal juga. Misalkan $X$ bisa soal no $1-5$. Andaikan ada dari $7$ siswa selain $X$ tersebut bisa mengerjakan soal no $6-8$ sekaligus, berarti kita selesai. Jika tidak, berarti kemungkinan kombinasi soal yang diselesaikan oleh $7$ siswa tersebut adalah $5$ soal no $1-5$, $4$ soal no $1-5$ dan $1$ soal no $6-8$,  $3$ soal no $1-5$ dan $2$ soal no $6-8$. Jadi maksimal ada $2\times 7=14$ soal pada no $6-8$ yang diselesaikan oleh kedelapan orang tersebut. Padahal banyak soalnya ada $3$ dimana setiap soal minimal ada $5$ siswa yang bisa menjawab. Jadi harusnya ada $15$ soal pada no $6-8$ yang harus diselesaikan oleh ke $8$ siswa tersebut. Hal ini kontradiksi.
Jadi, Terbukti bahwa kita dapat mengambil $2$ orang siswa diantara $8$ orang siswa itu sehingga $8$ buah soal yang ada dapat diselesaikan oleh paling sedikit $1$ orang siswa diantara $2$ orang siswa yang diambil.