Soal dan Pembahasan - ONMIPA Matematika
ONMIPA merupakan sebuah kompetisi di tingkat perguruan tinggi yang terdiri dari empat bidang, yaitu Matematika, Fisika, Kimia, dan Biologi. Ada tiga tahapan seleksi pada ONMIPA, mulai dari seleksi tingkat universitas, tingkat wilayah, sampai tingkat nasional.
ONMIPA Matematika mencakup lima bidang, yaitu kombinatorika, aljabar linear, struktur aljabar, analisis real, dan analisis kompleks. Berikut ini kami sajikan pembahasan soal ONMIPA Matematika, sebagai referensi bagi teman-teman yang ingin mempersiapkan diri. Selamat Belajar!
Pembahasan Soal Aljabar Linear
(2016 Wilayah) Jika $$u=\begin{bmatrix}1&-1&2\end{bmatrix},\;A=\begin{bmatrix}3&2\\1&3\\0&1\end{bmatrix}, \; \text{dan }v=\begin{bmatrix}2&-1\end{bmatrix}$$ maka $uAv^t=\ldots$
Dengan mengalikan matriks $u$, $A$, dan $v^t$ diperoleh $$\begin{aligned} uAv^t &= \begin{bmatrix}1&-1&2\end{bmatrix} \begin{bmatrix}3&2\\1&3\\0&1\end{bmatrix} \begin{bmatrix}2\\-1\end{bmatrix} \\ &= \begin{bmatrix}2&1\end{bmatrix} \begin{bmatrix}2\\-1\end{bmatrix} \\ &= \begin{bmatrix} 3 \end{bmatrix} \end{aligned}$$
(2016 Wilayah) Misalkan $A=\begin{bmatrix}1&-1\\-4&-2\end{bmatrix}$, maka $A^{2016}=\ldots$
Pertama, akan diperiksa apakah $A$ dapat didiagonalkan. Polinomial karakteristik dari matriks $A$ adalah $$\begin{aligned} \text{det}(A-\lambda I) &= \left|\begin{matrix}1-\lambda&-1\\-4&-2-\lambda\end{matrix}\right| \\[3pt] &= (1-\lambda)(-2-\lambda)-(-4) (-1) \\[3pt] &= -2-\lambda+2\lambda+\lambda^2-4 \\[3pt] &= \lambda^2+\lambda-6 \\[3pt] &= (\lambda-2)(\lambda+3) \end{aligned}$$ sehingga persamaan karakteristiknya $$(\lambda-2)\;(\lambda+3)=0$$
Solusi dari persamaan ini merupakan nilai eigen matriks $A$, yaitu $\lambda = 2$ dan $\lambda = -3$. Karena $A$ mempunyai dua nilai eigen (sesuai dengan ordo matriks $A$), maka matriks $A$ dapat didagonalkan.
Melalui prosedur diagnoalisasi matriks, diperoleh $D=P^{-1}AP$ dengan $$D=\begin{bmatrix}2&0\\0&-3\end{bmatrix} ,\quad P=\begin{bmatrix}-1&1\\1&4\end{bmatrix} ,\quad P^{-1}=\frac{1}{5}\begin{bmatrix}-4&1\\1&1\end{bmatrix}$$
Perhatikan bahwa $$\begin{aligned} P^{-1}AP &= D \\[3pt] (P^{-1}AP)^{2016} &= D^{2016} \\[3pt] P^{-1}A^{2016}P &= D^{2016} \\[3pt] A^{2016} &= PD^{2016}P^{-1} \end{aligned}$$
Akibatnya $$\begin{aligned} A^{2016} &= PD^{2016}P^{-1} \\[3pt] &= \begin{bmatrix}-1&1\\1&4\end{bmatrix} \cdot \begin{bmatrix}2^{2016}&0\\0&3^{2016}\end{bmatrix} \cdot \frac{1}{5}\begin{bmatrix}-4&1\\1&1\end{bmatrix} \\[3pt] &= \begin{bmatrix} -2^{2016}&3^{2016}\\2^{2016}&4\cdot3^{2016} \end{bmatrix} \cdot \frac{1}{5}\begin{bmatrix}-4&1\\1&1\end{bmatrix} \\[3pt] &= \frac{1}{5}\begin{bmatrix} 4\cdot 2^{2016}+3^{2016}&3^{2016}-2^{2016}\\4\cdot 3^{2016}-4\cdot 2^{2016}&2^{2016}+4\cdot 3^{2016} \end{bmatrix} \end{aligned}$$
(2016 Wilayah) Diberikan sistem persamaan linier $$\begin{alignat*}{3} x & \:+\: &y & \:+\: &z & \:=\: &1 \\ x & \:+\: &ay & \:+\: &2z & \:=\: &-1 \\ x & \:+\: &a^2y & \:+\: &4z & \:=\: &2 \\ 2x & \:+\: &(a+1)y & \:+\: &3z & \:=\: &0 \end{alignat*}$$ Nilai-nilai $a$ yang membuat sistem persamaan linier tersebut mempunyai solusi tunggal adalah $\ldots$
Matriks yang diperbesar dari sistem persamaan tersebut adalah $$\begin{bmatrix} 1&1&1&1\\ 1&a&2&-1\\ 1&a^2&4&2\\ 2&a+1&3&0 \end{bmatrix}$$
Matriks di atas akan diubah ke dalam bentuk eselon baris. Tambahkan $-1 \times R_1$ pada baris kedua dan ketiga, serta $-2 \times R_1$ pada baris keempat. $$\begin{bmatrix} 1&1&1&1\\ 0&a-1&1&-2\\ 0&a^2-1&3&1\\ 0&a-1&1&-2 \end{bmatrix}$$
Berikutnya, tambahkan $-(a+1) \times R_2$ pada $R_3$ dan $-1 \times R_2$ pada $R_4$. $$\begin{bmatrix} 1&1&1&1\\ 0&a-1&1&-2\\ 0&0&-a+2&2a+3\\ 0&0&0&0 \end{bmatrix}$$
Pada baris ketiga diperoleh $(-a+2)z = 2a+3$. Solusi tunggal terjadi ketika $-a+2 \neq 0$. Dengan demikian, nilai-nilai $a$ yang membuat sistem tersebut mempunyai solusi tunggal adalah semua bilangan real selain $2$.
(2016 Wilayah) Terhadap basis $\{1+x,x+x^2,1+x^2\}$, matriks representasi transformasi linier $T:P_2 \to P_2$ adalah $$\begin{bmatrix}-1&0&1\\-2&1&0\\1&-1&1\end{bmatrix}$$ Maka $T(x-x^2)=\ldots$
Misalkan $u=x-x^2$ dan $B=\{1+x,x+x^2,1+x^2\}$. Pertama, kita akan menentukan koordinat vektor $u$ terhadap basis $B$, yaitu $[u]_B$. Misalkan $$[u]_B=\begin{bmatrix}k_1\\k_2\\k_3\end{bmatrix}$$ sehingga $$\begin{aligned} u &= k_1(1+x)+k_2(x+x^2)+k_3(1+x^2) \\ x-x^2 &= (k_1+k_3)+(k_1+k_2)x+(k_2+k_3)x^2 \end{aligned}$$
Berdasarkan kesamaan dua polinom, diperoleh sistem persamaan $$\left\{\begin{aligned}k_1+k_3&=0\\k_1+k_2&=1\\k_2+k_3&=-1\end{aligned}\right.$$
Solusi dari sistem tersebut adalah $k_1=1$, $k_2=0$, dan $k_3=-1$. Berikutnya, kita akan menentukan koordinat $T(u)$ terhadap basis $B$, yaitu $$\begin{aligned} \begin{bmatrix}T(u)\end{bmatrix}_B &= \begin{bmatrix}-1&0&1\\-2&1&0\\1&-1&1\end{bmatrix} [u]_B \\[3pt] &= \begin{bmatrix}-1&0&1\\-2&1&0\\1&-1&1\end{bmatrix} \begin{bmatrix}1\\0\\-1\end{bmatrix} \\[3pt] &= \begin{bmatrix}-2\\-2\\0\end{bmatrix} \end{aligned}$$
Dengan demikian $$\begin{aligned} T(x-x^2) &= -2(1+x)-2(x+x^2)+0(1+x^2) \\ &= -2-2x-2x-2x^2 \\ &= -2-4x-2x^2 \end{aligned}$$
(2016 Wilayah) Pemetaan linier $T:P_2 \to \mathbb R^2$ memenuhi $$T(1+x)=\begin{bmatrix}2\\-1\end{bmatrix},\;T(x+x^2)=\begin{bmatrix}2\\0\end{bmatrix},\; \text{dan } T(1+x^2)=\begin{bmatrix}2\\1\end{bmatrix}$$ Salah satu basis $\text{Inti}(T)$ adalah $\ldots$
Diambil sebarang $p \in \text{Inti}(T)$. Karena $\{1+x,x+x^2,1+x^2\}$ merupakan basis dari $P_2$ (periksa!), maka $p$ dapat dinyatakan sebagai kombinasi linear dari vektor-vektor tersebut. Misalkan $$p=a(1+x)+b(x+x^2)+c(1+x^2)$$
Sehingga $$\begin{aligned} T(p) &= T(a(1+x)+b(x+x^2)+c(1+x^2)) \\[3pt] 0_{\mathbb R^2} &= aT(1+x)+bT(x+x^2)+cT(1+x^2) \\[3pt] \begin{bmatrix}0\\0\end{bmatrix} &= a\begin{bmatrix}2\\-1\end{bmatrix}+b\begin{bmatrix}2\\0\end{bmatrix}+c\begin{bmatrix}2\\1\end{bmatrix} \\[3pt] \begin{bmatrix}0\\0\end{bmatrix} &= \begin{bmatrix}2a+2b+2c\\-a+c\end{bmatrix} \\ \end{aligned}$$
Berdasarkan kesamaan dua vektor diperoleh sistem persamaan $$\left\{\begin{aligned}2a+2b+2c&=0\\-a+c &= 0\end{aligned}\right.$$
Sistem persamaan tersebut mempunyai solusi $a=t$, $b=-2t$, $c=t$ untuk sebarang bilangan real $t$. Akibatnya $$\begin{aligned} p &= a(1+x)+b(x+x^2)+c(1+x^2) \\ &= t(1+x)-2t(x+x^2)+t(1+x^2) \\ &= t(2-x-x^2) \end{aligned}$$
Dari hasil di atas, terlihat bahwa $\text{Inti}(T)$ dibangun oleh $\{2-x-x^2\}$. Himpunan ini jelas bebas linear, sehingga merupakan basis dari $\text{Inti}(T)$.
(2016 Wilayah) Diketahui $\begin{bmatrix}-3\\1\end{bmatrix}$ adalah vektor eigen matriks $A=\begin{bmatrix}1&a\\1&2\end{bmatrix}$ untuk nilai eigen $\lambda$. Maka nilai eigen $A$ selain $\lambda$ adalah $\ldots$
Jika $x$ adalah vektor eigen matriks $A$ untuk nilai eigen $\lambda$ maka berlaku $Ax=\lambda x$. Akibatnya $$\begin{aligned} \begin{bmatrix}1&a\\1&2\end{bmatrix}\begin{bmatrix}-3\\1\end{bmatrix} &= \lambda \begin{bmatrix}-3\\1\end{bmatrix} \\[3pt] \begin{bmatrix}-3+a\\-1\end{bmatrix} &= \begin{bmatrix}-3\lambda\\\lambda\end{bmatrix} \end{aligned}$$
Diperoleh dua persamaan yaitu $\lambda=-1$ dan $-3+a=-3\lambda$. Substitusi nilai $\lambda = -1$ pada persamaan kedua sehingga diperoleh $$-3+a=3 \quad \Longrightarrow \quad a=6$$
Dengan ini, entri-entri matriks $a$ sudah lengkap. Berikutnya, kita akan menentukan nilai eigen matriks $A$. Polinomial karakteristik matriks $A$ adalah $$\begin{aligned} \text{det}(A-\lambda I) &= \begin{vmatrix} 1-\lambda&6\\1&2-\lambda \end{vmatrix} \\[3pt] &= (1-\lambda)(2-\lambda)-1\cdot 6 \\[3pt] &= \lambda^2-3\lambda+2-6 \\[3pt] &= \lambda^2-3\lambda-4 \\[3pt] &= (\lambda-4)(\lambda+1) \end{aligned}$$
Sehingga persamaan karakteristiknya adalah $(\lambda-4)(\lambda+1)=0$. Dengan demikian, nilai eigen matriks $A$ selain $-1$ adalah $4$.
(2016 Wilayah) Komponen baris ke-$i$ kolom ke-$j$ matriks $A$ yang berukuran $n \times n$ adalah $1$ jika $i+j$ ganjil dan $0$ jika $i+j$ genap. Jika $n$ ganjil, multiplisitas aljabar $0$ sebagai nilai eigen $A$ adalah $\ldots$
Berdasarkan syarat yang diberikan diberikan, diperoleh $$A=\begin{bmatrix} 0&1&0&\ldots&1&0 \\ 1&0&1&\ldots&0&1 \\ 0&1&0&\ldots&1&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 1&0&1&\ldots&0&1 \\ 0&1&0&\ldots&1&0 \end{bmatrix}$$
Polinomisl karakteristik matriks $A$ adalah $$\begin{aligned} \text{det}(A-\lambda I) &= \begin{vmatrix} -\lambda&1&0&\ldots&1&0 \\ 1&-\lambda&1&\ldots&0&1 \\ 0&1&-\lambda&\ldots&1&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 1&0&1&\ldots&-\lambda&1 \\ 0&1&0&\ldots&1&-\lambda \end{vmatrix} \end{aligned}$$
Untuk $i$ ganjil selain $1$, tambahkan $-R_1$ pada $R_i$. Sedangkan untuk $i$ genap selain $2$, tambahkan $-R_2$ pada $R_i$. Operasi baris elementer ini tidak mengubah nilai determinan, sehingga $$\begin{aligned} \text{det}(A-\lambda I) &= \begin{vmatrix} -\lambda&1&0&\ldots&1&0 \\ 1&-\lambda&1&\ldots&0&1 \\ \lambda&0&-\lambda&\ldots&0&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&\lambda&0&\ldots&-\lambda&0 \\ \lambda&0&0&\ldots&0&-\lambda \end{vmatrix} \\[3pt] &= \lambda^{n-2} \begin{vmatrix} -\lambda&1&0&\ldots&1&0 \\ 1&-\lambda&1&\ldots&0&1 \\ 1&0&-1&\ldots&0&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&1&0&\ldots&-1&0 \\ 1&0&0&\ldots&0&-1 \end{vmatrix} \end{aligned}$$
Karena $n$ ganjil, maka selain baris pertama sebanyak $\textcolor{red}{\frac{n+1}{2}-1}$ baris ganjil dan selain baris kedua terdapat sebanyak $\textcolor{blue}{\frac{n-1}{2}-1}$ baris genap.
Untuk $i$ ganjil selain $1$, tambahkan $R_i$ pada $R_2$. Sedangkan untuk $i$ genap selain $2$, tambahkan $R_i$ pada $R_1$. Akibatnya $$\begin{aligned} \text{det}(A-\lambda I) &= \lambda^{n-2} \begin{vmatrix} -\lambda&\textcolor{blue}{\frac{n-1}{2}}&0&\ldots&0&0 \\ \textcolor{red}{\frac{n+1}{2}}&-\lambda&0&\ldots&0&0 \\ 1&0&-1&\ldots&0&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&1&0&\ldots&-1&0 \\ 1&0&0&\ldots&0&-1 \end{vmatrix} \end{aligned}$$
Dengan ekspansi kofaktor sepanjang kolom terakhir (sebanyak $n-2$ kali) diperoleh $$\begin{aligned} \text{det}(A-\lambda I) &= \lambda^{n-2} (-1)^{n-2} \begin{vmatrix} -\lambda&\textcolor{blue}{\frac{n-1}{2}} \\\textcolor{red}{\frac{n+1}{2}}&-\lambda \end{vmatrix} \\[3pt] &= -\lambda^{n-2} \left( \lambda^2-\frac{n+1}{2} \cdot \frac{n-1}{2} \right) \end{aligned}$$
Karena $\lambda$ muncul sebagai faktor sebanyak $n-2$ kali, maka multiplisitas aljabar dari $0$ adalah $n-2$.
(2016 Wilayah) Diberikan matriks $A$ ukuran $n \times n$, dengan entri-entri $$a_{ij} = \binom{x_i+j}{j-1}$$
Hitunglah determinan $A_n$, jika didefinisikan $$\binom{x}{n}=\frac{x(x-1)(x-2)\cdots(x-n+1)}{n!}$$ untuk setiap bilangan riil $x$ dan bilangan asli $n$ dengan ketentuan $$\binom{x}{0}=1$$
Berdasarkan ketentuan dalam soal, diperoleh $$\begin{aligned} \text{det}(A) &= \begin{vmatrix} \binom{x_1+1}{0}&\binom{x_1+2}{1}&\binom{x_1+3}{2}&\ldots&\binom{x_1+n}{n-1} \\ \binom{x_2+1}{0}&\binom{x_2+2}{1}&\binom{x_2+3}{2}&\ldots&\binom{x_2+n}{n-1} \\ \binom{x_3+1}{0}&\binom{x_3+2}{1}&\binom{x_3+3}{2}&\ldots&\binom{x_3+n}{n-1} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ \binom{x_n+1}{0}&\binom{x_n+2}{1}&\binom{x_n+3}{2}&\ldots&\binom{x_n+n}{n-1} \end{vmatrix} \\[4pt] &= \begin{vmatrix} 1 & x_1+2 & \frac{(x_1+3)(x_1+2)}{2!} & \ldots & \frac{(x_1-n+1)(x_1-n) \ldots (x_1+2)}{(n-1)!} \\ 1 & x_2+2 & \frac{(x_2+3)(x_2+2)}{2!} & \ldots & \frac{(x_2-n+1)(x_2-n) \ldots (x_2+2)}{(n-1)!} \\ 1 & x_3+2 & \frac{(x_3+3)(x_3+2)}{2!} & \ldots & \frac{(x_3-n+1)(x_3-n) \ldots (x_3+2)}{(n-1)!} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 1 & x_n+2 & \frac{(x_n+3)(x_n+2)}{2!} & \ldots & \frac{(x_n-n+1)(x_n-n) \ldots (x_n+2)}{(n-1)!} \end{vmatrix} \end{aligned}$$
Tambahkan $-2 \times C_1$ pada $C_2$ sehingga $$\text{det}(A) = \begin{vmatrix} 1 & x_1 & \frac{(x_1+3)(x_1+2)}{2!} & \ldots & \frac{(x_1-n+1)(x_1-n) \ldots (x_1+2)}{(n-1)!} \\ 1 & x_2 & \frac{(x_2+3)(x_2+2)}{2!} & \ldots & \frac{(x_2-n+1)(x_2-n) \ldots (x_2+2)}{(n-1)!} \\ 1 & x_3 & \frac{(x_3+3)(x_3+2)}{2!} & \ldots & \frac{(x_3-n+1)(x_3-n) \ldots (x_3+2)}{(n-1)!} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 1 & x_n & \frac{(x_n+3)(x_n+2)}{2!} & \ldots & \frac{(x_n-n+1)(x_n-n) \ldots (x_n+2)}{(n-1)!} \end{vmatrix}$$
Entri-entri pada kolom ke-$3$ merupakan polinom berderajat $2$. Dengan memanfaatkan kolom sebelumnya, kita dapat mengubah kolom ini sehingga hanya memuat suku dengan pangkat tertinggi. Berikut ilustrasi untuk prosedur pada kolom ketiga, yang juga dapat diterapkan pada kolom-kolom berikutnya.
Jika diuraikan, maka entri-entri pada kolom ketiga berbentuk $\frac{x_n^2}{2!} + ax_n + b$ untuk suatu nilai $a$ dan $b$ yang sesuai. Tambakan $-b \times C_1$ pada $C_3$ sehingga diperoleh entri $\frac{x_n^2}{2!} + ax_n$. Lalu tambahkan $-a \times C_2$ pada $C_3$, sehingga entri ini menjadi $\frac{x_n^2}{2!}$. Akibatnya $$\begin{aligned} \text{det}(A) &= \begin{vmatrix} 1 & x_1 & \frac{x_1^2}{2!} & \ldots & \frac{(x_1-n+1)(x_1-n) \ldots (x_1+2)}{(n-1)!} \\ 1 & x_2 & \frac{x_2^2}{2!} & \ldots & \frac{(x_2-n+1)(x_2-n) \ldots (x_2+2)}{(n-1)!} \\ 1 & x_3 & \frac{x_3^2}{2!} & \ldots & \frac{(x_3-n+1)(x_3-n) \ldots (x_3+2)}{(n-1)!} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 1 & x_n & \frac{x_n^2}{2!} & \ldots & \frac{(x_n-n+1)(x_n-n) \ldots (x_n+2)}{(n-1)!} \end{vmatrix} \\[4pt] &= \frac{1}{2!} \cdot \begin{vmatrix} 1 & x_1 & x_1^2 & \ldots & \frac{(x_1-n+1)(x_1-n) \ldots (x_1+2)}{(n-1)!} \\ 1 & x_2 & x_2^2 & \ldots & \frac{(x_2-n+1)(x_2-n) \ldots (x_2+2)}{(n-1)!} \\ 1 & x_3 & x_3^2 & \ldots & \frac{(x_3-n+1)(x_3-n) \ldots (x_3+2)}{(n-1)!} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 1 & x_n & x_n^2 & \ldots & \frac{(x_n-n+1)(x_n-n) \ldots (x_n+2)}{(n-1)!} \end{vmatrix} \end{aligned}$$
Ulangi prosedur di atas untuk kolom-kolom berikutnya, sehingga diperoleh $$\begin{aligned} \text{det}(A) &= \frac{1}{2!3! \cdots (n-1)!} \cdot \begin{vmatrix} 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \ldots & x_2^{n-1} \\ 1 & x_3 & x_3^2 & \ldots & x_3^{n-1} \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 1 & x_n & x_n^2 & \ldots & x_n^{n-1} \end{vmatrix} \\[4pt] &= \frac{1}{2!3! \cdots (n-1)!} \cdot \text{det}(B) \end{aligned}$$
Matriks $B$ ini disebut Matriks Vandermonde, dengan nilai determinan $$\text{det}(B) = \prod_{1 \leq i < j \leq n} (x_j-x_1)$$
Dengan demikian $$\text{det}(A) = \frac{1}{2!3! \cdots (n-1)!} \times \prod_{1 \leq i < j \leq n} (x_j-x_1)$$
(2016 Wilayah) Di $\mathbb R^{2 \times 2}$ didefinisikan hasil kali dalam $\langle A,B \rangle =\text{tr}(B^tA)$. Jika $$W=\text{span}\left\{ \begin{bmatrix}1&0\\0&1\end{bmatrix},\begin{bmatrix}0&-1\\1&0\end{bmatrix} \right\}$$ tentukan $W^{\perp}$, yaitu komplemen ortogonal dari $W$.
Diambil sebarang $M \in W^{\perp}$, dengan $$M=\begin{bmatrix}a&b\\c&d\end{bmatrix}, \; \text{untuk suatu }a,b,c,d \in \mathbb R$$
Berdasarkan definisi, matriks $M$ ortogonal dengan setiap anggota $W$, termasuk kedua matriks yang membangun $W$. Perhatikan bahwa $$\begin{aligned} \left \langle \begin{bmatrix}a&b\\c&d\end{bmatrix},\begin{bmatrix}1&0\\0&1\end{bmatrix} \right \rangle &= \text{tr}\left( \begin{bmatrix}1&0\\0&1\end{bmatrix}^t \begin{bmatrix}a&b\\c&d\end{bmatrix} \right) \\[3pt] &= \text{tr}\left( \begin{bmatrix}1&0\\0&1\end{bmatrix} \begin{bmatrix}a&b\\c&d\end{bmatrix} \right) \\[3pt] &= \text{tr}\left( \begin{bmatrix}a&b\\c&d\end{bmatrix} \right) \\[3pt] &= a+d \end{aligned}$$ dan $$\begin{aligned} \left \langle \begin{bmatrix}a&b\\c&d\end{bmatrix},\begin{bmatrix}0&-1\\1&0\end{bmatrix} \right \rangle &= \text{tr}\left( \begin{bmatrix}0&-1\\1&0\end{bmatrix}^t \begin{bmatrix}a&b\\c&d\end{bmatrix} \right) \\[3pt] &= \text{tr}\left( \begin{bmatrix}0&1\\-1&0\end{bmatrix} \begin{bmatrix}a&b\\c&d\end{bmatrix} \right) \\[3pt] &= \text{tr}\left( \begin{bmatrix}c&d\\-a&-b\end{bmatrix} \right) \\[3pt] &= c-b \end{aligned}$$
Karena matriks tersebut ortogonal, maka $$\begin{aligned} a+d = 0 \quad &\Longrightarrow \quad d=-a \\ c-b=0 \quad &\Longrightarrow \quad c=b \end{aligned}$$
Akibatnya $$\begin{aligned} M &= \begin{bmatrix} a&b\\c&d \end{bmatrix} \\[3pt] &= \begin{bmatrix} a&b\\b&-a \end{bmatrix} \\[3pt] &= \begin{bmatrix} a&0\\0&-a \end{bmatrix} + \begin{bmatrix} 0&b\\b&0 \end{bmatrix} \\[3pt] &= a\begin{bmatrix} 1&0\\0&-1 \end{bmatrix} + b\begin{bmatrix} 0&1\\1&0 \end{bmatrix} \end{aligned}$$
Dengan demikian $$W^{\perp} = \text{span}\left\{ \begin{bmatrix} 1&0\\0&-1 \end{bmatrix},\begin{bmatrix} 0&1\\1&0 \end{bmatrix} \right\}$$
(2017 Wilayah) 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 tidak saling berdekatan adalah $\ldots$
Dalam menata pose foto keenam orang tersebut, terdapat dua kemungkinan, yaitu (1) pengantin berdekatan dan (2) pengantin berdiri tidak saling berdekatan. Untuk menghitung banyak cara menata pose foto untuk kemungkinan kedua, kita dapat menghitung banyak cara keseluruhan, lalu menguranginya dengan banyak cara pada kemungkinan pertama.
Banyak cara keseluruhan adalah $6!$. Untuk kemungkinan pertama, anggap pengantin sebagai sebuah objek, sehingga kita perlu menata $5$ objek dengan cara sebanyak $5!$. Pengantin laki-laki dan perempuan dapat bertukar posisi, sehingga kita mengalikannya dengan $2!=2$. Jadi, banyak cara untuk kemungkinan pertama adalah $2 \cdot 5!$.
Dengan demikian, banyak cara menata pose foto agar pengantin tidak saling berdekatan adalah $$6!-2 \cdot 5! = 480!$$
(2017 Wilayah) Sebuah rangkaian digit biner adalah sebuah barisan yang terdiri dari $1$ dan $0$. 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 $\ldots$
Pertama, tentukan susunan delapan digit $0$ dan delapan digit $1$, sesuai syarat yang diberikan. $$01 \;\; 01 \;\; 01 \;\; 01 \;\; 01 \;\; 01 \;\; 01 \;\; 01$$
Dengan ini, tersisa dua digit $1$. Kedua digit ini bisa ditempatkan pada ujung kiri, tengah, atau ujung kanan. Banyak tempat yang tersedia adalah $9$. $$\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}01\underline{}\underline{}$$
Digit $1$ pertama dapat menempati $9$ tempat, begitupun dengan digit $1$ kedua. Dengan demikian, banyaknya rangkaian digit biner dengan syarat yang diberikan adalah $9 \times 9 = 81$.
(2017 Wilayah) Pada sebuah lemari terdapat $25$ helai baju yang terdiri atas $4$ ukuran. Lima helai baju berukuran S, $4$ helai baju berukuran M, $9$ helai baju berukuran L, dan $7$ helai baju berukuran XL. Untuk menjamin telah terambil $7$ helai baju berukuran sama, maka sedikitnya total helai baju yang harus diambil dari lemari adalah $\ldots$
Dengan mengambil $7$ helai baju, ada kemungkinan terambil $7$ helai baju berukuran sama, misalnya XL. Namun bukan ini yang dimaksud, karena dari $7$ baju yang diambil, bisa jadi terdapat $3$ helai ukuran S dan $4$ helai ukuran $L$, atau kemungkinan lainnya.
Untuk menjawab pertanyaan ini, kita dapat menentukan banyak helai baju maksimal yang diambil sehingga belum terjamin terambil $7$ helai baju berukuran sama. Ini terjadi jika terambil sebanyak $$\begin{aligned} &5 \text{ helai ukuran S} \\ &4 \text{ helai ukuran M} \\ &6 \text{ helai ukuran L} \\ &6 \text{ helai ukuran XL} \end{aligned}$$ dengan total sebanyak $21$ helai baju. Dengan mengambil satu helai lagi, apapun ukuran yang terambil, pasti terdapat $7$ helai baju berukuran sama. Jadi, banyak helai baju minimal yang diambil adalah $21+1=22$ helai.
(2017 Wilayah) 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 banyak pose foto berdiri dalam satu baris dari $14$ orang anak tersebut adalah $\ldots$
Soal ini dapat diselesaikan menggunakan permutasi dengan unsur berulang. Banyak pose foto berdiri dalah satu baris adalah $$\frac{14!}{3!3!2!2!2!}$$
(2017 Wilayah) Solusi dari relasi rekurensi $a_n=2a_{n-1}+3a_{n-2}$ dengan $a_0=1$ dan $a_1=2$ adalah $\ldots$
Misalkan $a_n=Cr^n$ dengan $r \neq 0$, sehingga $$\begin{aligned} a_n &= 2a_{n-1}+3a_{n-2} \\ Cr^n &= 2Cr^{n-1}+3Cr^{n-2} r^2 &= 2r+3 \\ r^2-2r-3 &= 0 \\ (r-3)(r+1) &= 0 \end{aligned}$$
Diperoleh $r=3$ atau $r=-1$, sehingga $a_n=C_1 \cdot 3^n+C_2 \cdot(-1)^n$. Untuk $n=0$ diperoleh $$a_0=C_1 \cdot 3^0+C_2 \cdot(-1)^0 \quad \Longrightarrow \quad 1=C_1+C_2$$
Sedangkan untuk $n=1$ diperoleh $$a_1=C_1 \cdot 3^1+C_2 \cdot(-1)^1 \quad \Longrightarrow \quad 2=3C_1-C_2$$
Dengan menambahkan kedua persamaan, diperoleh $4C_1=3$ sehingga $C_1=3/4$. Substitusi nilai $C_1$ pada persamaan pertama, sehingga diperoleh $C_2=1/4$. Dengan demikian, solusi dari relasi rekurensi tersebut adalah $$a_n=\frac{3}{4} \cdot 3^n+\frac{1}{4} \cdot(-1)^n$$
(2017 Wilayah) Banyak cara menugaskan $5$ pekerjaan berbeda ke $4$ orang pegawai berbeda sedemikian sehingga setiap pegawai ditugaskan ke paling sedikit satu pekerjaan adalah $\ldots$
Kita akan menyelesaikan soal ini dengan fungsi pembangkit eksponensial. Fungsi pembangkitnya adalah $$\begin{aligned} f(x) &= \left( x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots \right)^4 \\ &= (e^x-1)^4 \\ &= e^{4x}-4e^{3x}+6e^{2x}-4e^x+1 \\ &= \sum_{i=0}^{\infty} \frac{(4x)^i}{i!}-4\sum_{i=0}^{\infty} \frac{(3x)^i}{i!}+6\sum_{i=0}^{\infty} \frac{(2x)^i}{i!}-4\sum_{i=0}^{\infty} \frac{x^i}{i!}+1 \\ &= \sum_{i=0}^{\infty} \left( 4^i-4 \cdot 3^i+6 \cdot 2^i-4 \right) \frac{x^i}{i!}+1 \end{aligned}$$
Banyak cara menugaskan pekerjaan sesuai syarat yang diberikan sama dengan koefisien $x^5/5!$ pada $f(x)$, yaitu $$4^5-4 \cdot 3^5+6 \cdot 2^5-4 = 240$$
(2017 Wilayah) Dalam bentuk yang paling sederhana fungsi pembangkit biasa (ordinary generating function), $g(x)$, dari barisan $(0,1,0,1,0,1,0,1,\ldots)$ adalah $\ldots$
Fungsi pembangkit biasa dari barisan $(0,1,0,1,0,1,0,1,\ldots)$ adalah $$\begin{aligned} g(x) &= x+x^3+x^5+\ldots \\[3pt] &= \frac{x}{1-x^2}, \;\; |x| < 1 \end{aligned}$$
(2017 Wilayah) Tentukan semua solusi $(a,b,c)$ dari persamaan diophantine $2^a+5^b=c^2$.
Persamaan tersebut tidak mempunyai solusi jika $a$ atau $b$ bernilai negatif. Jika $a$ ganjil maka digit satuan dari $2^a$ adalah $2$ atau $8$. Ditambah dengan $5$, diperoleh digit satuan $3$ atau $7$. Tidak ada bilangan kuadrat dengan digit satuan tersebut, sehingga dapat disimpulkan bahwa $a$ genap. Selain itu, untuk menyederhanakan masalah, kita misalkan $c$ tak negatif.
Misalkan $a=2n$ dengan $n$ bilangan bulat tak negatif. Persamaan semula menjadi $$\begin{aligned} 2^{2n}+5^b &= c^2 \\ c^2-2^{2n} &= 5^b \\ c^2-(2^n)^2 &= 5^b \\ (c-2^n)(c+2^n) &= 5^b \end{aligned}$$
Perhatikan bahwa kedua faktor pada ruas kiri berselisih $2 \times 2^n$. Karena $2 \times 2^n$ tidak habis dibagi $5$, maka kedua faktor ini tidak mungkin habis dibagi $5$ secara bersamaan (hanya salah satunya). Akibatnya $$c-2^n=1 \quad \text{dan} \quad c+2^n=5^b$$
Kurangkan kedua persamaan, sehingga diperoleh $$2^{n+1} = 5^b-1 \quad \Longrightarrow \quad 5^b-2^{n+1}=1$$
Konjektur Catalan
Untuk $x,y,a,b > 1$ persamaan $$x^a-y^b=1$$ hanya mempunyai satu solusi, yaitu $x=3$, $a=2$, $y=2$, dan $b=3$.
Berdasarkan Konjektur Catalan, persamaan $5^b-2^{n+1}=1$ tidak mempunyai solusi untuk $n+1 > 1$ dan $b > 1$. Dengan kata lain, persamaan tersebut mempunyai solusi jika $$n+1 \leq 1 \quad \text{atau} \quad b \leq 1$$
Nilai $b$ dan $n$ yang memenuhi adalah $b=1$ dan $n=1$. Dengan demikian, solusi $(a,b,c)$ dari persamaan semula adalah $$(2,1,-3) \quad \text{dan} \quad (2,1,3)$$
(2017 Wilayah) 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.
Misalkan $x_i$ menyatakan banyaknya latih tanding yang dilakukan pada minggu ke-$i$. Misalkan pula $y_i$ menyatakan banyaknya latih tanding yang telah dilakukan sampai minggu ke-$i$. Dengan kata lain $$y_i = x_1+x_2+ \ldots +x_i$$
Dalam satu minggu, terdapat sedikitnya satu latih tanding, tetapi tidak lebih dari total $125$ latih tanding dalam periode $75$ minggu. Ini berarti $$1 \leq y_1 < y_2 < \ldots < y_{75} \leq 125 \qquad \ldots(\ast)$$
Tambahkan $24$ pada setiap ruas, sehinga diperoleh $$25 \leq y_1+24 < y_2+24 < \ldots < y_{75}+24 \leq 149$$
Perhatikan barisan yang terdiri dari $150$ suku berikut. $$y_1,y_2,\ldots,y_{75},y_1+24,y_2+24,\ldots,y_{75}+24$$
Ada $149$ nilai yang mungkin untuk suku-suku tersebut, yaitu $1,2, \ldots,149$. Berdasarkan Prinsip Sangkar Burung, terdapat dua suku yang bernilai sama. Namun dari pertidaksamaan $(\ast)$ kita tahu bahwa tidak ada suku yang sama di antara $y_1,y_2,\ldots,y_{75}$. Begitupun dengan $y_1+24,y_2+24,\ldots,y_{75}+24$. Akibatnya terdapat $i,j \in \{1,2,\ldots,75\}$ sedemikian sehingga $y_i=y_j+24$. Dari persamaan ini diperoleh $$\begin{aligned} 24 &= y_i-y_j \\[3pt] &= (x_1+\ldots+x_j+x_{j+1}+\ldots + x_i)-(x_1+\ldots+x_j) \\[3pt] &= x_{j+1}+x_{j+2}+\ldots + x_i \end{aligned}$$
Dengan demikian, pada minggu ke-$j+1$ sampai dengan minggu ke-$i$ petinju tersebut melakukan tepat $24$ latih tanding. Terbukti.
(2017 Wilayah) Diberikan bilangan bulat $n \geq 5$. Tuliskan sebuah argumentasi kombinatorial untuk memperlihatkan bahwa $$\binom{2n}{5} = 2\binom{n}{5} + 2n\binom{n}{4} + (n^2-n)\binom{n}{3}$$
Misalkan terdapat $2n$ orang, dengan $n \geq 5$, yang terdiri dari $n$ perempuan dan $n$ laki-laki. Akan dibentuk sebuah kelompok yang beranggotakan $5$ orang. Hal ini dapat dilakukan melalui dua cara.
Cara 1. Pilih sebanyak $5$ di antara $2n$ orang yang ada, tanpa memperhatikan jenis kelaminnya. Banyak cara melakukan hal ini adalah $$\binom{2n}{5}$$
Cara 2. Dalam memilih $5$ orang tersebut, ada $6$ kemungkinan yang bisa terjadi. Pertama, kelima orang yang terpilih seluruhnya laki-laki. Kedua, terpilih $4$ orang laki-laki dan $1$ orang perempuan. Dan seterusnya. Banyak cara untuk setiap kemungkinan adalah $$\begin{aligned} &5L \; 0P&&: &\binom{n}{5}\binom{n}{0}&= \binom{n}{5}\\[3pt] &4L \; 1P&&: &\binom{n}{4}\binom{n}{1}&= n\binom{n}{4} \\[3pt] &3L \; 2P&&: &\binom{n}{3}\binom{n}{2}&= \frac{n^2-n}{2}\binom{n}{3} \\[3pt] &2L \; 3P&&: &\binom{n}{2}\binom{n}{3}&= \frac{n^2-n}{2}\binom{n}{3} \\[3pt] &1L \; 4P&&: &\binom{n}{1}\binom{n}{4}&= n\binom{n}{4} \\[3pt] &0L \; 5P&&: &\binom{n}{0}\binom{n}{5}&=\binom{n}{5} \end{aligned}$$
Secara keseluruhan, terdapat cara sebanyak $$2\binom{n}{5} + 2n\binom{n}{4} + (n^2-n)\binom{n}{3}$$
Berdasarkan kedua cara di atas, diperoleh $$\binom{2n}{5} = 2\binom{n}{5} + 2n\binom{n}{4} + (n^2-n)\binom{n}{3}$$ Terbukti.
(2017 Wilayah) 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 sikel di $G$.
Pernyataan $P \iff Q$ ekuivalen dengan $\neg P \iff \neg Q$. Sehingga untuk membuktikan pernyataan dalam soal, kita dapat menunjukkan bahwa "sisi $e$ bukan cut edge di $G$ jika dan hanya jika $e$ termuat dalam suatu sikel di $G$".
Dari kiri. Misalkan $e=uv$ adalah sisi di $G$ yang bukan cut edge dan $H$ adalah komponen graf $G$ yang memuat $e$. Karena $e$ bukan cut edge, maka jumlah komponen $H\setminus e$ sama dengan jumlah komponen dari $H$. Dengan kata lain, $H\setminus e$ terhubung.
Akibatnya terdapat lintasan dari $u$ ke $v$ pada $H\setminus e$. Dengan menambahkan $e$ pada lintasan tersebut, terbentuklah sebuah sikel pada $H$. Ini juga sikel pada $G$, karena $H$ merupakan komponen graf $G$. Terbukti.
Dari kanan. Misalkan $e=uv$ adalah sisi di graf $G$ dan $H$ adalah komponen graf $G$ yang memuat $e$. Misalkan pula $e$ termuat dalam suatu sikel, sehingga terdapat lintasan dari $u$ ke $v$ yang tidak memuat $e$, sebutlah $P$.
Diambil sebarang simpul $x$ dan $y$ pada $H\setminus e$. Karena $H$ terhubung, maka terdapat lintasan dari $x$ ke $y$. Ada dua kemungkinan yang bisa terjadi. Pertama, lintasan tersebut tidak memuat $e$, sehingga juga merupakan lintasan pada $H\setminus e$.
Kemungkinan kedua, lintasan tersebut memuat $e$. Ganti kemunculan sisi $e$ dengan lintasan $P$, sehingga terbentuk sebuah jalan dari $x$ ke $y$. Ini berakibat adanya lintasan dari $x$ ke $y$. Lintasan baru ini tidak memuat $e$, sehingga juga merupakan lintasan $H\setminus e$.
Dari dua kemungkinan ini, bisa disimpulkan bahwa $H \setminus e$ terhubung. Sehingga jumlah komponen $H\setminus e$ sama dengan jumlah komponen $H$. Dengan demikian, $e$ bukan cut edge. terbukti.