Naskah Soal ONMIPA PT 2015 — Kombinatorika

Pada babak final sebuah turnamen, tim pemenang adalah tim yang pertama sekali memenangkan dua pertandingan secara berurutan atau tim yang pertama kali memenangkan empat pertandingan. Banyaknya cara turnamen dapat terjadi adalah $\dots$

Banyaknya cara mengisi persegi panjang berukuran $2\times 16$ dengan persegi panjang yang berukuran $2\times 2, 2\times 3, 2\times 4$ adalah $\dots$

Enam komite akan dibentuk dari 14 orang. Bila 2 komite dari 6 komite ini terdiri atas tiga orang dan sisanya terdiri atas masing-masing 2 orang, maka banyaknya komite yang dapat dibentuk adalah $\dots$

Sebuah password terdiri atas 7 huruf dibentuk dengan menggunakan huruf kapital. Sebuah password dikatakan legal bila memenuhi dua kondisi: (i) tidak terdapat huruf berulang, (ii) huruf X dan Y tidak saling berdekatan. Besarnya peluang untuk membentuk password legal adalah $\dots$

Diberikan sebuah barisan $(x_n)$ dengan suku ke-$n$ adalah $\displaystyle x_n = \frac{1}{\sqrt 5}(a^n - b^n)$ di mana $a = \dfrac{1 + \sqrt 5}{2}$ dan $b = \dfrac{1 - \sqrt 5}{2}$. Relasi rekursif yang memenuhi barisan $(x_n)$ adalah $\dots$

Lima buah dadu (enam sisi) digulirkan. Peluang bahwa mata dadu yang muncul berjumlah 14 adalah $\dots$

Setiap bujursangkar pada persegi panjang berukuran $1\times n$ diwarnai dengan menggunakan satu dari tiga warna merah, putih, atau biru. Banyak cara mewarnai $1\times n$ dengan merah, putih, atau biru sehingga terdapat genap buah bujursangkar berwarna putih adalah $\dots$

Untuk setiap bilangan asli $n\in\mathbb{N}$ dengan $n \ge 2$, nilai dari $\frac{1}{n}\binom{n}{1} + \frac{2}{n}\binom{n}{2} + \frac{3}{n}\binom{n}{3} + \dots + \frac{n - 1}{n}\binom{n}{n - 1}$ adalah $\dots$

Suatu graf $\Lambda$ disebut komplemen dari graf $\Gamma$ jika $V(\Lambda) = V(\Gamma)$ dan sisi $e = (u,v)\in E(\Lambda)$ jika dan hanya jika sisi $e = (u,v)\notin E(\Gamma)$. Komplemen dari graf $\Gamma$ ditulis $\overline{\Gamma}$. Tentukan bilangan bulat positif terkecil $N$ sedemikian sehingga untuk setiap sebarang graf $\Gamma$ dengan $N$ titik senantiasa memuat graf lengkap $K_3$ sebagai subgraf atau graf $\overline{\Gamma}$ memuat graf lengkap $K_3$ sebagai subgraf. Kemudian buktikan!

Sebuah papan catur $C$ terdiri dari $i$ baris dan $j$ lajur. Misalkan $b$ menyatakan banyaknya maksimal benteng yang dapat diletakkan pada $C$ sehingga tidak ada dua benteng yang saling menyerang. Tentukan banyaknya cara meletakkan $b$ buah benteng pada $C$ sedemikian sehingga tidak ada dua benteng yang saling menyerang.

Misalkan $n$ adalah sebuah bilangan bulat positif. Buktikan bahwa $\sum_{k = 1}^n \frac{(-1)^{k - 1}}{k}\binom{n}{k} = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}.$