OSN 2017 Matematika Hari Pertama (Soal dan Solusi)

Silakan unduh soal dan solusinya di sini: osn2017h1.pdf.

 

Advertisements

Ketaksamaan kompleks ekivalen

Misalkan $a,b\in \mathbb{C}$. Buktikan bahwa $\left| az+b\bar{z} \right|\le 1$, untuk setiap $z\in \mathbb{C}$, dengan $\left| z \right|=1$, jika dan hanya jika$\left| a \right|+\left| b \right|\le 1$.

Bukti.

(Jika)

Jika $|a|+|b| \le 1$, maka dengan ketaksamaan segitiga, berlaku $|az+b\overline{z}| \le |a||z|+|b||\overline{z}| = |a|+|b| \le 1$.

(Hanya jika)

Asumsikan bahwa $|az+b\overline{z}| \le 1$ untuk setiap $z$ dengan $|z|=1$. Jika $a=0$ atau $b=0$, ketaksamaan $|a|+|b| \le 1$ terpenuhi. Asumsikan $ab \ne 0$. Dengan manipulasi aljabar, berlaku $|az^2+b| \le 1$. Ini juga berakibat $|az+b| \le 1$ untuk setiap $|z|=1$. Akibatnya
$|a|^2+|b|^2+a\overline{b}z+\overline{a}b\overline{b} \le 1 \quad (*)$.
Ambil $z=\dfrac{|a||b|}{a\overline{b}}$, perhatikan bahwa $|z|=1$ dan ketaksamaan $(*)$ menjadi $|a|^2+|b|^2+2|a||b| \le 1$ yang berakibat $|a|+|b| \le 1$.

Terbukti.

Refleksi.

Soal yang cukup rutin kecuali ide untuk kalimat terakhir yang mengambil $z=\dfrac{|a||b|}{a\overline{b}}$ harus sedikit licik. 🙂

 

Soal OSN 2016 Hari Kedua Soal 5

Ini adalah salah satu dari tiga soal saya yang diterima menjadi soal OSN 2016 di Palembang, Sumatera Selatan. Sama seperti soal kedua hari pertama, aslinya soal ini diajukan untuk OSP (tingkat provinsi), namun saya coba ajukan lagi dan ternyata diterima. Yeah.

Soal. Andaikan $x$ merupakan bilangan real sehingga barisan bilangan bulat yang didefinisikan dengan $a_n=\lfloor nx \rfloor$ untuk setiap bilangan asli $n$ merupakan barisan aritmetika. Haruskah $x$ merupakan bilangan bulat?

Solusi. Ya. Misalkan $x=a+r$ dengan $a$ bilangan bulat dan $0 \le r < 1$. Perhatikan bahwa berlaku untuk setiap bilangan asli $n$:

$2\lfloor nx \rfloor = \lfloor (n-1)x \rfloor + \lfloor (n+1)x \rfloor$

$2na + 2\lfloor nr \rfloor = (n-1)a+\lfloor (n-1)r \rfloor + (n+1)a+\lfloor (n+1)r \rfloor$

$2\lfloor nr \rfloor = \lfloor (n-1)r \rfloor + \lfloor (n+1)r \rfloor$.

Asumsikan $r>0$, maka terdapat bilangan asli $k$ sehingga $\dfrac{1}{k+1} \le r < \dfrac{1}{k}$. Ini akan berakibat $(k-1)r<kr<1$ dan $(k+1)r \ge 1$. Artinya, $\lfloor (k-1)r \rfloor=\lfloor kr \rfloor=0$ dan $\lfloor (k+1)r \rfloor = 1$. Dengan mensubstitusi $n=k$ pada persamaan terakhir, diperoleh persamaan $2 (0)=0+1$ yang tidak valid.

Dengan demikian, haruslah $r=0$. Ini berarti $x$ haruslah berupa bilangan bulat.

Refleksi.

Soal ini sebenarnya harapannya mudah, makanya dijadikan soal pertama di hari kedua OSN. Namun, sepertinya soal ini tidak bisa dikatakan immediate juga bagi peserta OSN yang sebagian besar masih belum terbiasa menuangkan ide matemtis ke dalam tulisan yang runut. Alhasil, soal nomor 7, yaitu soal teori bilangan yang lebih terlihat “menghitung” memberikan nilai rata-rata yang lebih tinggi dibandingkan soal nomor 5 ini.

