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.

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 Kedua Soal 5

Soal 5. Tinjau grup himpunan bilangan rasional  terhadap operasi penjumlahan (\mathbb{Q},+).

(a) Tunjukkan bahwa terdapat koleksi subgrup H_1,H_2,H_3\dots dari \mathbb{Q} sehingga H_i \ne \mathbb{Q} untuk setiap i dan \mathbb{Q}=H_1 \cup H_2 \cup H_3 \cup \dots.

(b) Adakah koleksi hingga subgrup S_1,S_2,\dots,S_n dari \mathbb{Q} sehingga S_i \ne \mathbb{Q} untuk setiap i dan \mathbb{Q}=S_1 \cup S_2 \cup \dots \cup S_n?

Solusi.

(a)

Misalkan \displaystyle H_k = \{\dfrac{j}{k}: j \in \mathbb{Z}\}. Jelas bahwa H_k merupakan subgrup. Selain itu, perhatikan bahwa H_1 \cup H_2 \cup \dots = \mathbb{Q}.

(b)

Asumsikan ada. Misalkan S_i \ne \mathbb{Q}, maka terdapat bilangan asli n_i demikian sehingga \dfrac{1}{k_i} \notin S_i. Pernyataan ini benar, karena jika seandainya \dfrac{1}{k} \in S_i untuk semua bilangan asli k, maka sifat grup S_i mengakibatkan S_i=\mathbb{Q}.

Misalkan \mathbb{Q}=S_1 \cup S_2 \cup \dots \cup S_n, maka ada \dfrac{1}{k_i} \notin S_i untuk i=1,2,\dots,n. Selain itu, karena \dfrac{1}{k_i} \notin S_i, maka untuk setiap bilangan asli m berlaku pula \dfrac{1}{mk_i} \notin S_i. Dari sini, diperoleh bahwa \dfrac{1}{k_1k_2 \dots k_n} \notin S_i untuk setiap i=1,2,\dots,n. Padahal, \dfrac{1}{k_1 k_2 \dots k_n} \in \mathbb{Q} tetapi bukan anggota S_1 \cup S_2 \cup \dots \cup S_n. Kontradiksi.

Seleksi IMC 2016

Terima kasih kepada M. Faikar M. A. (Universitas Negeri Malang) yang bersedia  membagikan soalnya ke grup OSN Matematika PT. 🙂

Tes diadakan dua kali di dua hari berturutan. Masing-masing tes mengandung 5 soal dari bidang aljabar abstrak, aljabar linear, kombinatorika, analisis real, dan analisis kompleks. Durasi tes adalah 4 jam. Setiap soal berbobot sama.

Hari Pertama

Soal 1. Misalkan f:(0,\infty) \rightarrow \mathbb{R} merupakan fungsi yang terturunkan dua kali dan turunan keduanya kontinu demikian sehingga

\displaystyle \lim_{x \to 0^+} f'(x) = +\infty, dan

\displaystyle \lim_{x \to 0^+} f''(x) = - \infty.

Tunjukkan bahwa

\displaystyle \lim_{x \to 0^+} \dfrac{f'(x)}{f''(x)} = 0.

Soal 2. Tentukan semua bilangan kompleks z yang memenuhi |z-|z+1||=|z+|z-1||.

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]?

Soal 4. Sebuah n-board adalah sebuah persegi panjang berukuran n \times 1. Misalkan g_n menyatakan banyak cara mengubin n-board dengan menggunakan ubin 1 \times 1 dan 2 \times 1. Jadi, g_1=1 dan g_2=2. Untuk n \ge 0, perlihatkan bahwa

\displaystyle g_n = \sum_{i \ge 0} \sum_{j \ge 0} {n-i \choose j} {n-j \choose i}.

Soal 5. Misalkan A \in \mathbb{C}^{n \times n} matriks tak singular dan \overline{A} merupakan matriks yang diperoleh dengan mengganti setiap komponen A dengan konjugatnya. Misalkan \lambda merupakan bilangan real negatif. Jika \lambda merupakan nilai eigen dari A\overline{A}, tunjukkan bahwa multiplisitas aljabarnya genap.

Hari Kedua

Soal 1. Misalkan n merupakan bilangan bulat positif dan k merupakan bilangan bulat tak negatif dengan 0 \le k \le n/2. Buktikan bahwa

\displaystyle \sum_{m=k}^{n-k} {m \choose k}{n-m \choose k} = {n+1 \choose 2k+1}.

Soal 2. Diberikan fungsi f:[a,b] \rightarrow \mathbb{R} yang terdiferensialkan dan f(a)=0. Misalkan terdapat A>0 dan k>0 sehingga |f'(x)-kf(x)| \le A|f(x)| untuk setiap x \in [a,b]. Buktikan bahwa f(x)=0 untuk setiap x \in [a,b].

