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. 🙂

Soal favorit saya lagi: Barisan digit

Soal ini menggunakan solusi yang sangat mirip dengan soal favorit saya yang pernah saya post tahun 2011 dan juga muncul di kontes besar semacam APMO. Mirip. Otomatis jadi soal favorit lagi hehehe. 🙂

Soal. Diberikan barisan digit-digit $2,0,2,9,3,\dots$ sehingga setiap digit merupakan digit terakhir dari hasil jumlah empat digit sebelumnya. Apakah digit-digit $2,0,1,5$ pernah muncul berturutan di dalam barisan tersebut?

Continue reading

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.

Ternyata matriks permutasi

Misalkan A \in \mathbb{R}^{n \times n} merupakan matriks yang invertible yang entri-entrinya merupakan bilangan bulat tak negatif. Andaikan bahwa himpunan

\displaystyle \bigcup_{i=1}^\infty \{A^i\}

merupakan himpunan berhingga. Tunjukkan bahwa A merupakan matriks permutasi.

Solusi.

Karena himpunan tersebut berhingga, terdapat dua bilangan asli berbeda i>j sehingga A^i=A^j. Dengan demikian, A^{i-j}=I. Misalkan n merupakan bilangan asli terkecil demikian sehingga A^n=I. Mudah dilihat bahwa \displaystyle \bigcup_{i=1}^\infty \{A^i\}=\{I,A,A^2,\dots,A^{n-1}\}.

Sekarang, karena \det(A^n)=I, maka \det(A)=\pm 1. Dengan demikian, terdapat permutasi \sigma dari 1,2,\dots,n demikian sehingga \prod_i a_{i \sigma(i)}. Dengan demikian, terdapat matriks permutasi P dan matriks tak nol dan matriks berentri bulat tak negatif A_1 demikian sehingga A=P+A_1.

Perhatikan bahwa terdapat bilangan asli m dan n demikian sehingga A^m=P^n=I. Kedua ruas dari persamaan A=P+A_1 dipangkatkan mn sehingga diperoleh

A^{mn}=P^{mn}+P^{mn-1}A_1+\dots+A_1^{mn}

I=I+P^{mn-1}A_1+\dots+A_1^{mn}

O=P^{mn-1}A_1+\underbrace{\dots+A_1^{mn}}_{\text{semua entrinya} \, \ge 0}

sehingga semua entri P^{mn-1}A_1 haruslah bernilai 0. Namun P^{mn-1} merupakan matriks permutasi sehingga hanya mengacak urutan baris A_1. Dengan demikian, haruslah A_1=O.

Jadi, diperoleh bahwa A=P+O=P untuk suatu matriks permutasi P.

Refleksi.

Ini soal imut-imut tidak bersalah. Saya suka.