Hal yang paling sulit dari soal ini adalah memilih bilangan asli $k$ yang memenuhi $\dfrac{1}{k+1} \le r < \dfrac{1}{k}$. Mengapa sulit? Perhatikan bahwa untuk $r$ yang semakin mendekati $0$, nilai $k$ yang dipilih pun akan semakin besar agar memenuhi pertidaksamaan tersebut. Dengan demikian, pengambilan nilai $k$ yang cukup besar ini adalah langkah yang perlu (necessary) untuk menyelesaikan soal. Di nilai batas $k$ inilah titik kritis di mana barisan tersebut akan gagal menjadi barisan aritmetika untuk $r>0$. Menggunakan manipulasi aljabar biasa tidak membantu menyelesaikan soal ini. Ada properti analisisnya sedikit-sedikit. Oh ya properti ini dikenal juga dengan Archimedian Property.

Selain itu, hanya menggunakan informasi bahwa berhingga suku dari $a_n=\lfloor nx \rfloor$  merupakan barisan aritmetika tidak akan berhasil. Hal ini karena pada dasarnya ada $x$ yang tidak bulat yang membuat berhingga suku tersebut barisan aritmetika. Jadi, mengambil nilai  $k$ yang cukup besar adalah jalan yang “harus dilewati” untuk menyelesaikan soal ini. Tidak harus sama persis argumennya, namun begitulah kurang lebih struktur solusinya.

Kondisi ekivalen untuk lapangan berhingga berkarakteristik 2

Soal. Misalkan $\displaystyle \mathcal K$ merupakan lapangan berhingga. Buktikan bahwa pernyataan berikut ekivalen:

(a) $\displaystyle 1+1=0$;

(b) untuk setiap $\displaystyle f \in \mathcal K \left[ X \right]$ dengan $\displaystyle \textrm{deg} \, f \geq 1$, $\displaystyle f \left( X^2 \right)$ reducible.

(Romania National Olympiad 2006)

Solusi.

$\text{(a)} \rightarrow \text{(b)}$.
Perhatikan bahwa $\mathcal K$ memiliki kardinalitas berbentuk $2^n$ untuk suatu bilangan asli $n$. Untuk setiap $a \in \mathcal K$, berlaku $a+a=0$ sehingga $-a=a$. Sekarang, perhatikan himpunan $S=\{a^2:a \in \mathcal K\}$, akan ditunjukkan bahwa $S=\mathcal K$. Jelas $S \subseteq \mathcal K$. Sekarang, misalkan ada $x,y \in \mathcal K$ sehingga $x^2=y^2$. Ini berakibat $(x-y)(x+y)=0$. Artinya $x-y=0$atau $x+y=0$. Namun, karena $x+x=y+y=0$, maka $x=y$. Jadi, setiap elemen berbeda $a \in \mathcal K$, menghasilkan $a^2 \in S$ yang berbeda-beda. Terbukti bahwa $S=\mathcal K$.

Jadi, untuk setiap $a \in \mathcal K$, ada $b \in \mathcal K$, sehingga $a=b^2$. Dengan demikian, untuk setiap polinomial $f(X)=\sum_{k=0}^n a_kX^k \in \mathcal K[X]$, kita punyai ada $b_k$ sehingga $b_k^2=a_k$. Ini berakibat
$f(X^2)=\sum_{k=0}^n b_k^2X^{2k} = \left( \sum_{k=0}^n b_kX^k \right)^2=f(X)^2$
sehingga terbukti bahwa $f(X^2)$ irreducible.

$\text{(b)} \rightarrow \text{(a)}$.
Kita buktikan kontraposisinya. Misalkan $1+1 \ne 0$, maka karakteristik dari $\mathcal K$ adalah $p>2$ suatu bilangan prima. Perhatikan bahwa $\mathcal K - \{0\}$ merupakan grup siklis perkalian dengan order $p^n-1$ untuk suatu bilangan asli $n$. Karena $p$ ganjil, maka $p^n-1$ genap. Jadi, ada $\alpha \in \mathcal K$ dengan $\alpha^2 = 1 = 1^2$. Dengan demikian, ada elemen $\beta \in \mathcal K$ yang bukan kuadrat suatu elemen $\mathcal K$. Sekarang, pandang polinomial $f(X)=X-\beta$. Perhatikan bahwa $f(X^2)$ irreducible karena $X^2-\beta=0$ tidak punya akar.

