Menyusun : Bagaimana cara menyusun objek sesuai syarat yang diberikan?

Salah satu permasalahan kombinatorika adalah cara menyusun objek jika diberikan suatu syarat tertentu. Misalnya objek A tidak boleh di sebelah objek B, dan sebagainya.

Sesuai dengan pengertian kita mengenai kombinatorika sebelumnya, yaitu bahwa kombinatorika adalah studi matematika mengenai susunan objek, maka permasalahan paling mendasar dalam kombinatorika adalah menyusun.

Kaleb

Besok jadi kita nonton bioskop?

Faisal

Jadi dong. Aku sudah pesan tiket untuk kita berlima di baris kedua paling pinggir kanan.

Kaleb

Ingat ya. Aku maunya di paling kanan, dan sebelahku harus Rosita.

Faisal

Iya, iya. Aku tahu. Aku, Kevin, dan Siska tidak masalah duduk di posisi mana saja.

Berdasarkan dialog di atas, susunan duduk berikut ini (dari kiri ke kanan) memenuhi syarat yang diajukan Kaleb:

Faisal Kevin Siska Rosita Kaleb

Tentunya tidak hanya satu kemungkinan susunan. Susunan duduk seperti ini juga masih memenuhi syarat:

Siska Faisal Kevin Rosita Kaleb

Namun kalau Faisal menempati posisi di sebelah Kaleb, ini akan memicu perang dunia ketiga.

Siska Rosita Kevin Faisal Kaleb

Masalah seperti ini memiliki nama khusus, yaitu permutasi. Sederhananya, permutasi adalah urusan membolak-balik urutan. Dalam kasus ini, permutasi dilakukan terhadap posisi duduk kelima orang teman kita di atas. Permutasinya tidak dilakukan secara sembarang tetapi harus memenuhi syarat yang diberikan oleh Kaleb, yaitu:

A1

Kaleb harus di ujung kanan.

A2

Rosita harus di sebelah Kaleb.

Perhatikan bahwa selain syarat yang diajukan oleh Kaleb, terdapat syarat-syarat lain yang tidak disebutkan tetapi diasumsikan sudah diketahui oleh kelima orang tersebut, misalnya:

A3

memenuhi sifat barisan terurut dan terbatas, yaitu ada ujung kiri, berderet terus ke kanan dan ada ujung kanan.

A4

satu orang hanya menempati satu kursi.

A5

satu kursi hanya ditempati satu orang.

Syarat-syarat tambahan seperti ini biasanya diasumsikan sudah diketahui bersama, tetapi ada baiknya kamu selalu mendeskripsikannya agar tidak terjadi kesalahpahaman. Ingat bahwa matematika tidak boleh multi-tafsir (atau terdefinisi dengan baik) sehingga kita perlu selalu menyebutkan sespesifik mungkin aturan-aturan yang terlibat dalam suatu permasalahan, walaupun tidak perlu berlebihan.

Seandainya Kaleb dan Rosita tidak masalah duduk di posisi manapun, kita secara praktis dapat mengatakan bahwa susunan duduk mereka adalah tanpa syarat (seperti cintanya Kaleb pada Rosita, ehm), tetapi ingat bahwa walaupun tampaknya tanpa syarat, sebenarnya ada syarat tertentu yang sudah diasumsikan. Misalnya satu orang hanya menempati satu kursi.

Memperluas masalah

Dalam permasalahan ini, kita dapat mengajukan banyak pertanyaan, misalnya:

  • Adakah syarat-syarat lain yang belum disebutkan? Jika ada, apa sajakah syarat-syarat tersebut?
  • Bagaimana algoritma untuk memastikan bahwa susunan yang kita buat akan memenuhi syarat?
  • Jika ada yang ingin berpindah tempat duduk, susunan lain seperti apa yang berbeda dengan susunan sebelumnya, tetapi tetap memenuhi syarat?

Pertanyaan-pertanyaan apa lagi yang dapat kamu ajukan terkait masalah ini?

Jangan takut mengajukan pertanyaan. Pertanyaan yang baik akan membawamu menyelam semakin dalam sehingga kamu bisa melihat berbagai bijaksana yang ada di bawah lautan permasalahan. Jawabannya tidak tentu mudah, dan bahkan mungkin tidak akan dapat dijawab. Namun dalam proses pencariannya kamu akan mendapatkan hikmat yang lebih tinggi.

Kembali ke Go Ae-rin lagi

