ONMIPA PT 2017 Kombinatorik

By | June 29, 2019

BAGIAN KEDUA

Soal 1.   Seorang petinju mempunyai waktu \(75\) minggu untuk mempertahankan gelar. Untuk itu pelatih menjadwalkan program latih tanding. Pelatih merencanakan sedikitnya terdapat satu latih tanding dalam satu minggu, tetapi tidak lebih dari total \(125\) latih tanding dalam periode \(75\) minggu. Perlihatkan ada periode waktu yang terdiri atas beberapa minggu berturutan sehingga terdapat tepat \(24\)  latih tanding dalam periode waktu tersebut.

Solusi.   Misalkan  \({{a}_{i}}\) adalah banyaknya latih tanding yang telah dilakukan petinju sampai minggu ke \(i\) dengan \(i=1,2,3,…,75\) . Maka  kita memiliki

\(1\le {{a}_{1}}<{{a}_{2}}<{{a}_{3}}<…<{{a}_{{75}}}\le 125\)

Dan

\(25\le {{a}_{1}}+24<{{a}_{2}}+24<{{a}_{3}}+24<…<{{a}_{{75}}}+24\le 149\)

Karena dari 1 hingga 149 hanya terdapat 149 bilangan sedangkan

\({{a}_{1}},{{a}_{2}},{{a}_{3}},…,{{a}_{{75}}},{{a}_{1}}+24,{{a}_{2}}+24,{{a}_{3}}+24,…,{{a}_{{75}}}+24\)

barisan dengan \(150\)  bilangan, maka menurut pigeon hole principle setidaknya tedapat dua bilangan yang sama dari barisan tersebut, yakni terdapat  ada \(i\) dan \(j\)  sehingga \({{a}_{i}}={{a}_{j}}+24\) . Dengan kata lain pada minggu ke-\(j+1\) , \(j+2\) , …., \(i\)  si pentinju tepat latih tanding sebanyak \(24\) kali. (Shown)

Soal 2.   Diberikan bilangan bulat \(n\ge 5\) . Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan bahwa

\(\left( {\begin{array}{*{20}{c}} {2n} \\ 5 \end{array}} \right)=2\left( {\begin{array}{*{20}{c}} n \\ 5 \end{array}} \right)+2n\left( {\begin{array}{*{20}{c}} n \\ 4 \end{array}} \right)+\left( {{{n}^{2}}-n} \right)\left( {\begin{array}{*{20}{c}} n \\ 3 \end{array}} \right)\)

Solusi.   Anggap terdapat \(2n\) orang dalam suatu grup yang terdiri dari \(n\) laki-laki dan \(n\) perempuan dan kita hendak memilih 5 orang perwakilan dari grup tersebut. Jelas bahwa banyaknya cara untuk memilih 5 perwakilan tersebut adalah

\(\left( {\begin{array}{*{20}{c}} {2n} \\ 5 \end{array}} \right)\).

Dilain sisi 5 perwakilan tersebut dapat terdiri dari  5 Laki Laki  (L),  atau 5 Perempuan (P), 4L 1P, 4P 1L,  3L 2P, 3P 2L. Sehingga banyaknya pemilihan dengan cara tersebut adalah

\(2\left( {\begin{array}{*{20}{c}} n \\ 5 \end{array}} \right)\left( {\begin{array}{*{20}{c}} n \\ 0 \end{array}} \right)+2\left( {\begin{array}{*{20}{c}} n \\ 4 \end{array}} \right)\left( {\begin{array}{*{20}{c}} n \\ 1 \end{array}} \right)+2\left( {\begin{array}{*{20}{c}} n \\ 3 \end{array}} \right)\left( {\begin{array}{*{20}{c}} n \\ 2 \end{array}} \right)\)

jika disederhanakan menjadi

\(2\left( {\begin{array}{*{20}{c}} n \\ 5 \end{array}} \right)+2n\left( {\begin{array}{*{20}{c}} n \\ 4 \end{array}} \right)+\left( {{{n}^{2}}-n} \right)\left( {\begin{array}{*{20}{c}} n \\ 3 \end{array}} \right)\)