Refleksi.

Contoh soal yang menarik tentang lapangan. Saya sedang mengumpulkan soal-soal dan solusi tentang lapangan. Hehe. Semoga nanti berguna sebagai referensi. 🙂

Tes 4 IMO 2016 Tahap 3

Soal. Evaluasi nilai

\displaystyle \sum_{k=0}^{n-1} \dfrac{1}{1+8\sin^2 \left(\dfrac{k \pi}{n} \right)}.

Solusi.

Misalkan \theta_k=\dfrac{k \pi}{n} untuk k=0,1,2,\dots,n-1, maka

\sin \theta_k = \dfrac{e^{i \theta_k} - e^{-i \theta_k}}{2i}.

Misalkan z_k=e^{2i \theta_k}, maka ekspresi pada soal dapat diubah menjadi

\displaystyle \sum_{k=0}^{n-1} \dfrac{1}{1-2\left(e^{i\theta_k}-\dfrac{1}{e^{i\theta_k}}\right)^2}

\displaystyle = \sum_{k=0}^{n-1} \dfrac{e^{2i\theta_k}}{-2e^{4i\theta_k}+5e^{2i\theta_k}-2}

\displaystyle = \sum_{k=0}^{n-1} \dfrac{z_k}{-2z_k^2+5z_k-2}

\displaystyle = \sum_{k=0}^{n-1} \dfrac{z_k}{(2z_k-1)(2-z_k)}

\displaystyle =\sum_{k=0}^{n-1} \dfrac{2}{3} \left( \dfrac{1}{2-z_k} \right) - \dfrac{1}{3} \left(\dfrac{1}{1-2z_k}\right)

di mana z_k adalah akar-akar dari polinomial p(z)=z^n-1 untuk k=0,1,2,\dots,n-1.

Dengan demikian, bentuk tersebut akan sama nilainya dengan

\displaystyle =\dfrac{2}{3} \times \dfrac{p'(2)}{p(2)} - \dfrac{1}{3} \times \dfrac{1}{2} \times \dfrac{p'(\frac{1}{2})}{p(\frac{1}{2})}
\displaystyle =\dfrac{2}{3} \times \dfrac{n 2^{n-1}}{2^n-1} + \dfrac{1}{6} \times \dfrac{n}{2^n-1}

\displaystyle = \dfrac{n}{6} \times \dfrac{2^{n+1}-1}{(2^n-1)}.

Refleksi

Saya berpikir bahwa ini soal standar, mungkin hanya mengandalkan kemampuan manipulasi aljabar. Namun, ternyata hanya ada 1 orang yang berhasil menyelesaikan soal ini di Tahap 3. Saat saya cobakan ke anak pelatnas IMC 2016, cukup banyak yang bisa. Well, saya pikir permasalahannya cuman satu sih, kekurangan pengalaman mengerjakan soal-soal aljabar. Semoga nanti di IMO mereka cukup lihai dalam mengerjakan soal-soal aljabar yang bertipe manipulasi saja. Good luck.

Seleksi IMC 2016 Hari Pertama Soal 3

Soal 3. Misalkan F merupakan lapangan berhingga dengan 2^{2n} anggota.

(i) Tunjukkan bahwa ada \alpha \in F demikian sehingga \alpha^2+\alpha+1=0.

(ii) Apakah x^4+x+1 irreducible di F[x]?

Solusi.

(a)

Perhatikan bahwa F-\{0\} merupakan subgrup cyclic dengan order 4^n-1. Karena 3|4^n-1, maka ada unsur \alpha \in F-\{0\} dengan \alpha \ne 1 yang berorder 3. Dengan demikian, \alpha^3=1. Namun, (\alpha-1)(\alpha^2+\alpha+1)=0 dan \alpha-1 \ne 0. Jadi, \alpha^2+\alpha+1=0.

(b)

Perhatikan bahwa

(x^2+x+\alpha)(x^2+x+\alpha+1)=(x^2+x+\alpha)^2+ x^2+x+\alpha

=x^4+x^2+\alpha^2+x^2+x+\alpha

=x^4+x+1.

Jadi, x^4+x+1 reducible.