Beranda > kombinatorik > Prinsip rumah burung

Prinsip rumah burung

 

Jika ada 6 burung yang ditempatkan dalam 5 rumah, maka salah satu rumah pasti ditempati oleh lebih dari satu burung. Ini adalah prinsip sederhana yang disebut prinsip rumah burung. Dengan prinsip ini kita dapat menyimpulkan hal berikut ini

 

Dalam satu kelas yang terdiri dari 32 murid, maka ada murid yang ulang tahun dengan tanggal yang sama.

 

Diantara 13 murid, selalu ada dua murid yang mempunyai bulan lahir yang sama

 

Di Surabaya ada sedikitnya dua orang yang mempunyai tinggi badan yang sama (dalam satuan centimeter)

 

Di Maluku ada sedikitnya dua orang yang mempunyai berat badan yang sama (dalam satuan kilogram)

 

 

Prinsip ini secara umum dapat dinyatakan sebagai berikut

 

“jika ada barang dengan jumlaj lebih dari n dan ditempatkan pada n kotak, maka ada satu kotak atau lebih yang berisi lebih dari satu benda”.

 

Contoh :

Dari bilangan bulat 1, 2, 3, 4, 5, …, 200.

Kita pilih 101 bilangan. Perlihatkan bahwa dari 101 bilangan yang kita pilih ada dua bilangan yang satu habis dibagi dengan yang lainnya?

 

Jawaban :

Kita tuliskan bilangan bulat 1, 2, 3, 4, 5, …, 200 dalam bentuk 2^k.a

Dengan a bilangan bulat ganjil dan k lebih besar atau sama dengan nol terbesar dari yang mungkin.

 

Contohnya :

50 = 2.25

36 = 2^2.9

 

Perhatikan bahwa dari 1, 2, 3, 4, 5, …, 200.  Maka nilai a yang mungkin adalah bilangan-bilangan ganjil di 1, 2, 3, 4, 5, …, 200. yaitu 1, 3, 5, …,199 sebanyak 100 bilangan.

 

Sekarang kita telah memilih 101 bilangan. Maka pasti akan ada dua bilangan yang mempunyai a yang sama.

Ingat kembali prinsip rumah burung. Misalkan bilangan tersebut adalah 2^p.a dan 2^q.a, dengan p < q. Ini mengakibatkan bilangan kedua habis dibagi oleh bilangan pertama.

 

Kita telah memperlihatkan bahwa dari 101 bilangan yang kita pilih ada dua bilangan yang satu habis dibagi dengan yang lainnya.

Prinsip rumah burung ini sering digunakan di dalam soal-soal olimpiade. Untuk lebih mudah memahaminya, perhatikan kalimat berikut ini.

 

“jika diketahui tersedia rumah burung sebanyak n dan ada n + 1 burung, maka salah satu dari rumah tersebut terdiri lebih dari satu burung”

 

Contoh :

Seorang tukang listrik harus mengambil sekering listrik yang terdiri dari sekering 15A dan 20A tanpa dapat memilih. Dalam satu kali ambil, ia menginginkan ada dua sekering yang mempunyai ukuran yang sama besar. Tentukan jumlah yang harus diambil seorang tukang listrik tersebut?

 

Jawab :

Misalnya pak tukang tersebut mengambil hanya dua biji sekering, maka kemungkinan-kemungkinannya adalah

Dua biji 15A dan tidak ada 20A

Dua biji 20A dan tidak ada 15A

1 biji 15A dan 1 biji 20A.

Padahal yang diinginkan pak tukang adalah dua biji dengan ukuran yang sama. Ketika mengambil dua, maka masih ada kemungkinan bahwa yang diambil itu adalah 1 berukuran 15A dan yang satu lagi berukuran 20A.

Sehingga pak tukang sedikitnya harus mengambil 3 buah sekering.

 

Kemungkinan-kemungkinannya yaitu

 

2 biji berukuran 15A dan 1 biji berukuran 20A

1 biji berukuran 15A dan 2 biji berukuran 20A

3 biji berukuran 15A

3 biji berukuran 20A

 

Tulisan terbaru :

 

Kategori:kombinatorik
  1. Belum ada komentar.
  1. No trackbacks yet.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

%d blogger menyukai ini: