Naskah Soal ONMIPA PT 2016 — Kombinatorika

Sepotong kawat berukuran 1 meter dipotong secara acak menjadi tiga bagian. Besarnya peluang ketiga bagian ini membentuk sebuah segitiga adalah $\dots$

Sebuah palindrome adalah sebuah barisan berhingga karakter sehingga dapat dibaca dengan cara yang sama baik dari kiri maupun kanan. SIKAPAKIS adalah sebuah contoh palindrome. Banyaknya bilangan palindrome yang terdiri atas 7 digit sedemikian sehingga tidak terdapat digit yang muncul lebih dari dua kali adalah $\dots$

Dari himpunan 26 huruf $A=\{a,b,c,\dots,y,z\}$ dibentuk sebuah susunan enam huruf berbeda (susunan tak perlu bermakna) sedemikian sehingga huruf pertama dan huruf terakhir adalah huruf vokal dan sisanya adalah huruf konsonan. Jika huruf $b$ selalu muncul pada susunan dan berdampingan dengan huruf $c$, maka banyaknya susunan yang mungkin adalah $\dots$

Banyaknya cara memfaktorkan bilangan 441.000 menjadi dua faktor positif $m$ dan $n$ yang saling relatif prima adalah $\dots$

Banyaknya bilangan antara 1 dan 500 yang tidak habis dibagi oleh 3, 4, dan 6 adalah $\dots$

Banyaknya graf sederhana berlabel atas $n$ titik yang memiliki sedikitnya dua sisi adalah $\dots$

Didefinisikan suatu fungsi rekursif, $\forall n\in\mathbb{Z}$ berlaku $f(1) = 1, f(2) = 5$, dan $f(n + 1) = f(n) + 2f(n - 1), \forall n > 2$. Maka $f(n) = \dots$

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

Perlihatkan bahwa untuk setiap himpunan yang terdiri dari 7 bilangan bulat berbeda maka terdapat dua bilangan $x$ dan $y$ pada himpunan tersebut sedemikian sehingga $x + y$ atau $x - y$ adalah kelipatan 10.

Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan $\binom{2n}{2} = 2\binom{n}{2} + n^2$ di mana $n\ge 2$.

Diberikan sebarang bilangan bulat positif $a$ dan $b$, bilangan $r(a,b) = t$ adalah suatu bilangan bulat positif terkecil sedemikian sehingga setiap pewarnaan merah-biru pada semua sisi dari graf lengkap dengan $t$ titik, senantiasa akan memuat subgraf lengkap $a$ titik dengan semua sisi berwarna merah atau memuat subgraf lengkap $b$ titik dengan semua sisi berwarna biru. Jika bilangan $t$ ada dan $a,b\ge 2$, buktikan bahwa $r(a - 1, b) + r(a, b - 1) \le \binom{a + b - 2}{a - 1}.$