Dalam permasalahan yang dihadapi oleh Go Ae-rin, syarat-syarat apakah yang dapat kamu tarik berdasarkan adegan tersebut?

Hayo apa hayo!

Syarat-syarat bagi kemungkinan kode pintu adalah:

A1

Terdiri dari 4 digit 0-9.

A2

Urutan penekanan digit harus spesifik. Penekanan digit dalam kode yang benar, misalnya 2289, harus 2289, tidak boleh 2982.

A3

Hanya boleh 1 digit yang ditekan pada satu saat.

Setelah ada jejak penekanan tombol, diketahui bahwa digit yang digunakan adalah 2, 8, dan 9. Jadi syaratnya bertambah lagi:

A4

Digit yang digunakan hanya {2, 8, 9}.

T1

Kode mengandung 2 digit yang sama. Ini disimpulkan dari A1 dan A4.

Persegi ajaib

Persegi ajaib adalah kumpulan bilangan yang disusun dalam bentuk persegi, tetapi harus memenuhi syarat ini:

A1

Setiap kotak diisi dengan bilangan yang berbeda.

A2

Jumlah bilangan dalam setiap kolom, setiap baris, dan setiap diagonal sama.

Salah satu konfigurasi yang sesuai dengan syarat tersebut adalah:

163110
131925
28722

Dalam persegi ini, jumlah setiap bilangan dalam setiap kolom, baris, dan diagonal adalah 57.

Persoalan yang dapat ditanyakan dalam permasalahan ini misalnya:

  • Apakah hal yang terbaik yang dapat kita lakukan untuk membuat persegi semacam ini hanyalah dengan cara coba-coba? Adakah algoritma umum untuk menentukan susunan bilangan semacam ini?
  • Jika ada algoritma semacam itu, apakah algoritma itu hanya satu-satunya, atau ada algoritma lain yang juga akan menghasilkan susunan bilangan semacam ini?
  • Apakah persegi ajaib hanya ada pada ukuran 3×3 ataukah untuk sembarang ukuran n×n?
  • Jika diberikan jumlah yang diinginkan (misalnya 99), dapatkah kita membentuk persegi ajaib yang jumlahnya sedemikian?
  • Adakah jumlah yang tidak mungkin dimiliki oleh persegi ajaib?
  • Apakah persegi panjang ajaib - yaitu susunan bilangan m×n dengan mn mungkin dibuat?

Pertanyaan apa lagi yang dapat kamu ajukan terkait masalah ini?

Permasalahan lain dalam kategori ini

Masih banyak permasalahan lain yang termasuk dalam kategori ini. Beberapa di antaranya adalah:

Sudoku

Dalam permainan sudoku, kita harus mengisi 81 kotak yang disusun sebagai persegi dengan angka 1-9. Syarat yang diberikan misalnya angka yang sudah diberikan pada awalnya tidak boleh diganti, lalu setiap baris, kolom, dan sub-persegi 3×3 harus mengandung angka yang berbeda.

Jadwal pelajaran

Di sekolahmu pasti ada jadwal pelajaran, bukan? Jadwal pelajaran tidak disusun secara asal-asalan, tetapi harus memperhatikan syarat yang begitu banyak, seperti ruangan, mata pelajaran yang tersedia, guru yang hanya bisa mengajar pada hari tertentu, guru tidak dapat mengajar di dua ruangan berbeda, dan sebagainya. Ini permasalahan kombinatorika yang sangat sulit. Jadi kamu harus memberi penghormatan khusus pada guru yang merancang jadwal pelajaran di sekolahmu.

Sintesa protein

Tubuh manusia, hewan, dan tanaman tersusun atas protein. Protein pada dasarnya adalah rangkaian asam amino dengan urutan tertentu. Urutan asam amino yang berbeda akan menghasilkan protein yang berbeda.

Protein yang dihasilkan pada awalnya berbentuk rantai asam amino yang panjang, tetapi karena gaya elektromagnetik dan dengan bantuan sejumlah enzim tertentu protein itu akan melipat secara tiga dimensi membentuk alat-alat kecil dalam sel-sel tubuhmu yang digunakan untuk tujuan yang berbeda-beda.

Dengan memahami susunan dan mekanisme pembentukan protein, yang pada dasarnya adalah permasalahan kombinatorika, pada masa yang akan datang kita dapat membuat vaksin yang lebih ampuh, mengobati kanker, alergi, dan sebagainya.

Ditulis oleh
Ari Prasetyo
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
kombinatorika