Naskah Soal ONMIPA PT 2017 — Kombinatorika

Pada sebuah pesta pernikahan terdapat enam orang (termasuk pengantin) yang hendak berfoto. Banyak cara menata pose foto dalam satu baris dari keenam orang tersebut sedemikian sehingga pengantin berdiri tidak saling berdekatan adalah $\dots$

Sebuah rangkaian digit biner adalah sebuah barisan yang terdiri dari 0 dan 1. Banyaknya rangkaian digit biner yang terdiri atas tepat delapan digit 0 dan tepat sepuluh digit 1 sedemikian sehingga setiap kemunculan digit 0 segera diikuti oleh digit 1 adalah $\dots$

Pada sebuah lemari terdapat 25 helai baju yang terdiri atas 4 ukuran: 5 helai baju ukuran S, 4 helai baju ukuran M, 9 helai baju ukuran L, dan 7 helai baju ukuran XL. Untuk menjamin telah terambil 7 helai baju berukuran sama, maka sedikitnya total helai baju yang harus diambil dari lemari adalah $\dots$

Sebuah keluarga besar beranggotakan 14 orang anak yang terdiri dari dua kelahiran kembar tiga identik, tiga kelahiran kembar dua identik, dan dua anak yang lain. Bila kembar identik tak dapat dibedakan, maka banyaknya pose foto berdiri dalam satu baris dari 14 orang anak tersebut adalah $\dots$

Solusi dari relasi rekurensi $a_n=2a_{n-1}+3a_{n-2}$ dengan $a_0=1$ dan $a_1=2$ adalah $\dots$

Banyak cara menugaskan 5 pekerjaan berbeda ke 4 orang pegawai berbeda sedemikian sehingga setiap pegawai ditugaskan ke paling sedikit satu pekerjaan adalah $\dots$

Dalam bentuk paling sederhana fungsi pembangkit biasa (ordinary generating function), $g(x)$, dari barisan $(0,1,0,1,0,1,\dots )$ adalah $\dots$

Tentukan semua solusi $(a,b,c)$ dari persamaan Diophantine $2^a+5^b=c^2$.

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 berurutan sehingga terdapat tepat 24 latih tanding dalam periode waktu tersebut.

Diberikan bilangan bulat $n\ge 5$. Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan bahwa $\left(\genfrac{}{}{0ex}{}{2n}{5}\right)=2\left(\genfrac{}{}{0ex}{}{n}{5}\right)+2n\left(\genfrac{}{}{0ex}{}{n}{4}\right)+(n^2-n)\left(\genfrac{}{}{0ex}{}{n}{3}\right).$

Suatu sisi $e$ di graf $G$ dikatakan suatu cut edge jika jumlah komponen dari $G\setminus e$ lebih dari jumlah komponen dari $G$. Buktikan bahwa suatu sisi $e$ adalah cut edge di $G$ jika dan hanya jika $e$ tidak termuat di setiap lingkaran di $G$.