KimiaMath

Dalam tulisan ini, kita akan membahas soal Kombinatorika dalam ON MIPA-PT Matematika Tahun 2009. Biasanya, soal Kombinatorika terdiri dari delapan soal isian singkat dan tiga soal uraian. Namun, dalam naskah soal yang saya unduh di internet, hanya tersedia dua soal uraian. Sebelumnya, kita telah membahas soal isian singkat Kombinatorika tahun 2009. Jadi, sebagai lanjutan tulisan tersebut, kita akan membahas dua soal uraian yang tersisa.

Nomor 1

Dari 400 bilangan bulat 1, 2, …, 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.

PEMBAHASAN
Di antara 400 bilangan bulat tersebut, terdapat sebanyak 200 bilangan ganjil. Distribusikan setiap bilangan ganjil tersebut ke tepat satu himpunan. Misalkan A_k menyatakan himpunan yang memuat bilangan ganjil k.

Selanjutnya, kita akan mendistribusikan 200 bilangan genap yang tersisa ke dalam 200 himpunan tersebut. Namun, kita tidak boleh mendistribusikan secara acak. Dalam setiap himpunan, di antara dua bilangan berbeda, salah satunya harus membagi bilangan yang lain. Agar kondisi ini terpenuhi, kita harus mengelompokkan bilangan dalam bentuk k, k \cdot 2, k \cdot 2^2, dan seterusnya, ke dalam himpunan A_k.

Distribusikan bilangan genap (dari 2 sampai 400) yang dapat ditulis sebagai k \cdot 2^r, untuk suatu bilangan asli r, ke dalam himpunan A_k. Berikut adalah himpunan yang terbentuk:

    \begin{align*} A_1 &= \{ 1,1 \cdot 2^1,1 \cdot 2^2,1 \cdot 2^3, \ldots , 1 \cdot 2^8 \} \\ &= \{ 1,2,4,8, \ldots , 256 \} \\ A_3 &= \{ 3,3 \cdot 2^1,3 \cdot 2^2,3 \cdot 2^3, \ldots , 3 \cdot 2^7 \} \\ &= \{ 3,6,12,24, \ldots , 384 \} \\ A_5 &= \{ 5,5 \cdot 2^1,5 \cdot 2^2,5 \cdot 2^3, \ldots , 5 \cdot 2^6 \} \\ &= \{ 5,10,20,40, \ldots, 320 \} \\ &\vdots \\ A_{397} &= \{ 397 \} \\ A_{399} &= \{ 399 \} \end{align*}

Dengan cara ini, 400 bilangan telah didistribusikan ke dalam 200 himpunan. Berdasarkan Prinsip Sangkar Burung (Pigeon Hole Principle), jika dipilih 201 bilangan maka sedikitnya terdapat 2 bilangan yang berada pada himpunan yang sama. Untuk setiap dua anggota pada himpunan di atas, bilangan yang satu membagi bilangan yang lainnya.
Terbukti.

Jadi, di antara 201 bilangan bulat yang terpilih, terdapat 2 bilangan sehingga satu dari bilangan tersebut akan membagi bilangan yang lain.

Nomor 2

Diberikan barisan a_1,a_2, \ldots ,a_{2n} yang terdiri dari n buah 1 dan n buah -1 dengan jumlahan parsialnya memenuhi sifat

    \[a_1+a_2+ \cdots +a_k \geq 0 \quad (k=1,2,3,\ldots,2n)\]

Perlihatkan bahwa banyaknya barisan yang demikian adalah \frac{1}{n+1} \binom{2n}{n}.

PEMBAHASAN
Misalkan barisan yang memenuhi disebut barisan keren, dan barisan yang tidak memenuhi disebut barisan jelek.

Agar pembahasan soal ini lebih mudah dipahami, kita akan meninjau kasus yang lebih sederhana terlebih dahulu. Misalnya, nilai n adalah 3. Suku pertama pada barisan keren harus satu, karena jumlahan parsial a_1 \geq 0. Selain itu, pada setiap jumlahan parsial, banyaknya angka 1 harus lebih dari atau sama dengan banyaknya angka -1. Salah satu barisan keren adalah 1,-1,1,1,-1,-1.

Contoh barisan jelek adalah 1,-1,-1,1,1,-1, karena

    \[a_1+a_2+a_3=1+(-1)+(-1)=-1 \leq 0\]

Perhatikan suku barisan yang pertama kali membuat jumlahan parsialnya negatif. Dalam barisan ini, yang dimaksud adalah suku ketiga (-1 yang kedua). Sekarang, kita akan melakukan sedikit perubahan. Kita ganti nilai dari tiga suku pertama dengan aturan: suku yang mulanya 1 menjadi -1 dan yang mulanya -1 menjadi 1. Sehingga kita memperoleh barisan -1,1,1,1,1,-1 yang terdiri dari 4 buah 1 dan 2 buah -1.

