Sumber: Ujian kombinatorik 3
Buktikan bahwa bilangan \({\underbrace{99\ldots9}_{2005}}^{2009}\) bisa diperoleh dengan cara menghapus beberapa digit pada bilangan \({\underbrace{99\ldots9}_{2008}}^{2009}\)
Read More
Prob 2
Tuesday, 5 January 2010 – 12:50 pm
Prob 1
Tuesday, 5 January 2010 – 11:54 am
Sumber: Ujian kombinatorik 1
Misalkan setiap titik pada bidang diberi warna merah, hijau, dan biru. Buktikan bahwa terdapat suatu persegi panjang sedemikian sehingga setiap titik sudutnya mempunyai warna yang sama.
Read More
Pigeonhole Principle
Tuesday, 17 November 2009 – 7:25 pm
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.
