4. Prinsip Sangkar Merpati dan Penggunaan Kombinasi
A). Prinsip Sangkar Merpati
Prinsip Sangkar Merpati (Pigeonhole Principle, disingkat PHP) disebut juga dengan "Drawer Principle" atau "Dirichlet's Principle". Prinsip sangkar merpati sangat berguna dalam pembuktian beberapa masalah matematika.
Prinsip-prinsip Sangkar Merpati:
Prinsip I:
Jika \(n+1\) merpati dimasukkan ke dalam \(n\) sangkar merpati (\(n\) bilangan asli), maka setidaknya terdapat satu sangkar yang memiliki lebih dari 1 merpati. Secara umum, jika terdapat lebih dari \(pn\) benda dimasukkan ke dalam \(n\) kotak, maka sedikitnya ada satu kotak berisi lebih dari \(p\) benda.
Prinsip II:
Jika \(n\) merpati dimasukkan ke dalam \(m\) sangkar merpati, maka terdapat satu sangkar yang memiliki setidaknya \(\left\lfloor\frac{n-1}{m}\right\rfloor+1\) merpati.
Di dalam kelas terdapat 38 siswa. Paling sedikit berapa siswa yang memiliki tanggal lahir yang sama di kelas tersebut?
Banyaknya kemungkinan tanggal lahir dalam satu bulan ada \(m = 31\) tanggal (sangkar).
Jumlah siswa di dalam kelas adalah \(n = 38\) siswa (merpati).
Berdasarkan Prinsip Sangkar Merpati II, paling sedikit siswa yang memiliki tanggal lahir sama adalah:
\[\left\lfloor\frac{n-1}{m}\right\rfloor+1 = \left\lfloor\frac{38-1}{31}\right\rfloor+1 = \left\lfloor\frac{37}{31}\right\rfloor+1 = 1 + 1 = 2 \text{ siswa}\]Berapakah jumlah siswa paling sedikit pada satu kelas agar terdapat minimal 2 orang yang memiliki kelahiran pada bulan yang sama?
Terdapat \(m = 12\) bulan dalam satu tahun sebagai sangkar.
Berdasarkan Prinsip Sangkar Merpati I, agar terjamin ada minimal 2 orang lahir di bulan yang sama (\(n > m\)), maka jumlah siswa paling sedikit yang dibutuhkan adalah:
\[n = m + 1 = 12 + 1 = 13 \text{ siswa}\]Di dalam sebuah kantong terdapat 30 kelereng biru, 20 kelereng kuning, 15 kelereng merah, dan 10 kelereng putih. Tanpa melihat isi kantong, tentukan banyaknya kelereng paling sedikit yang harus kamu ambil, sehingga dapat dipastikan kamu mendapat paling sedikit 4 kelereng berwarna sama.
Terdapat 4 variasi warna kelereng (biru, kuning, merah, putih).
Kondisi terburuk (worst-case scenario) adalah ketika kita telah mengambil masing-masing 3 kelereng dari setiap warna tanpa ada satu pun warna yang mencapai 4 kelereng:
\[\text{Total kelereng terambil} = 3 \times 4 = 12 \text{ kelereng}\]Pada pengambilan kelereng ke-13, kelereng warna apa pun yang terambil pasti akan membuat salah satu warna berjumlah 4 kelereng.
Jadi, banyak kelereng minimal yang harus diambil adalah \(12 + 1 = 13\) kelereng.
Di dalam sebuah peti terdapat 9 bola merah, 4 bola kuning, 11 bola hijau, 7 bola biru, dan 1 bola hitam. Tentukan banyaknya bola paling sedikit yang harus diambil dari dalam peti itu agar kita dapat menjamin bahwa pasti terambil paling sedikit dua bola berwarna berbeda.
Kondisi terburuk terjadi jika kita terus mengambil bola dari warna yang jumlahnya terbanyak terlebih dahulu.
Bola hijau memiliki jumlah terbanyak, yaitu 11 bola. Jika kita mengambil 11 bola, ada kemungkinan seluruhnya berwarna hijau (hanya 1 warna).
Pengambilan ke-12 dipastikan akan menghasilkan warna kedua yang berbeda.
Jadi, banyak bola minimal yang harus diambil adalah \(11 + 1 = 12\) bola.
Andik mempunyai 36 manik-manik yang terdiri dari lima warna berbeda. Berapa sedikitnya manik-manik Andi yang mempunyai warna sama?
Diketahui jumlah manik-manik \(n = 36\) dan jumlah warna \(m = 5\).
Berdasarkan Prinsip Sangkar Merpati II, sedikitnya manik-manik yang memiliki warna sama adalah:
\[\left\lfloor\frac{n-1}{m}\right\rfloor+1 = \left\lfloor\frac{36-1}{5}\right\rfloor+1 = \left\lfloor\frac{35}{5}\right\rfloor+1 = 7 + 1 = 8 \text{ manik-manik}\]B). Penggunaan Kombinasi
(i). Binomial Newton
Bentuk ekspansi binomial secara umum:
\[(a+b)^{n}=\sum_{r=0}^{n}C_{r}^{n}a^{n-r}b^{r}\] \[(a+b)^{n}=C_{0}^{n}a^{n}b^{0}+C_{1}^{n}a^{n-1}b^{1}+\dots+C_{n-1}^{n}a^{1}b^{n-1}+C_{n}^{n}a^{0}b^{n}\]Catatan penting:
- Jika \(a=b=1\), maka: \[2^{n}=C_{0}^{n}+C_{1}^{n}+\dots+C_{n-1}^{n}+C_{n}^{n}\]
- Suku ke-\(k\) dari ekspansi Binomial Newton adalah: \[T_k = C_{(k-1)}^{n}a^{n-(k-1)}b^{k-1}\]
Jabarkanlah bentuk berikut:
a). \((x+2)^4\)
b). \((2m+3n)^3\)
a). \((x+2)^4\):
\[\begin{aligned} (x+2)^4 &= C_0^4 x^4(2)^0 + C_1^4 x^3(2)^1 + C_2^4 x^2(2)^2 + C_3^4 x^1(2)^3 + C_4^4 x^0(2)^4 \\ &= 1 \cdot x^4 \cdot 1 + 4 \cdot x^3 \cdot 2 + 6 \cdot x^2 \cdot 4 + 4 \cdot x \cdot 8 + 1 \cdot 1 \cdot 16 \\ &= x^4 + 8x^3 + 24x^2 + 32x + 16 \end{aligned}\]b). \((2m+3n)^3\):
\[\begin{aligned} (2m+3n)^3 &= C_0^3 (2m)^3 + C_1^3 (2m)^2(3n)^1 + C_2^3 (2m)^1(3n)^2 + C_3^3 (3n)^3 \\ &= 1 \cdot (8m^3) + 3 \cdot (4m^2)(3n) + 3 \cdot (2m)(9n^2) + 1 \cdot (27n^3) \\ &= 8m^3 + 36m^2n + 54mn^2 + 27n^3 \end{aligned}\]Ubahlah bentuk berikut menjadi bentuk pangkat:
\[C_{1}^{2021}+C_{3}^{2021}+C_{5}^{2021}+\dots+C_{2019}^{2021}+C_{2021}^{2021}\]Berdasarkan sifat kombinasi Binomial Newton, jumlah kombinasi dengan indeks ganjil adalah seperdua dari total jumlah seluruh koefisien:
\[C_1^n + C_3^n + C_5^n + \dots = 2^{n-1}\]Dengan \(n = 2021\), diperoleh:
\[C_{1}^{2021}+C_{3}^{2021}+\dots+C_{2021}^{2021} = 2^{2021-1} = 2^{2020}\]Dari bentuk \((3x+y)^{50}\), tentukan koefisien dari \(x^{26}y^{24}\).
Suku umum dari \((a+b)^n\) adalah \(C_r^n a^{n-r} b^r\). Di sini \(a = 3x\), \(b = y\), dan \(n = 50\).
Untuk mendapatkan variabel \(x^{26}y^{24}\), kita pilih \(r = 24\) (sehingga \(n-r = 50-24 = 26\)):
\[\text{Suku} = C_{24}^{50} (3x)^{26} (y)^{24} = C_{24}^{50} \cdot 3^{26} \cdot x^{26}y^{24}\]Jadi, koefisien dari \(x^{26}y^{24}\) adalah \(C_{24}^{50} \cdot 3^{26}\).
(ii). Banyak Lintasan Terpendek
Perhatikan grid berukuran \(m \times n\) berikut:
Kita akan menghitung banyak lintasan terpendek dari A ke B. Lintasan terpendek hanya terjadi jika kita selalu berjalan ke kanan dan ke atas. Dengan demikian, kita harus melangkah sejauh \(m+n\) dengan \(m\) di antaranya ke kanan dan sisanya ke atas, sehingga kita memilih \(m\) langkah ke kanan dari \(m+n\) langkah kemudian memilih \(n\) langkah ke atas dari sisanya. Banyaknya cara adalah \(C_{m}^{m+n} \times C_{n}^{n} = C_{m}^{m+n}\) atau \(C_{n}^{m+n}\).
\[\text{Banyak lintasan terpendek} = C_{m}^{m+n} \quad \text{atau} \quad C_{n}^{m+n}\]Pada grid berukuran \(5 \times 3\), tentukan banyak lintasan terpendek dari titik pojok kiri bawah ke titik pojok kanan atas.
Grid berukuran \(m \times n = 5 \times 3\), artinya terdapat \(m = 5\) langkah ke kanan dan \(n = 3\) langkah ke atas. Total langkah \(= 5 + 3 = 8\).
\[\text{Banyak lintasan} = C_3^8 = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \text{ cara}\](iii). Star and Bar Theorem
Misalkan terdapat \(x_{1} \ge 0, x_{2} \ge 0, \dots, x_{k} \ge 0\) yang memenuhi persamaan:
\[x_{1}+x_{2}+\dots+x_{k}=n\]Banyak solusi pasangan \((x_{1}, x_{2}, \dots, x_{k})\) bilangan bulat non-negatif adalah:
\[\text{Banyak solusi} = C_{n}^{n+k-1} \quad \text{atau} \quad C_{k-1}^{n+k-1}\]Budi memiliki 8 kelereng merah, 9 kelereng hitam, dan 10 kelereng biru. Jika Budi ingin mengambil 4 kelereng (boleh hanya satu warna saja) untuk diberikan ke temannya, maka ada berapa cara pengambilan yang mungkin?
Misalkan \(x_1, x_2, x_3\) berturut-turut menyatakan banyak kelereng merah, hitam, dan biru yang diambil.
Persamaan matematika yang memenuhi: \(x_1 + x_2 + x_3 = 4\) dengan \(x_i \ge 0\).
Karena jumlah kelereng tiap warna yang tersedia (\(\ge 8\)) melebihi total kelereng yang diambil (\(4\)), maka tidak ada pembatasan atas.
Dengan Star and Bar Theorem (\(n = 4\) dan \(k = 3\)):
\[\text{Banyak cara} = C_4^{4+3-1} = C_4^6 = \frac{6 \times 5}{2 \times 1} = 15 \text{ cara}\]Soal Latihan
Demikian pembahasan materi Prinsip Sangkar Merpati dan Penggunaan Kombinasi Olim Matik SMP dan contoh-contohnya. Silahkan juga baca materi lain yang berkaitan dengan materi ini. Setiap artikel akan diupdate secara bertahap. Jika ada kritik dan saran, atau koreksi dari isi artikel di halaman ini, mohon bantuannya untuk menuliskannya di kolom komentar di bagian bawah setiap artikel. Ini sangat membantu untuk memperbaiki kualitas dari artikel di blog koma. Semoga bermanfaat. Terimakasih.
