Pigeonhole Principle

Bermula dari ide sederhana berikut

Jika ada 3 ekor merpati ditaruh kedalam 2 buah kandang merpati, maka dapat dipastikan pada salah satu dari kandang merpati tersebut terdapat sekurang-kurangnya 2 ekor merpati.

didapatkan sebuah generalisasi yang dinamakan Pigeonhole Principle (yang selanjutnya disingkat PP) sebagai berikut:

Misalkan terdapat 2 buah bilangan bulat positif \(n\) dan \(k\). Jika ada \(kn+1\) objek yang didistribusikan ke \(n\) kotak, maka terdapat kotak yang memiliki sekurang-kurangnya \(k+1\) objek.

Pembuktian dari PP ini adalah sebagai berikut. Jika tidak ada 1 pun kotak yang memiliki \(k+1\) objek, maka setiap kotak memiliki paling banyak \(k\) objek, sehingga total banyak objek yang ditaruh kedalam \(n\) kotak, berjumlah \(kn\), sehingga terjadi kontradiksi.

Yang paling penting dalam menggunakan PP ini adalah representasi objek dan kotak yang benar.

Contoh 1
Dalam suatu pesta terdapat 7 orang, maka sekurang-kurangnya terdapat 4 orang yang memiliki jenis kelamin yang sama.

Bukti

Objek adalah orang berjumlah 7 (\(3\times 2+1=kn+1\)), sedangkan kotak (\(n\)) adalah jenis kelamin berjumlah 2 (pria dan wanita), sehingga dengan menggunakan PP, terdapat sebuah kotak yang berisi sekurang-kurangnya (\(k+1=3+1=\))4 objek (pada soal ini menjadi, terdapat sekurang-kurangnya 4 orang diantara peserta pesta yang memiliki jenis kelamin yang sama).

Contoh 2
Terdapat sebuah bujur sangkar yang sisi-sisinya memiliki panjang 3 unit. Maka apabila kita memilih 10 titik didalam bujur sangkar tersebut secara sembarang, maka setidaknya ada 2 buah titik yang berjarak paling besar \(\sqrt{2}\).

Bukti

Mari kita bagi bujur sangkar menjadi 9 bujur sangkar kecil yang sisi-sisinya memiliki panjang 1 unit, seperti gambar berikut:
Kotak

Jarak antara 2 buah titik dalam sebuah kotak kecil paling besar \(\sqrt{2}\).
Karena jumlah bujur sangkar kecil hanya 9, sedangkan titik yang dipilih ada 10, maka setidaknya ada sebuah bujur sangkar kecil yang memiliki sekurang-kurangnya 2 buah titik didalamnya, sehingga kedua buah titik tersebut akan memiliki jarak paling besar \(\sqrt{2}\).

Contoh 3
Dalam sebuah turnamen terdapat 10 peserta, turnamen ini menggunakan sistem round-robin (ie: setiap peserta akan bertanding 1 kali dengan peserta lainnya). turnamen memiliki sistem skor sebagai berikut:

+1 point jika menang
0 point jika seri
-1 point jika kalah

Ketika turnamen berakhir, ternyata lebih dari 70% permainan seri. Tunjukkan bahwa terdapat 2 peserta yang memiliki skor total yang sama.

Bukti

Karena menggunakan sistem round-robin, maka jumlah pertandingan pada turnamen tersebut sebanyak \({10\choose{2}}=45\) kali. Dengan fakta bahwa 70% dari total pertandingan berakhir dengan seri, maka jumlah pertandingan yang tidak seri sebanyak \(\lfloor{45\times{30\%}}\rfloor=13\) pertandingan. Dengan mengumpamakan bahwa kesepuluh peserta memiliki total skor akhir yang berbeda, maka paling banyak hanya ada 1 peserta yang memiliki total skor akhir 0, dan sekurang-kurangnya terdapat 9 peserta yang memiliki skor total ntah positif atau negatif. Dengan menggunakan PP, sekurang-kurangnya terdapat 5 peserta yang memiliki nilai positif (atau negatif). agar ke-5 peserta tersebut memiliki nilai yang berbeda, maka minimal pertandingan yang harus dilakukan sebanyak \(1+2+3+4+5=15\), yang berarti terjadi kontradiksi. Oleh karena itu terdapat 2 peserta yang memiliki skor total sama.

KoleksiPanda

Post a Comment

Search

RSS Feeds

Meta

KoleksiPanda