Soal 3. Misalkan 0<r<R merupakan konstanta dan \gamma adalah lingkaran |z|=r. Tunjukkan bahwa

\displaystyle \int_\gamma \dfrac{R+z}{Rz-z^2}dz = 2\pi i

dan

\displaystyle \dfrac{1}{2\pi} \int_0^{2\pi} \dfrac{R^2-r^2}{R^2+r^2-2Rr \cos \theta}d\theta =1.

Soal 4. Misalkan V merupakan ruang vektor atas bilangan real dan \{v_1,v_2,\dots,v_k\} merupakan subhimpunan yang bebas linear dari V. Untuk suatu nilai tetap \alpha,\beta \in \mathbb{R} dengan \alpha \ne 0, definisikan

u_i = \alpha \sum_{j \ne i} v_j+\beta v_i

untuk setiap i=1,2,\dots,k. Tentukan semua semua kemungkinan dimensi subruang yang direntang oleh u_1,u_2,\dots,u_k.

Soal 5. Tinjau grup himpunan bilangan rasional  terhadap operasi penjumlahan (\mathbb{Q},+).

(a) Tunjukkan bahwa terdapat koleksi subgrup H_1,H_2,H_3\dots dari \mathbb{Q} sehingga H_i \ne \mathbb{Q} untuk setiap i dan \mathbb{Q}=H_1 \cup H_2 \cup H_3 \cup \dots.

(b) Adakah koleksi hingga subgrup S_1,S_2,\dots,S_n dari \mathbb{Q} sehingga S_i \ne \mathbb{Q} untuk setiap i dan \mathbb{Q}=S_1 \cup S_2 \cup \dots \cup S_n?

 

OSN 2016

Sudah hampir satu bulan saya tidak posting apa-apa di blog ini. Alasannya seperti biasa, pekerjaan di kampus.

Ada dua kabar, kabar baik dan buruk. Kabar buruknya adalah saya batal menjadi juri OSN 2016 di Palembang karena harus mengurus administrasi beasiswa. Kabar baiknya adalah soal saya diterima di OSN 2016 ini.  Tidak terlalu gabutlah ya. 😀

Ini adalah tiga soal yang diterima tersebut. Di OSN 2016 sendiri, ada dua tes yang masing-masing lamanya 4 jam. Setiap tes mengujikan 4 soal dari 4 bidang, yaitu aljabar, geometri, kombinatorika, dan teori bilangan, dengan tingkat kesulitan yang berbeda-beda. Di OSN 2016 ini, ada 3 soal saya yang diterima. Terakhir kali ini terjadi pas OSN 2010 di mana pas tes  Hari Kedua, soal saya terpilih untuk soal nomor 6, 7, dan 8. Di OSN 2011 – 2015, tidak ada satu pun soal saya yang masuk. Kapan-kapan saya bisa cerita prosedur pemilihan soal OSN. Intinya sih melalui voting, ya gitu aja, ditambah sedikit diskusi yang biasanya ribut di antara  para juri. 😛

Oke, ini tiga soal tersebut. Saya tulis soalnya dulu. Solusi menyusul.

Hari Pertama

Soal 2. Cari semua bilangan asli (a,b,c) yang memenuhi sekaligus:

(i) c>1, dan

(ii) 2^{2016}+2^c=a^b.

Soal 3. Lima buah kotak disusun secara melingkar, dengan satu kotak berisi satu bola dan kotak-kotak lainnya kosong. Ada dua operasi yang diizinkan untuk dilakukan terhadap kotak dan bola ini:

  1. Ambil satu bola dari suatu kotak tak kosong, lalu tambahkan satu bola ke masing-masing dua kotak tetangganya (yang berada di kiri dan kanan kotak yang diambil bolanya)
  2. Ambil satu bola dari suatu kotak tak kosong, lalu masukkan bola tersebut ke salah satu kotak kosong di sebelah kotak tersebut.

Mungkinkah pada akhirnya, setiap kotak berisi tepat 17^{5^{2016}} bola?

Hari Kedua

Soal 5. Diberikan bilangan real x demikian sehingga barisan tak hingga a_n=\lfloor nx \rfloor untuk n=1,2,3,\dots membentuk barisan aritmetika. Haruskah x merupakan bilangan bulat?

Next time, saya akan coba post solusi masing-masing soal dan kontroversi yang terjadi karena soal ini muncul di OSN. Serius, soal-soal di atas sedikit bermasalah dengan keberadaan teorema-teorema yang lebih advanced. Ini akan seru untuk dibahas. 🙂 Untuk sementara, coba dikerjakan dulu. :3