Pigeon Hole Principle (Prinsip Lubang Merpati)

Selasa, 17 Desember 2019

Pigen Hole Principle (Prinsip Lubang Merpati) mengatakan bahwa jika lebih dari n benda dimasukkan ke dalam n kotak, maka sedikitnya ada satu kotak yang berisi lebih dari satu benda. Secara umum bahwa jika ada lebih dari pn benda dimasukkan ke dalam n kotak maka sedikitnya ada satu kotak berisi lebih dari p benda.

Bentuk Lain : Jika n bilangan bulat m₁, m₂, m₃, ···, m_n memiliki rata-rata

, maka sedikitnya satu di antara bilangan-bilangan bulat tersebut lebih besar atau sama dengan r.

Contoh:

Jika ada 101 surat yang akan dimasukkan ke dalam 50 kotak pos, buktikan bahwa ada sedikitnya satu kotak pos berisi sekurang-kurangnya 3 surat.

Solusi :

Jika seluruh kotak pos maksimal hanya berisi 2 surat, maka jumlah maksimal surat yang dapat masuk kotak pos adalah 100. Tetapi jumlah surat yang ada yaitu 101. Maka dapat dipastikan ada sedikitnya satu kotak pos berisi sekurang-kurangnya 3 surat.

Contoh :

Pada sebuah pesta setiap orang yang hadir diharuskan membawa permen. Jika pada pesta tersebut jumlah orang yang hadir ada 10 sedangkan jumlah permen yang ada sebanyak 50 buah, buktikan bahwa ada sekurang-kurangnya 2 orang yang membawa permen dalam jumlah yang sama.

Solusi :

Andaikan bahwa seluruh orang membawa permen dalam jumlah yang berbeda maka sedikitnya jumlah permen yang ada sebanyak 1 + 2 + 3 + ··· + 10 = 55 > 50 (tidak memenuhi). Kontradiksi.

Maka dapat dibuktikan bahwa ada sekurang-kurangnya 2 orang yang membawa permen dalam jumlah yang sama.

Contoh :

Jika terdapat n² + 1 titik yang terletak di dalam sebuah persegi dengan panjang sisi n, buktikan bahwa ada sekurang-kurangnya √2 titik yang memiliki jarak tidak lebih dari 2 satuan.

Solusi :

Persegi dengan ukuran n x n dapat dibagi menjadi n 2 buah persegi berukuran 1 x 1.

Pada persegi dengan ukuran 1 x 1, jarak terjauh 2 titik adalah jika keduanya terletak pada titik sudut berlawanan yaitu sejauh √2 satuan.

Karena ada n² + 1 titik dengan ada n 2 persegi maka sesuai Pigeon Hole Principle, akan terdapat sedikitnya 2 titik yang terletak pada satu persegi dengan ukuran 1 x 1 yang sama.

Maka dapat dibuktikan ada sekurang-kurangnya 2 titik yang memiliki jarak tidak lebih dari √2 satuan.

Karena ada n² + 1 titik dengan ada n² segitiga sama sisi dengan panjang sisi 1 satuan maka sesuai Pigeon Hole Principle akan terdapat sedikitnya 2 titik yang terletak pada satu segitiga dengan panjang sisi 1 satuan yang sama.

Maka dapat dibuktikan bahwa ada sedikitnya 2 titik yang jaraknya satu sama lain paling jauh 1.

Contoh :

Buktikan bahwa di antara 7 bilangan bulat, pasti ada sekurang-kurangnya sepasang bilangan yang selisihnya habis dibagi 6.

Solusi :

Kemungkian sisa jika suatu bilangan bulat dibagi 6 adalah 0, 1, 2, 3, 4, atau 5. Karena ada 6 kemungkinan dan ada 7 bilangan bulat maka sesuai Pigeon Hole Principle, sedikitnya dua bilangan akan memiliki sisa yang sama jika dibagi 6. Misalkan bilangan itu adalah n₁ dan n₂ dengan sisa jika dibagi 6 adalah r. Maka kita dapat membuat n₁ = 6k₁ + r dan n₂ = 6k₂ + r dengan k₁ dan k₂ bilangan bulat.

n₁ – n₂ = 6(k₁ + k₂) yang merupakan bilangan yang habis dibagi 6 (terbukti).

Sifat penjumlahan berikut juga akan membantu menjelaskan :

Bilangan Genap - Bilangan Genap = Bilangan Genap

Bilangan Ganjil - Bilangan Ganjil = Bilangan Genap.

Kemungkinan jenis koordinat (dalam bahasa lain disebut paritas) suatu titik letis hanya ada 4 kemungkinan yaitu (genap, genap), (genap,ganjil), (ganjil, ganjil) dan (ganjil, genap).

Jika 2 titik letis mempunyai paritas yang sama maka sesuai sifat penjumlahan maka dapat dipastikan kedua titik letis memiliki jarak mendatar dan jarak vertikal merupakan bilangan genap yang berarti koordinat titik tengah dari garis yang menghubungkan kedua titik letis tersebut juga merupakan bilangan genap.

Karena ada 5 titik letis sedangkan hanya ada 4 paritas titik letis maka sesuai Pigeon Hole Principle (PHP) maka dapat dipastikan sekurang-kurangnya ada dua titik letis yang memiliki paritas yang sama.

Dari penjelasan di atas dapat dibuktikan bahwa jika P₁, P₂, P₃, P₄, P adalah lima titik letis berbeda pada bidang maka terdapat sepasang titik (P_i, P_j), i ≠ j, demikian, sehingga ruas garis P_i P_j  memuat sebuah titik letis selain P_i dan P_j.

Sumber

Labels: Serba-serbi

Thanks for reading Pigeon Hole Principle (Prinsip Lubang Merpati). Please share...!