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 $\left(\genfrac{}{}{0ex}{}{2n}{2}\right)=2\left(\genfrac{}{}{0ex}{}{n}{2}\right)+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 \left(\genfrac{}{}{0ex}{}{a+b-2}{a-1}\right).$