Kombinatorika Bilangan Tertata |
Oleh: Kutha Ardana, Math-IPB Salah satu topik yang sedang hangat diperbincangkan di face book Matematika IPB adalah sebuah open problem yang berasal dari salah satu situs matematik, di-repost oleh Sdr. Aji Raditya. Masalahnya cukup sederhana: “Construct a set of ten numbers with a mean of 7, a median of 6, and a mode of 3.” Sdr. Rismanto sudah menginisiasi formulasi beserta sekitar 50-an contoh solusi untuk bilangan asli. Saya akan membatasi domain solusinya pada bilangan bulat taknegatif (bilangan cacah). Formulasi bagi masalah tersebut adalah: Tentukan gugus bilangan bulat taknegatif {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10} yang memenuhi: (1) x1 + x2 + ... + x10 =70 (2) x5 + x6 = 12, dengan (3) modus = 3 Syarat (2) mengharuskan bilangan-bilangan tersebut tertata (terurut) dari kecil ke besar, 0 <= x1 <= x2 <= x3 <= x4 <= x5 <= x6 <= x7 <= x8 <= x9 <= x10. Dari teknik kombinatorika, dengan mudah kita dapat menghitung (1), yakni ada sebanyak C(70 + (10-1), 10-1) = C(79, 9) = 205 811 513 765 solusi. Namun dengan adanya syarat (2) dan (3) tentu saja banyaknya solusi akan berkurang, dan inilah yang membuat masalah menjadi rumit. Persamaan (2) memiliki C(13, 1) = 13 solusi taknegatif, yakni (0,12), (1,11), (2,10), (3, 9), (4, 8), (5, 7), (6, 6), (7,5), …, (12,0). Namun berdasarkan syarat tataan dan letaknya di posisi 5 dan 6, maka hanya ada empat kemungkinan yang memenuhi, yakni (3, 9), (4, 8), (5, 7), (6, 6). Dari syarat (3) dan (2), bilangan 3 dapat muncul sedikitnya 2x, dan paling banyak 5x. Misalkan akan dihitung banyaknya solusi yang mengandung bilangan 3 sebanyak 5x. Pola gugus solusinya adalah {3, 3, 3, 3, 3, 9, x7, x8, x9, x10}, dengan x7 + x8 + x9 + x10 = 70 – (15 + 9) = 46, dan 9 <= x7 <= x8 <= x9 <= x10 (perhatikan, tdk mungkin x7 = x8 = x9 = x10 = 9). Solusi untuk x7, …, x10 adalah · 9, 3x : {x7, x8, x9, x10} = {9, 9, 9, 19} : 1 cara · 9, 2x : x9 + x10 = 28 -> ada sebanyak 28/2–10 +1 = 5 cara, dengan analisis serupa, · 9, 1x : 8 cara · 10, 3x : 1 cara · 10, 2x : 3 · 10, 1x : 3 · 11, 3x : 1 · 11, 2x : 1 Jadi untuk kasus bilangan 3 muncul 5x ada sebanyak 23 cara. Proses ini tentu dapat diteruskan untuk kasus bilangan 3 muncul sebanyak 2x, 3x, 4x. Meskipun pada dasarnya mudah, namun hal ini akan menyita banyak waktu. Berikut kita gunakan bantuan sistem aljabar komputer Mathematica untuk memperoleh seluruh solusi. Perintah yang dapat digunakan adalah FindInstance. FindInstance[expr, vars, dom, n] menampilkan contoh solusi ekspresi expr yg terdiri atas variabel vars, pada domain dom, sebanyak n buah. Bila banyaknya solusi < n, outpunya adalah sejumlah solusi tersebut. Contoh: ekspresi berikut memiliki 4 solusi bilangan bulat (meskipun diminta untuk menampulkan 5 solusi) FindInstance[ x^2 + y^2 == 1, {x, y}, Integers, 5]
{{x -> 0,y -> -1},{x -> 0,y -> 1},{x -> -1,y -> 0},{x -> 1,y -> 0}}
Berikut kode untuk memverifikasi analisis kasus di atas (bilangan 3 muncul 5x). sol1 = FindInstance[{15 + 9 + x7 + x8 + x9 + x10 == 70, 9 <= x7 <= x8 <= x9 <= x10}, {x7, x8, x9, x10}, Integers, 25] /. (x_ -> y_) -> y
{{9, 9, 9, 19}, {9, 9, 10, 18}, {9, 9, 11, 17}, {9, 9, 12, 16}, {9, 9, 13, 15}, {9, 9, 14, 14}, {9, 10, 10, 17}, {9, 10, 11, 16}, {9, 10, 12, 15}, {9, 10, 13, 14}, {9, 11, 11, 15}, {9, 11, 12, 14}, {9, 11, 13, 13}, {9, 12, 12, 13}, {10, 10, 10, 16}, {10, 10, 11, 15}, {10, 10, 12, 14}, {10, 10, 13, 13}, {10, 11, 11, 14}, {10, 11, 12, 13}, {10, 12, 12, 12}, {11, 11, 11, 13}, {11, 11, 12, 12}}
Ada sebanyak 23 solusi, Length@sol1 23 Kode berikut menentukan seluruh solusi masalah yang dibicarakan. sol mencari 60 000 solusi dari syarat (1) dan (2). sol = FindInstance[{Total[{x1, x2, x3, x4, x5, x6, x7, x8, x9,x10}] == 70, x5 + x6 == 12,0 <= x1 <= x2 <= x3 <= x4 <= x5 <= x6 <= x7 <= x8 <= x9 <= x10}, {x1, x2, x3, x4, x5, x6, x7, x8, x9, x10},Integers,60000] /.(x_->y_)->y; Berikutnya, sol disaring yang memenuhi modus 3 sol2=Extract[sol,Position[Commonest/@sol,{3}]]//Sort; Length[sol2] 1773 Jadi permasalahan tersebut secara keseluruhan memiliki 1773 solusi bilangan bulat taknegatif dengan distribusi modus 3 sbb. Tally[(Count[#,3]&/@sol2)] {{2, 209}, {3, 1192}, {4, 349}, {5, 23}} Artinya, bilangan 3 muncul 2x sebanyak 209, 3x sebanyak 1192, 4x sebanyak 349, 5x sebanyak 23. Ingin melihat keseluruhan solusi dimaksud? Evaluasi sol2.
Kutha Ardana, Math-IPB, 2 Juli 2011 |
< Sebelumnya | Berikutnya > |
---|