Contoh barisan jelek lainnya adalah 1,1,-1,-1,-1,1. Dengan cara yang sama, kita memperoleh barisan bersesuaian yang terdiri dari 4 buah 1 dan 2 buah -1, yaitu -1,-1,1,1,1,1.

Prosedur di atas dapat dibalik. Misalkan kita diberikan barisan yang terdiri dari 4 buah 1 dan 2 buah -1, yaitu -1,1,1,-1,1,1. Suku barisan yang pertama kali membuat jumlahan parsialnya positif adalah suku ketiga. Dengan aturan penukaran yang sama, kita memperoleh barisan 1,-1,-1,-1,1,1 yang merupakan barisan jelek.

Dari uraian di atas, kita dapat melihat adanya korespondensi satu-satu antara barisan jelek dengan barisan yang terdiri dari 4 buah 1 dan 2 buah -1. Akibatnya, banyaknya barisan jelek sama dengan banyaknya barisan yang terdiri dari 4 buah 1 dan 2 buah -1.

Suku pertama pada barisan keren harus 1, karena jumlahan parsial a_1 \geq 0. Selain itu, banyaknya suku 1 pada setiap jumlahan parsial harus lebih dari atau sama dengan banyaknya suku -1. Misalkan banyaknya barisan keren adalah x dan banyaknya barisan jelek adalah y. Banyaknya barisan dengan n buah -1 dan n buah 1 adalah \binom{2n}{n}, sehingga banyaknya barisan keren adalah

    \[x=\binom{2n}{n}-y\]

Kita akan menentukan banyaknya barisan jelek. Misalkan a_m adalah suku pertama yang membuat jumlahan parsial barisan jelek bernilai negatif. Suku-suku a_1,a_2, \ldots,a_{m-1} memiliki jumlah 0, dengan kata lain, banyaknya suku -1 sama dengan banyaknya suku 1.

Untuk m suku pertama, ganti suku yang mulanya -1 menjadi 1 dan yang mulanya 1 menjadi -1. Di antara m-1 suku pertama, banyaknya suku 1 sama dengan banyaknya suku -1, sehingga penggantian ini tidak akan mengubah banyaknya suku 1 dan -1 secara keseluruhan. Namun, ini akan berubah saat kita mengganti nilai suku a_m dari -1 menjadi 1. Dengan cara ini, akan terbentuk barisan baru yang terdiri dari n+1 buah 1 dan n-1 buah -1.

Proses ini dapat dibalik. Misalnya diberikan barisan dengan n+1 buah 1 dan n-1 buah -1, dan suku pertama yang membuat jumlahan parsialnya bernilai positif adalah a_k (pasti terdapat suku yang seperti ini, sebab suku yang bernilai 1 lebih banyak dari suku yang bernilai -1). Dengan mengganti k suku pertama, yang mulanya -1 menjadi 1 dan yang mulanya 1 menjadi -1, kita akan memperoleh barisan baru yang terdiri n buah 1 dan n buah -1. Jumlah k suku pertama pada barisan ini bernilai negatif, sehingga barisan ini termasuk barisan jelek.

Nah, dari uraian di atas, kita dapat melihat adanya korespondensi satu-satu antara barisan jelek dengan barisan yang terdiri dari n+1 buah 1 dan n-1 buah -1. Sehingga, banyaknya barisan jelek sama dengan banyaknya barisan yang terdiri dari n+1 buah 1 dan n-1 buah -1, yaitu

    \[y=\binom{2n}{n-1}\]

Berikutnya, kita akan menggunakan nilai y untuk menghitung banyaknya barisan keren.

    \begin{align*} x &= \binom{2n}{n}-\binom{2n}{n-1} \\ &= \frac{(2n)!}{n!n!}-\frac{(2n)!}{(n+1)!(n-1)!} \\ &= \frac{(2n)!}{n! \cdot n \cdot (n-1)!}-\frac{(2n)!}{(n+1) \cdot n! \cdot (n-1)!} \\ &= \left( \frac{1}{n}-\frac{1}{n+1} \right) \frac{(2n)!}{n!(n-1)!} \\ &= \frac{1}{n(n+1)} \cdot \frac{(2n)!}{n!(n-1)!} \\ &= \frac{1}{n+1} \cdot \frac{(2n)!}{n!n!} \\ &= \frac{1}{n+1} \binom{2n}{n} \end{align*}

Jadi, banyaknya barisan keren adalah \frac{1}{n+1} \binom{2n}{n}.
Terbukti.

Semoga bermanfaat! Jika ada yang perlu diperbaiki atau anda punya solusi yang berbeda, silakan beritahu melalui komentar. 🙂

Tinggalkan Komentar