Prinsip Sangkar Burung: Sebuah Bilangan Membagi Bilangan Yang Lain

Problem

Dari 400 bilangan bulat $1,2,\ldots,400$ dipilih 201 bilangan. Buktikan bahwa di antara 201 bilangan bulat terpilih terdapat 2 bilangan sehingga satu dari bilangan tersebut akan membagi bilangan yang lain.
[ON MIPA-PT Matematika 2009, Tingkat Wilayah]

Solusi

Misalkan $S=\{1,2,3, \ldots , 400 \}$. Perhatikan bahwa setiap anggota $S$ dapat ditulis sebagai $2^n \cdot k$, dengan $n$ bilangan bulat non negatif dan $k$ bilangan ganjil positif. Sebagai contoh, kita dapat menuliskan 24 sebagai $2^3 \cdot 3$. Namun, $2^2 \cdot 6$ bukanlah penulisan yang dimaksud, karena 6 bukan bilangan ganjil.

Karena $k$ ganjil, maka nilai $k$ yang mungkin adalah anggota dari $\{ 1,3,5, \ldots , 399 \}$. Sehingga terdapat 200 nilai $k$ yang mungkin. Berdasarkan Prinsip Sangkar Burung, jika kita memilih 201 bilangan, maka terdapat 2 bilangan dengan nilai $k$ sama. Misalkan kedua bilangan itu adalah $a=2^m \cdot k$ dan $b=2^n \cdot k$, untuk suatu bilangan bulat non negatif $m$ dan $n$. Jika $m < n$ maka $a \mid b$. Sedangkan, jika $m > n$ maka $b \mid a$. Dengan demikian, terdapat dua bilangan sehingga salah satu bilangan membagi bilangan yang lain. Terbukti.


Bagikan ke:
Click here if solved
Click here to save

Maaf, fitur ini hanya untuk pembaca yang telah terdaftar. Silakan Masuk atau buat akun terlebih dahulu.

Tambah Komentar