Last Updated on Juli 28, 2021 by prooffic
Postingan kali ini akan menyajikan Pembahasan Soal KNMIPA 2020 Uraian Kombinatorika. Pembahasan kali ini melibatkan Prinsip Sangkar Burung Merpati (Pigeon Hole Principle), prinsip perkalian dan kombinasi. Prinsip ini seringkali muncul di Seleksi ONMIPA/KNMIPA Tingkat Wilayah. Sebelumnya, kita terlebih dahulu melihat pernyataan dari prinsip-prinsip/aturan-aturan tersebut
**Selamat menikmati**
Pendahuluan
Prinsip Sangkar Burung Merpati :Ada beberapa versi bunyi prinsip tersebut, di antaranya adalah sebagai berikut:
- Misalkan terdapat $m$ burung merpati dan $n\geq 1$ sangkar dan misalkan pula bahwa burung merpati tersebut semuanya akan dimasukkan ke dalam sangkar tersebut. Jika $m > n, $maka terdapat paling sedikit $2$ burung merpati yang terletak pada sangkar yang sama.
- Diberikan $m,n$ bilangan asli dengan $n\geq 1.$ Misalkan $A_m$ adalah himpunan dengan $m$ anggota dan $A_n$ adalah himpunan dengan $n$ anggota. Jika $m > n,$ maka tidak terdapat fungsi satu-satu dari $A_m$ ke $A_n.$
Prinsip Perkalian: Misalkan $A$ adalah himpunan dengan $m$ anggota berbeda dan $B$ adalah himpunan dengan $n$ anggota berbeda. Maka, banyaknya pasangan berbeda ($A$ dan $B$ masing-masing 1 anggota) yang dapat terbentuk adalah $m \times n.$
Aturan Kombinasi: Misalkan $m \geq n$ adalah dua bilangan tak negatif dan misalkan terdapat $m$ objek berbeda, maka banyaknya cara memilih $n$ objek dari $m$ objek tersebut adalah ${m \choose n}.$
Soal dan Pembahasan
Hari pertama
Diberikan himpunan $A = \{a_1, a_2, \cdots, a_n\}.$ Bila Anda memilih $2^{n-1}+1$ himpunan berbeda dari $A,$ buktikan bahwa di antara $2^{n-1}+1$ himpunan bagian terpilih terdapat dua himpunan sedemikian sehingga yang satu adalah himpunan bagian dari yang lain.
Jawab: Tinjau himpunan $\mathcal{P},$ yaitu keluarga himpunan yang terdiri dari subhimpunan dari $A$ yang tidak memuat $a_1.$ $A’$ subset dari $A$ dikatakan berpasangan dengan suatu unsur $A”$ di $\mathcal{P}$ jika $A’ = A”$ atau $A’-A” = \{a_1\}.$ Perhatikan bahwa setiap subhimpunan dari $A$ berpasangan dengan tepat satu unsur di $\mathcal{P}.$ Misalkan diambil $2^{n-1}+1$ subhimpunan berbeda dari $A,$ karena banyaknya anggota dari $\mathcal{P}$ adalah $2^{n-1},$ maka berdasarkan pigeon hole principle, terdapat paling sedikit dua subhimpunan tersebut yang memiliki pasangan yang sama.
Misalkan kedua subhimpunan tersebut adalah $A_1$ dan $A_2$ dengan pasangannya di $\mathcal{P}$ adalah $A”.$ Catat bahwa $A_1$ dan $A_2$ berbeda. Jika $A_1 = A”,$ maka haruslah $A_2 – A” =\{a_1\}$ yang berakibat bahwa $A_1$ adalah subhimpunan dari $A_2.$ Jika $A_1 – A” =\{a_1\}.$ maka haruslah $A_2 = A”$ yang berakibat bahwa $A_2$ adalah subhimpunan dari $A_1.$ Dari sini, di antara $2^{n-1}+1$ subhimpunan berbeda dari $A$ yang terpilih, senantiasa terdapat paling sedikit dua himpunan sedemikian sehingga yang satu adalah subhimpunan dari yang lain $\blacksquare$
Baca juga:
1. Soal dan pembahasan KNMIPA 2020 Matematika Analisis Real
2. Soal dan pembahasan KNMIPA 2020 Aljabar Linear
3. Pembahasan soal KNMIPA 2020 Kombinatorika Isian Singkat
Hari Kedua
Untuk bilangan bulat $x,y \geq 1, $tuliskan bukti kombinatorial dari $$xy = {x + y \choose 2} – {x \choose 2} – {y \choose 2}$$
Jawab: Pada suatu tim bulutangkis, terdapat $x$ atlet laki-laki dan $y$ atlet perempuan. Pelatih dari tim tersebut akan membentuk ganda campuran untuk mengikuti suatu turnamen. Berdasarkan prinsip perkalian, maka banyaknya ganda campuran yang terbentuk adalah $xy.$ Banyaknya ganda campuran yang dapat terbentuk tersebut dapat ditentukan dengan cara berbeda sebagai berikut.
banyaknya ganda bulutangkis keseluruhan yang dapat terbentuk adalah ${x + y \choose 2}, $yang terdiri dari ganda putri, ganda putra dan ganda campuran. Banyaknya ganda putra yang dapat terbentuk adalah ${x \choose 2}$ berdasarkan aturan kombinasi. Sedangkan banyaknya ganda putri yang dapat terbentuk adalah ${y \choose 2}.$ Sehingga, banyaknya ganda campuran yang mungkin adalah banyaknya ganda yang dapat terbentuk secara keseluruhan dikurangi dengan jumlah dari banyaknya ganda putra dan ganda putri yang terbentuk, yaitu $${x + y \choose 2} – {x \choose 2} – {y \choose 2}$$
Sehingga, diperoleh bahwa banyaknya ganda campuran yang dapat terbentuk adalah $xy$ dan ${x + y \choose 2} – {x \choose 2} – {y \choose 2}.$ Sehingga, haruslah $$xy = {x + y \choose 2} – {x \choose 2} – {y \choose 2} \blacksquare$$
Sekian postingan kali ini tentang Pembahasan Soal KNMIPA 2020 Uraian Kombinatorika. Jika Anda tertarik dengan postingan lainnya mengenai KNMIPA/ONMIPA, silahkan ke sini. Jika Anda tertarik dengan topik lainnya, silahkan ke sini. Semoga membantu. Sekian dan terima kasih.
