Pigeonhole Principle

 Teoremanya kurang lebih seperti berikut:

“Ada m burung merpati, yang akan ditempatkan ke sarang-sarang mereka yang jumlahnya n, jika m > n, maka paling tidak ada 1 sarang merpati yang isinya 2 atau lebih merpati.”

Ada beberapa soal nih tentang Pigeonhole Principle 😀

1. Ada suatu geng wanita yang berjumlah 12 orang. Geng tersebut ingin pergi ke pesta dansa bersama suatu geng pria, yang berisi 13 orang. Jika satu wanita harus berpasangan dengan tepat satu pria, buktikan akan ada pria yang tidak memiliki pasangan (jomblo).

2. Selesai meeting di suatu ruangan, ada n orang yang saling berjabat tangan, buktikan ada paling tidak 2 orang yang jumlah jabat tangannya sama.

3. (Dari Pak Arzaki) Buktikan bahwa dari 6 bilangan bulat yang diambil secara acak, paling tidak kita akan selalu menemukan 2 bilangan yang jumlah atau selisihnya habis dibagi 8.

4. (Generalisasi Soal 3) Untuk seluruh bilangan asli n, buktikan bahwa jika kita mengambil n + 2 bilangan bulat secara acak, akan selalu ada paling tidak dua bilangan yang jumlah atau selisihnya habis dibagi 2n.

5. Misalkan barisan bilangan  dan adalah permutasi dari bilangan natural 1 sampai 100, buktikan diantara perkalian akan ada paling tidak 2 bilangan yang mempunyai sisa sama jika dibagi dengan 100.

6. (IMO 1972) Dari 10 bilangan bulat diantara 10 sampai dengan 99 (inclusive) dapat dicari 2 subset yang disjoint sedemikian sehingga jumlah elemen-elemen dari kedua subset tersebut sama.

7. Buktikan bahwa dari 7 bilangan real, akan ada 2 bilangan x dan y sedemikian sehingga:

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s