Kombinatorika: Mengisi Slot dengan Syarat
Konsep Dasar Metode Slot
Metode slot bekerja dengan mengalikan banyak pilihan di tiap posisi untuk mencari total kemungkinan susunan. Bayangkan kita sedang menyusun tim estafet: ada beberapa posisi lari yang harus diisi satu per satu oleh pelari yang tersedia. Setiap posisi lari ini kita gambarkan sebagai sebuah kotak atau "slot".
Kenapa jumlah pilihannya harus dikali, bukan ditambah? Prinsip ini disebut aturan perkalian. Setiap satu pilihan di posisi pertama akan membuka cabang baru untuk pilihan di posisi kedua.
Sebagai contoh, jika kita memilih ketua dan wakil dari $3$ kandidat ($A$, $B$, dan $C$):
Posisi ketua (Posisi 1) memiliki $3$ pilihan kandidat.
Untuk setiap ketua yang terpilih, posisi wakil (Posisi 2) memiliki $2$ pilihan tersisa.
Karena setiap cabang pertama berpasangan dengan masing-masing cabang kedua, total susunan yang terbentuk adalah hasil kalinya: $3 \times 2 = 6$ kemungkinan pasangan.
Makna Angka Berbeda
Syarat 'angka berbeda' berarti angka yang sudah dipakai di satu slot tidak tersedia lagi untuk slot berikutnya. Dalam analogi tim estafet, pelari yang sudah berlari di etape pertama tidak boleh berlari lagi di etape kedua. Inilah yang disebut penyusunan tanpa pengulangan.
Akibat dari aturan tanpa pengulangan ini sangat jelas pada perhitungan: jumlah pilihan di setiap slot berikutnya selalu berkurang satu.
Mari kita bandingkan dua kondisi saat menyusun $3$ angka dari $5$ angka yang tersedia ($0, 1, 2, 3, 4$):
Boleh berulang: Angka yang sudah dipakai bebas digunakan kembali. Setiap slot tetap memiliki $5$ pilihan angka, sehingga totalnya $5 \times 5 \times 5 = 125$ susunan.
Tanpa pengulangan (angka berbeda): Slot pertama memiliki $5$ pilihan. Setelah satu angka terpasang, slot kedua hanya memiliki $4$ pilihan, dan slot ketiga tersisa $3$ pilihan. Totalnya menjadi $5 \times 4 \times 3 = 60$ susunan.
Sebuah PIN 4 digit dibuat dari angka 1 sampai 9 dengan syarat semua angka harus berbeda (tanpa pengulangan). Berapa banyak pilihan angka yang tersedia khusus untuk mengisi digit ketiga?
- 9 pilihan
- 7 pilihan
- 8 pilihan
- 6 pilihan
Jawaban: 7 pilihan
Tersedia 9 angka (1 sampai 9). Karena syaratnya tanpa pengulangan, digit pertama menghabiskan 1 angka dan digit kedua menghabiskan 1 angka lagi. Dengan demikian, sudah ada 2 angka yang terpakai, sehingga pilihan untuk digit ketiga tersisa $9 - 2 = 7$ pilihan. Pilihan A (9) keliru karena menganggap boleh berulang, C (8) keliru karena baru mengurangi 1 angka, dan D (6) keliru karena mengurangi terlalu banyak.
Syarat tanpa pengulangan mengurangi jumlah pilihan di slot berikutnya.
Prioritas Syarat Khusus
Slot yang memiliki syarat paling ketat harus diisi lebih dulu agar tidak kehabisan pilihan yang sesuai. Dalam analogi tim estafet, jika ada aturan bahwa pelari terakhir harus seorang sprinter spesialis, kita wajib menempatkan sprinter itu di posisi terakhir terlebih dahulu. Jika posisi lain diisi sembarangan sejak awal, pelari sprinter tersebut bisa terlanjur dipakai di tempat lain dan tim kita melanggar aturan.
Pada soal kita, ada dua syarat khusus: angka terakhir harus $1$ atau $3$, dan angka pertama bukan $0$. Di antara keduanya, syarat angka terakhir jauh lebih spesifik karena pilihannya dibatasi secara langsung pada dua angka tertentu. Oleh karena itu, kita prioritaskan pengisian slot terakhir terlebih dahulu:
Langkah 1 (Slot Terakhir): Angka yang diperbolehkan hanyalah $1$ atau $3$, sehingga ada $2$ pilihan.
Setelah slot terakhir mengunci satu angka (entah angka $1$ atau $3$), kita beralih ke syarat khusus berikutnya di slot pertama:
Langkah 2 (Slot Pertama): Dari total $5$ angka ($0, 1, 2, 3, 4$), sebanyak $1$ angka ganjil sudah terpakai di belakang, menyisakan $4$ angka. Namun, angka pertama tidak boleh $0$. Karena $0$ pasti masih ada di antara $4$ angka tersisa tersebut, kita kurangi $0$ dari pilihan, sehingga slot pertama menyisakan tepat $3$ pilihan angka.