[Problem] Soal Dengan Pangkat Irasional

[Problem] Soal Dengan Pangkat Irasional

00:02:00   Olimpiade Matematika, soal-soal,

Beberapa minggu terakhir, saya menemukan soal-soal (di problem set olimpiade) yang ternyata bisa saya selesaikan dengan menggunakan Teorema Kalkulus.

Teorema yang akan kita pakai pada post berikut ini adalah Teorema Nilai Antara. Teorema ini termasuk teorema Kalkulus yang memang tidak termasuk pada kurikulum IMO, tapi penggunaannya tidak dilarang.

(Teorema Nilai Rata-Rata)
Misalkan $A\subset \mathbb{R}$ dan $f: A \rightarrow \mathbb{R}$ adalah fungsi yang kontinu pada interval $[a,b] \subset A$ dan terdiferentialkan pada interval $(a,b)$. Maka terdapat $\xi \in (a,b)$ sedemikian sehingga
\[\frac{f(b)-f(a)}{b-a}=f^{\prime}(\xi)\]

Bukti teorema ini (hampir?) selalu pasti ada di buku textbook Calculus.

Berikut adalah sebuah soal yang bisa diselesaikan dengan menggunakan Teorema Nilai Rata-Rata. Tapi menurut saya soal ini harusnya tidak ada di olimpiade SMA, karena menggunakan definisi dari pangkat irasional, yang mana hal tersebut menggunakan fungsi logaritma natural.

[Edit: Ternyata soal ini adalah soal Putnam 1971 A6]

Diberikan bilangan real $r>0$ sedemikian sehingga $n^r \in \mathbb{Z}$ untuk setiap $n \in \mathbb{N}$. Buktikan bahwa $r \in \mathbb{Z}$.

Solusi:

Definisikan fungsi $f(x)=x^r$. Kemudian untuk sebarang bilangan $w \in \mathbb{N}$ kita definisikan barisan fungsi $f_0(w), f_1(w), f_2(w), ....$ sebagai
\[f_0(w) = f(w) \qquad f_j(w) = f_{j-1}(w+1)-f_{j-1}(w) \quad j\geq 1\]

Dari hipotesa soal dan definisi diatas, diperoleh $f_j(w)$ selalu merupakan bilangan bulat untuk setiap bilangan asli $j$ dan $w$. Selanjutnya kita akan membutuhkan lemma berikut:

Lemma
Untuk bilangan asli $1 \leq k \leq j$ terdapat bilangan real $w_k \in (w, w+k)$ sedemikian sehingga
\[f_j (w) = f_{j-k}^{(k)}(w_k)\]

Bukti Lemma: Pertama-tama kita buktikan dulu untuk $k=1$ dan $k=2$ (agar lebih jelas). Dengan menggunakan Teorema Nilai Rata-Rata,  terdapat $w_1 \in (w, w+1)$ yang memenuhi
\[f_j(w) = f_{j-1}(w+1) - f_{j-1}(w) = f_{j-1}^{\prime}(w_1)\]
Sedangkan $f_{j-1}^{\prime}(w_1) = f_{j-2}^{\prime}(w_1+1) - f_{j-2}^{\prime}(w_1)$ yang dengan menggunakan Teorema Nilai Rata-Rata lagi, diperoleh $w_2 \in (w_1, w_1+1) \subset (w,w+2)$ yang memenuhi \[f_{j-2}^{\prime}(w_1+1) - f_{j-2}^{\prime}(w_1) = f_{j-2}^{\prime \prime}(w_2)\]
Sekarang kita bisa lanjutkan dengan menggunakan induksi matematika, yaitu jika $f_j(w)=f_{j-k}^{(k)}(w_k)$ untuk suatu $w_k \in (w, w+k)$ maka
\[f_j(w)=f_{j-k}^{(k)}(w_k) = f_{j-k-1}^{(k)}(w_k+1)- f_{j-k-1}^{(k)}(w_k) =  f_{j-k-1}^{(k+1)}(w_{k+1})\]
dimana $w_{k+1} \in (w_k , w_{k}+1) \subset (w, w+k+1)$. Jadi Lemma Terbukti.

Sekarang kembali ke soal,  tulis $r = \lfloor r \rfloor + \{r\}$ , dan tulis juga $s={\lfloor r \rfloor}+1$,  definisikan juga  $A=\prod_{k=1}^s (r-k+1)$, jadi kita bisa tulis turunan ke-$s$ dari $f(x)$ adalah $A \cdot x^{r-s}$.

Asumsikan  $r$ bukan bilangan bulat, maka diperoleh $A>0$.

Sekarang karena $s-r>0$ kita bisa memilih bilangan asli $w$ yang memenuhi $w^{s-r}> A$. Kemudian dengan menggunakan lemma untuk $k=j=s$ diperoleh

\[f_{s} (w)=f^{(s)}(w_s)= A \cdot w_s^{r-s} \]

dimana $w_s \in (w, w+s)$.  Perhatikan bahwa $r-s+1 > 0$ namun  $r-s$ negatif,  sehingga diperoleh $A>0$ dan $w_s^{r-s} < w^{r-s}$.  Kita simpulkan

\[0< f_{s} (w) < A \cdot w^{r-s}< 1 \]

Hal ini kontradiksi dengan observasi sebelumnya bahwa $f_s(w)$ selalu bilangan bulat.

Edit : Dari komentar Yosua Yonathan dan Erlang di Facebook, soal ini juga benar apabila  "untuk setiap $n \in \mathbb{Z}$" diganti dengan "$n \in \{2,3,5\}$".  Lebih lanjut lagi untuk $n \in \{2,3\}$ masalah ini dipercaya masih merupakan open problem.

Masalah yang berhubungan dengan soal ini adalah Six Exponentials Theorem dan Four Exponentials Conjecture

Continue Reading

Soal Partisi Bilangan Bulat.

Soal Partisi Bilangan Bulat.

00:17:00   Olimpiade Matematika, Umum,

Beberapa hari yang lalu, saya diberi soal berikut oleh Erlang Wiratama Surya :

Diberikan himpunan $X \subset \mathbb{Z}$ dan misalkan $a_1, a_2, \cdots, a_n$ adalah bilangan bulat sedemikian sehingga
\[\mathbb{Z} = \bigcup_{j=1}^n (X+a_j)\]
dan $X+a_i \cap X+a_j = \emptyset$ untuk sebarang $i\neq j$.  Buktikan bahwa terdapat bilangan  bulat tak-nol $p$ sedemikian sehingga $X+p=X$.(Disini definisi dari $X+d:= \{x+d | x \in X\}$ ).

Katanya soal ini ada di Sesi Mandiri Pembinaan IMO Tahap 4.

Sebenarnya saya sudah pernah lihat soal ini sebelumnya (dan waktu itu saya tidak bisa menyelesaikannya).  Tapi sudah lupa dimana.

Sampai sekarang, saya masih penasaran tentang dimana saya melihat soal ini (saya memang sering berasa tidak lega dan agak annoying kalo ada sesuatu berasa di ujung lidah seperti ini :/  )

Bahkan setelah beberapa hari, saya berhasil menyelesaikan soal ini, tapi masih belum tahu source nya (sampai bikin thread di math.stackexcange menanyakan sumber).

Saya  (secara dejavu) merasa  ini bukan soal yang bersumber dari olimpiade, tapi dari matematika popular yang saya pernah baca di blog-blog post beken (Terence Tao, Timothy Gowers, dll)

Anyway ini solusinya, lagi-lagi saya pakai sesuatu yang sering saya pakai beberapa bulan terakhir (lihat soal kompetisi olimpiade.org no 4 buatan saya dan juga teknik yang sama di mini-artikel yang saya tulis ini ) yaitu kombinasi dari Indicator Function + PigeonHole Principle.

Solusi: 
Pertama-tama perhatikan bahwa apabila kita pilih bilangan asli $d$ sedemikian sehingga $a_i^{\prime}=a_i + d$ semua positif maka himpunan $X=X^{\prime} - d$ juga memenuhi

\[\mathbb{Z} = \bigcup_{i=1}^n (X^{\prime} + a_i^{\prime})\]

dan $X^{\prime} + a_i^{\prime} \cap X^{\prime} + a_j^{\prime} = \emptyset$. Lalu, apabila kita berhasil membuktikan $X^{\prime} + p^{\prime} = X^{\prime}$ maka diperoleh $X+p-d= X-d$, jadi $X+p=X$, dan soal terbukti.  Ini berarti pengubahan $a_i \rightarrow a_i^{\prime}$ tidak mengubah maksud soal.

Sehingga tanpa kehilangan keumuman soal bisa diasumsikan semua $a_i$ positif, dan tanpa kehilangan keumuman juga bisa diasumsikan $a_n > a_{n-1} > \cdots  > a_1$.

Sekarang kita definisikan fungsi indikator

\[v_i = \begin{cases} 1 & \text{jika $i\in X$, } \\ 0 & \text{jika tidak} \end{cases} \]

Idenya adalah dengan membuktikan bahwa fungsi indikator $v_i$ periodik, yakni $v_{i+p} =v_i$ untuk suatu $p$.

Maka dari kondisi $X+a_1, X+a_2, \cdots, X+a_n$ adalah partisi dari $\mathbb{Z}$,  diperoleh untuk setiap bilangan bulat $r$ berlaku

\[v_{r-a_1} + v_{r-a_2} + \cdots + v_{r-a_n} = 1\]

Sekarang misalkan $\lambda=a_n - a_1$.  Persamaan diatas adalah relasi rekursif, jadi apabila kita mempunyai informasi nilai awal  paling banyak $\lambda=a_n-a_1$ buah, maka solusi rekursif tersebut akan unik.

Jadi apabila nilai dari

\[v_{r+1}, v_{r+2}, \cdots, v_{r+\lambda}\]

diketahui maka nilai $v_i$ akan bisa di-generate  untuk setiap $i$. Karena $v_i$ hanya bisa nol atau satu, maka kemungkinan nilai awal diatas  hanya ada $2^{\lambda}$. Jadi apabila kita bentuk block-block dengan panjang $\lambda$ :

\[\cdots ,  \{ v_{-\lambda-1},  \cdots, v_{-1}, v_0\} , \{v_1, v_2, \cdots, v_{\lambda} \} , \{v_{\lambda+1}, v_{\lambda+1}, \cdots, v_{2 \lambda}\} , \cdots , \{v_{r+1}, v_{r+2}, \cdots , v_{r+\lambda}\}, \cdots  \]

 maka berdasarkan prinsip PigeonHole terdapat $u_1$ dan $u_2$ sedemikian sehingga

\[v_{u_1+i}=v_{u_2+i} \qquad i=1, \cdots, \lambda \]

dan karena block $v_{u_1 + 1}, v_{u_1+2}, \cdots , v_{u_1 + \lambda}$ men-generate nilai $v_i$,   maka  $v_{u_2 + 1}, v_{u_1+2}, \cdots , v_{u_2 + \lambda}$ juga men-generate nilai $v_i$ yang sama, jadi  nilai setelah $u_2$ mengulangi nilai setelah $u_1$, dan nilai sebelum $u_2+1$ mengulangi nilai sebelum $u_1+1$, sehingga $v_i$ periodic.

Ini berarti terdapat $p \neq 0$ sedemikian sehingga $v_{i+p} = v_i$,  untuk setiap $i$. Sehingga jika $h \in X$ jika dan hanya jika $v_{h} = 1 = v_{h+p}$ jika dan hanya jika $h+p \in X$. Terbukti.

Continue Reading

Soal IMO 2015 Nomor 6

Soal IMO 2015 Nomor 6

23:04:00   Olimpiade Matematika,

IMO 2015, Soal 6

Diberikan barisan bilangan bulat $a_1, a_2, \cdots, a_n, \cdots$ yang memenuhi
i) $1 \leq a_j \leq s$ untuk setiap $j \geq 1$
ii)  $k+a_k \neq l+a_l$ untuk setiap $1 \leq k < l$.

Buktikan bahwa terdapat bilangan bulat $N$ dan $b$ sedemikian sehingga

\[ \left| \sum_{i=m+1}^{n} (a_i-b) \right| \leq \left(\frac{s-1}{2}\right)\]
untuk setiap $n> m \geq N$

Solusi:

Definisikan $b_i:= a_i + i$. Berdasarkan sifat ii)  $b_i$ adalah bilangan bulat yang berbeda satu sama lain dan dari sifat i) berlaku  \[i+1 \leq b_i \leq s+i.\]


Pertama-tama kita buktikan dulu lemma berikut.

Lemma 1
Terdapat himpunan $\mathcal{B} \subset \mathbb{N}$ yang memenuhi $|\mathcal{B}|=b \leq s$ sedemikian sehingga jika $x \in \mathbb{N}$ dan $x \neq b_j$ untuk setiap $j$ maka $x \in \mathcal{B}$.  Dengan kata lain, hanya ada berhingga banyaknya bilangan yang tidak berada pada himpunan $R=\{b_1, b_2,  b_3, \cdots, \}$.


Bukti Lemma:
Misalkan tidak demikian, maka ini berarti $R=\{b_1, b_2,  b_3, \cdots, \}=\mathbb{N}$ atau himpunan $\mathcal{B}$ yang demikian mempunyai banyak anggota lebih dari $s$ (bisa saja punya tak berhingga anggota).  Kemungkinan pertama $R=\mathbb{N}$ tidak mungkin karena $1< 1+i \leq a_i + i =b_i$.

Kemudian misalkan  kemungkinan kedua terjadi yaitu $\mathcal{B}$ mempunyai lebih dari $s$ anggota, ini berarti terdapat lebih dari $s$ buah bilangan yang tidak berada di $R$. Misalkan $1=r_1 <  r_2 <  \cdots < r_{s+1}$ adalah $s+1$ buah bilangan pertama yang tidak berada di $R$. Perhatikan bahwa

\[\begin{align*} 2 & \leq b_1 \leq s+1 \\
3 &\leq b_2 \leq s+2 \\
\,  &\,  \cdots \,  \,   \\
r_{s+1} +1 &\leq b_{r_{s+1}} \leq s+r_{s+1}\end{align*} \]

Ini berarti $b_1, b_2, \cdots, b_{r_{s+1}}$ adalah $r_{s+1}$ buah bilangan berbeda yang berada pada interval $[2,s+r_{s+1}]$,  sehingga terdapat $s+r_{s+1}-1 - (r_{s+1})=s-1$ buah bilangan lain yang berada pada interval tersebut,  $s-1$ buah bilangan yang tersisa ini bisa mungkin anggota $R$ bisa juga tidak,  ini berarti pada interval $[2,s+r_{s+1}]$ terdapat paling banyak $s-1$ buah bilangan yang bukan anggota $R$, akan tetapi $r_2, r_3 , \cdots, r_{s+1}$ semuanya juga berada di interval $[2, s+r_{s+1}]$ dan  merupakan $s$ buah bilangan yang juga bukan anggota $R$, kontradiksi. Lemma terbukti.



Sekarang kita akan mengestimasi nilai dari jumlah parsial

\[\sum_{j=m+1}^n b_j\]

untuk $m$ cukup besar.

Kita notasikan sebagai $\mathcal{N}_j = \{1,2, \cdots, j\}$ . Jelas bahwa $\mathcal{N}_i \subset \mathcal{N}_j$ untuk setiap $i < j$.

Berdasarkan Lemma 1, himpunan $\mathcal{B}$ adalah himpunan yang berhingga, yang mempunyai $b$ buah anggota dimana $b \leq s$. Jadi di himpunan $\mathcal{B}$ terdapat anggota yang paling besar di himpunan tersebut, sebutlah $N$. Dengan demikian, untuk setiap $x \in \mathcal{B}$ selalu berlaku $x \leq N$, sehingga $x \in \mathcal{N}_N$, diperoleh $\mathcal{B}\subseteq \mathcal{N}_N$.

Diperoleh, untuk setiap $n > m \geq N$ maka berlaku \[\mathcal{B} \subseteq \mathcal{N}_N \subseteq \mathcal{N}_m \subset \mathcal{N}_n\]


Lemma 2

Untuk sebarang $v>N$ berlaku
\[\mathcal{N}_{v+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_v\}\subseteq \mathcal{N}_{v+s} \setminus \mathcal{B}.\]

Bukti Lemma: 
Misalkan terdapat $x \in \mathcal{N}_{v+1} \setminus \mathcal{B}$  dan $x \neq b_j$ untuk $1 \leq j \leq v$. Karena $x \not \in \mathcal{B}$, maka $x=b_k$ untuk suatu $k$ dan karena $x \neq b_j$ untuk $1\leq j \leq v$  maka haruslah $k>v$, kita simpulkan $x=b_{k}$ dimana $k \geq v+1$. Lalu karena $x \in \mathcal{N}_{v+1}$ diperoleh $x \leq v+1$, jadi
\[v+1 \geq x=b_k \geq k+1 \geq v+2 \]
kontradiksi, jadi terbukti $\mathcal{N}_{v+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_v\}$.
Sekarang ambil sebarang $x \in  \{b_1, b_2 , \cdots, b_v\}$, maka $x \not \in \mathcal{B}$, dan $x=b_k$ untuk suatu $k \leq v$, diperoleh $x=b_k \leq k+s \leq v+s$, jadi $x \in \mathcal{N}_{v+s}$, bersama dengan $x \not \in \mathcal{B}$ dapat disimpulkan bahwa $x \in \mathcal{N}_{v+s}\setminus \mathcal{B}.$ Lemma terbukti.


Lemma 3
Untuk $m>N$ , terdapat tepat  $b-1$ buah bilangan di $\{m+2, m+3, \cdots, m+s\}$ yang merupakan anggota dari $\{b_1, b_2, \cdots, b_m\}$

Bukti Lemma :
Dari Lemma 2, karena $m>N$ berlaku $\mathcal{N}_{m+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_m\}$, dan karena $|\mathcal{N}_{m+1} \setminus \mathcal{B}| = m+1-b$ dan $|\{b_1, b_2 , \cdots, b_m\}| = m$ maka terdapat tepat $m-(m+1-b)=b-1$ buah suku dari himpunan $\{b_1, b_2 , \cdots, b_m\}$ yang berada pada himpunan $\{m+2, m+3, \cdots, m+s\}$.

Kita akan menghitung nilai minimum dari $\sum_{j=m+1}^n b_j$. Jumlahan ini dapat ditulis

\[\sum_{j=1}^{n} b_j - \sum_{j=1}^{m} b_j\]

agar minimum, maka $\sum_{j=1}^{m} b_j$ harus sebesar-besarnya, dan dar Lemma terdapat $b-1$ buah suku pada $\{b_1, b_2, \cdots, b_{m}\}$ yang berada di $\{m+2, m+3, \cdots, m+s\}$, jadi agar  sebesar-besarnya, $b-1$ buah suku ini adalah $m+s , m+s-1, \cdots , m+s-b+2$.

Kemudian suku-suku pada $\{b_{m+1}, b_{m+2}, \cdots, b_n\}$ harus sekecil-kecilnya, dan karena untuk $j \geq m+1$ berlaku $b_{j} \geq j+1 \geq m+2$, maka yang terkecil adalah mulai dari $m+2, m+3, \cdots$ dan seterusnya, tapi perhatikan dari paragraf sebelumnya bahwa nilai $m+s-b+2, m+s-b+3, \cdots, m+s$ sudah terpakai untuk pada suku-suku di $\{b_1, b_2, \cdots, b_{m+1}\}$ (dan harus terpakai). Ini berarti pada himpunan $\{m+1, m+2, \cdots, m+s\}$ kita hanya boleh menggunakan

\[\{m+2 , m+2 , \cdots, m+s-b+1 \}\]

karena $\sum_{j=m+1}^n b_j$ memuat $n-m$ suku, dan kita baru memakai $|\{m+2 , m+2 , \cdots, m+s-b+1 \}| = s-b$ suku, maka masih harus ada $n-m-s-b$ buah suku lain, dan kemungkinan terkecil nya adalah setelah melangkahi $\{m+s-b+2, \cdots, m+s\}$ (karena sudah terpakai) yaitu

\[\{m+s+1, m+s+2, \cdots , n+b \}\]

Sehingga diperoleh
\[\begin{align*}\sum_{j=m+1}^{n} b_j &\geq \sum_{j=m+2}^{m+s-b+1} j + \sum_{j=m+s+1}^{n+b} j \\ &= \left( \frac{2m+s-b+3}{2} \right)(s-b) + \left(\frac{n+m+s+b+1}{2}\right) \left(n+b-m-s\right) \\ &= \left(\frac{s-b}{2}\right) (m-2b-n+2) +(n-m)\left( \frac{n+m+s++b+1}{2}\right) \\ &= (n-m) \left(\frac{n+m+2b+1}{2}\right) -(b-1)(s-b) \end{align*}\]

Jadi
\[\begin{align*}\sum_{j=m+1}^n (a_j - b) &= \sum_{j=m+1}^n (b_j-j-b) \\ &= \sum_{j=m+1}^n b_j -\sum_{j=m+1}^n j - (n-m)b \\ &\geq (n-m) \left(\frac{n+m+2b+1}{2}\right) -(b-1)(s-b) - \sum_{j=m+1}^n j - (n-m) b \\ &= -(b-1)(s-b)\end{align*}\]

Diperoleh
\[\sum_{j=m+1}^n (a_j - b) \geq -(b-1)(s-b) \qquad (1)\]

Sekarang akan di estimasi nilai maksimum dari $\sum_{j=m+1}^n b_j$.  Berdasarkan Lemma 3, karena $n > N$, maka terdapat tepat $b-1$ buah anggota $\{n+2, n+3, \cdots, n+s\}$ yang juga anggota $\{b_1, b_2, \cdots, b_n\}$. Jadi agar maksimum, $b-1$ buah anggota-anggota ini haruslah yang sebesar-besarnya yaitu $n+s-b + 2, n+s-b+3, \cdots, n+s$.

Karena $\sum_{j=m+1}^n b_j$ mempunyai $n-m$ suku, maka yang perlu dibatasi masih $n-m-b+1$ buah suku lagi dan mereka harus berasal dari himpunan $\{1,2 ,\cdots, n+1\}$ (jika tidak demikian maka $\{n+2, \cdots, n+s\}$ memuat lebih dari $b-1$ buah suku), dan agar maksimum dipilih $n-m-b+1$ buah anggota terbesar di $\{1,2, \cdots, n+1\}$ yaitu $n+1, n, \cdots,  m + b +1$.

Diperoleh
\[\begin{align*}\sum_{j=m+1}^n b_j &\leq \sum_{j=n+s-b+2}^{n+s} j + \sum_{j=m+b+1}^{n+1} j \\  &= \left(\frac{2n+2s-b+2}{2} \right)\left(b-1\right) + \left(\frac{n+m+b+2}{2}\right) \left(n-m-b+1\right) \\ &= \left(\frac{n-m+2s-2b}{2} \right)(b-1)+ \left(\frac{n+m+b+2}{2}\right) \left(n-m\right) \\ &=(b-1)(s-b) + (n-m) \left(\frac{n+m+2b+1}{2}\right)
\end{align*}\]

Sehingga
\[\begin{align*}\sum_{j=m+1}^n (a_j - b) &= \sum_{j=m+1}^n (b_j-j-b) \\ &= \sum_{j=m+1}^n b_j -\sum_{j=m+1}^n j - (n-m)b \\ &\leq (n-m) \left(\frac{n+m+2b+1}{2}\right) +(b-1)(s-b) - \sum_{j=m+1}^n j - (n-m) b \\ &= (b-1)(s-b)\end{align*}\]

Digabungkan dengan ketaksamaan (1) diperoleh

\[-(b-1)(s-b) \leq \sum_{j=m+1}^n (a_j - b) \leq (b-1)(s-b) \Rightarrow \left| \sum_{j=m+1}^n (a_j - b) \right| \leq (b-1)(s-b) \]

Dengan menggunakan AM-GM diperoleh $(b-1)(s-b) \leq \left(\frac{b-1+s-b}{2}\right)^2 = \left(\frac{s-1}{2}\right)^2$. Sehingga

\[\left| \sum_{j=m+1}^n (a_j - b) \right| \leq \left(\frac{s-1}{2}\right)^2. \]

Q.E.D

Continue Reading

23:02:00   Olimpiade Matematika,

I solved IMO problem 5 with the "density" style,  this is not that precise actual density from the topology course. High School students usually view 'dense' as "always getting somewhere in between". Note that (until this post got published) this proof is quite different from the proofs given in Mathlinks.

IMO 2013 Problem 5
Find all function $f: \mathbb{Q}_+\rightarrow \mathbb{R}$ which satisfies:
a) $f(x+y) \geq f(x)+f(y)$ for all $x, y \in \mathbb{Q}_+$.
b) $f(x)f(y) \geq f(xy)$ for all $x, y \in \mathbb{Q}_+$.
c) There exists $a\in \mathbb{Q}_+$ and $a> 1$ such that $f(a)=a$.

Solution: 

We first prove the following lemma:

Lemma: The set $A:=\left\{\frac{a^k}{n} \lvert k, n \in \mathbb{N}\right\}$ is "dense" in $\mathbb{Q}_+$. That is for any $x, y \in \mathbb{Q}_+$ there exists $\theta \in A$ such that $x < \theta < y$.

Proof: 
Given $x, y \in \mathbb{Q}_+$ with $y> x$, since $a> 1$ we can choose $k$ large enough so that $\frac{a^k}{x}-\frac{a^k}{y}=a^k \left(\frac{y-x}{xy}\right)> 1$. Therefore there exists an integer $N$ in the interval $\left(\frac{a^k}{y},\frac{a^k}{x}\right)$. Thus

\[\frac{a^k}{y} < N < \frac{a^k}{x}\]

This means $x < \frac{a^k}{N} < y$. $\blacksquare$.

From condition 3, we have $f(a)=a >  0$, thus $f(1)a=f(1)f\left(a\right) \geq f\left(a\right) = a$. Therefore $f(1) \geq 1$.

Next we will prove that $f(n)\geq n$ for all $n \in \mathbb{N}$.
Obviously, we have $f(x_1+x_2+\cdots+x_n)\geq f(x_1)+f(x_2)+\cdots+f(x_n)$. 
Thus $f(n)\geq f(1)n \geq n$.

Next we will prove that $f(x) > 0$ for all $x \in \mathbb{Q}_+$. Suppose that there exists a positive rational number $t$ such that $f(t) \leq 0 $ choose a positive integer $s$ such that $st$ is an integer. Hence since $f(s)\geq s > 0$ we have $st\leq f(st) \leq f(s) f(t) \leq 0$, a contradiction.

Then we prove that $f$ is monotonely increasing, for any positive rational numbers $y > x$, then $y=x+ t$ for some positive rational number $t$. Thus $f(y)= f(x+t)\geq f(x)+f(t) > f(x)$.

We have $f(a^k)\leq f(a)^k = a^k$ thus for any integers $m$ and $k$ we have $m f\left(\frac{a^k}{m}\right) \leq f(a^k) \leq a^k$ which implies
\[f\left(\frac{a^k}{m}\right)\leq \frac{a^k}{m} \qquad \text{for any integers $k,  m$}\]

We will prove that $f(r)\leq r$ for all $r \in \mathbb{Q}_+$. Suppose that there exists a  positive rational number $r$ such that $f(r) > r$, fix a natural number $k$ , then $v:=\frac{a^{k+1}}{f(r)-r}$ is a defined positive number. Thus we can take an integer $m$ greater than $v$.

But, by our lemma, between $r+\frac{a^k}{m}$ and $r+\frac{a^{k+1}}{m}$ there exists a rational number of the form $\frac{a^l}{u}$, hence by the monotonity we have

\[f(r) < f\left(r+\frac{a^k}{m}\right) < f\left(\frac{a^l}{u}\right) \leq \frac{a^l}{u} < r+\frac{a^{k+1}}{m} \]

But then $m < \frac{a^{k+1}}{f(r)-r} =v$ a contradiction. Thus for all positive rational numbers $r$ we have $f(r)\leq  r$ , in particular $f(n)\leq n$ for all natural numbers, since we also have $f(n)\geq n$ we conclude that $f(n)=n$ for all natural numbers $n$.

For any rational numbers $\frac{b}{c}$ where $b$ and $c$ are positive integers we have $f\left(\frac{b}{c}\right) \geq \frac{f(b)}{f(c)}=\frac{b}{c}$, therefore $f(r)\geq r$ for all $r\in \mathbb{Q}_+$, since $f(r)\leq r$ as well, we conclude that $f(r)=r$. It is easy to check that this function satisfies the given conditions. 

Continue Reading

Soal Persamaan Fungsi

Soal Persamaan Fungsi

20:07:00   Olimpiade Matematika,

Sebenarnya post ini cuma mau nge-test LaTex di Dynamic View nya blogger. Tapi ya sekalian kasi soal-Soal Fungsi berikut saya anggap susah.

Source nya nggak disebutkan, ada yang saya tahu ada yang saya lupa  (itung-itung buat yang mau latihan bisa ngilangin temptation untuk nge-browse solusinya di Mathlinks :D )
 ------------------------------------------------------
1. Tentukan semua fungsi $f : \mathbb{R}^+ \rightarrow \mathbb{R}^+$ yang memenuhi
\[f(x)f(y)=f(y)f(xf(y))+\frac{1}{xy}\]

2. Tentukan semua fungsi $f: \mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi : untuk setiap $x,y\in \mathbb{R}$
\[f(y+f(x))=f(x)f(y)+f(f(x))+f(y)-xy\]
untuk setiap $x,y \in \mathbb{R}$.

3. Tentukan semua fungsi $f: \mathbb{R}^+ \rightarrow \mathbb{R}^+$ yang memenuhi: untuk setiap $x,y\in \mathbb{R}^+$
\[f(x)f(y)=2f(x+yf(x))\]

4. Misalkan $f(x) \in \mathbb{Z}[x]$ dengan $\text{deg}(f(x))=4$, buktikan terdapat $M \in \mathbb{N}$ sedemikian sehingga \[f(n!) \equiv \pmod {2^n-1}\] untuk setiap $n>M$

5. Tentukan semua fungsi $f: \mathbb{N} \rightarrow \mathbb{N}$ yang memenuhi: untuk setiap $m,n \in \mathbb{N}$
\[f(m^2+f(n))=f(m)^2+n\]

6. Tentukan semua fungsi $f: \mathbb{R}\rightarrow \mathbb{R}$ yang memenuhi: untuk setiap $x,y\in \mathbb{R}$
\[f(xf(x+y))=f(yf(x))+x^2\]

7. Tentukan semua fungsi $f:\mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi: untuk setiap $x,y\in \mathbb{R}$
\[f(x-f(y))=f(f(y))+xf(y)+f(x)-1\]

8. Tentukan semua  fungsi $f: \mathbb{N} \rightarrow \mathbb{N}$ yang memenuhi untuk setiap $m,n \in \mathbb{N}$
\[f(f(m)^2+2f(n)^2)=m^2+2n^2\]

9. Tentukan semua fungsi $f:\mathbb{R} \rightarrow \mathbb{R}$ yang memenuhi: untuk setiap $x\in \mathbb{R}$ berlaku
\[f(x^2)=f(x)^2 \qquad \text{dan} \qquad f(x+1)=f(x)+1\]

10.Misalkan $f:\mathbb{R} \rightarrow \mathbb{R}$ fungsi monoton tak turun yang memenuhi
\[f(x+f(y))=f(f(x))+f(y)\]
untuk setiap $x,y \in \mathbb{R}$

Continue Reading

Exercises

Exercises

04:31:00   Olimpiade Matematika,

Solution for problem 11 is taken from American Math Monthly. Yes, Forgot to type solution for No 1, but maybe I don't need to, It's an easy problem :)

Problems

Solutions

Continue Reading

OSN Matematika 2012 Hari Pertama

OSN Matematika 2012 Hari Pertama

00:40:00   Olimpiade Matematika,

Ini adalah soal-soal dari OSN 2012 yang dilaksanakan tadi siang.


Berikut solusinya, kecuali soal no 3, karena saya tidak terlalu bisa Euclidean geometri jadi no 3 nggak saya kerjain :D


1. (Nanang Susyanto) Buktikan bahwa untuk sebarang bilangan asli $a$ dan $b$, bilangan

\[n=KPK(a,b)+FPB(a,b)-a-b\]

adalah bilangan genap tak negatif.

Solusi: Misalkan $d=FPB(a,b)$ maka $a=d x$ dan $b=d y$ dimana $x,y\in \mathbb{N}$ memenuhi $FPB(x,y)=1$, lalu $KPK(a,b)=\frac{ab}{FPB(a,b)}=dxy$ , jadi kita peroleh

\[n=d(x-1)(y-1)\geq 0\]

Karena $FPB(x,y)=1$ maka $x$ dan $y$ tidak mungkin dua-dua nya genap, jadi salah satu dari $x$ atau $y$ adalah bilangan ganjil, sehingga salah satu dari $x-1$ atau $y-1$ adalah bilangan genap, sehingga $n$ pasti genap.




2. (IMO Shortlist 2012) Diberikan bilangan asli $n$ dan bilangan real positif $a_1,a_2,\cdots,a_n$. Buktikan bahwa

\[(1+a_1)^2 (1+a_2)^3 \cdots (1+a_n)^{n+1} \geq (n+1)^{n+1}a_1 a_2 \cdots a_n \]




Solusi: Dengan menggunakan ketaksamaan AM-GM diperoleh untuk setiap bilangan bulat $i$

\[(1+a_i)=\left(\frac{1}{i}+\frac{1}{i}+\cdots + \frac{1}{i} + a_i\right) \geq (i+1) \left(\frac{a_i}{i^i}\right)^{\frac{1}{i+1}}\]

yang setara dengan

\[(1+a_i)^{i+1} \geq \frac{(i+1)^{i+1}}{i^i} a_i\]

Apabila dikalikan diperoleh

\[\begin{align*}(1+a_1)^2 (1+a_2)^3 \cdots (1+a_n)^{n+1} &\geq \frac{2^2}{1^1} \cdot \frac{3^3}{2^2} \cdots \frac{(n+1)^{n+1}}{n^n}\\ &= (n+1)^{n+1}a_1 a_2 \cdots a_n \end{align*}\]


3. (Suwono & Fajar Yuliawan) Diberikan segitiga lancip $ABC$ dengan $AB>AC$ dan memiliki titik pusat lingkaran luar $O$. Garis $BO$ dan $CO$ memotong garis bagi $BQ$ dan $CP$ berpotongan di titik $R$. Buktikan bahwa garis $AR$ tegak lurus $BC$.

Solusi:


4. (Hendrata Dharmawan) Diberikan 2012 titik berbeda $A_{1},A_{2},\ldots ,A_{2012}$ di bidang Cartesius. Untuk sebarang permutasi $B_{1},B_{2},\ldots ,B_{2012}$ dari $A_{1},A_{2},\ldots ,A_{2012}$, didefinisikan bayangan dari titik $P$ terhadap permutasi tersebut sebagai berikut.

Titik $P$ dirotasikan $180^{\circ }$ dengan pusat $B_{1}$ menghasilkan titik $P_{1}$,

titik $P_{1}$ dirotasikan $180^{\circ }$ dengan pusat $B_{2}$ menghasilkan titik $P_{2}$,  $\cdots ,$ titik $P_{2011}$ dirotasikan $180^{\circ }$ dengan pusat $B_{2012}$ menghasilkan titik $P_{2012}$. 

Selanjutnya, titik $P_{2012}$ dikatakan sebagai bayangan dari titik $P$ terhadap permutasi $B_{1},B_{2},\ldots ,B_{2012}$. Misalkan $N$ adalah banyak bayangan titik $P$ yang berbeda terhadap semua permutasi dari $A_{1},A_{2},\ldots ,A_{2012}$. Tentukanlah nilai terbesar yang mungkin bagi $N$.

Solusi: Misalkan titik $B_i$ mempunyai koordinat $(x_i,y_i)$ dan titik $P$ mempunyai koordinat $(s,t)$. Misalkan juga koordinat $P_i$ adalah $(s_i,t_i)$.

Diperoleh koordinat $P_1$ adalah $(-(s-x_1)+x_1,-(t-y_1)+y_1)=(2x_1-s,2y_1-t)$, dan untuk setiap $2 \leq i \leq 2012$ diperoleh

\[(s_i,t_i)=(2x_i-s_{i-1},2y_i-t_{i-1})\]

Diperoleh

\[s_{2012}=2x_{2012}-s_{2011}=2x_{2012}-2x_{2011}+s_{2010}=\left(\sum_{k=1}^{2012} (-1)^k x_k\right) + s\]

\[t_{2012}=2y_{2012}-t_{2011}=2y_{2012}-2y_{2011}+t_{2010}=\left(\sum_{k=1}^{2012} (-1)^k y_k\right) + t\]

Jadi kita diharapkan menemukan: Dari sebarang banyak koordinat $(x_1,x_2,\cdots,x_n)$ kita hitung berapa kali nilai

\[\sum_{k=1}^{2012} (-1)^k x_k\]

bisa berubah apabila $(x_1,\cdots,x_{2012})$ dipermutasikan, dan kita ingin menemukan maksimal dari perubahan ini.

Misalkan $(x_1,x_2,\cdots,x_{2012})$ dipermutasikan menurut permutasi $\pi$, maka penjumlahan nya menjadi $\sum_{k=1}^{2012}(-1)^k x_{\pi(k)}$. Akan dihitung berapa banyak ekspresi penjumlahan yang bisa terjadi.

Perhatikan bahwa setiap variabel $x_i$ dalam penjumlahan pasti bertanda positif atau negatif, dan tepat $1006$ diantaranya yang positif sedangkan $1006$ yang lain nya pasti negatif. Dengan demikian apabila kita mengambil sebarang $1006$ buah variabel $x_i$ dan memberikannya tanda negatif, maka $1006$ variabel sisa nya pasti diberi tanda positif dengan sendirinya. Jadi banyaknya membentuk ekspresi penjumlahan tersebut sama dengan banyaknya memilih $1006$ variabel dari $2012$ variabel yang ada, yaitu sebanyak

\[{2012 \choose 1006}\]

Dengan demikian nilai $N$ yang menyatakan banyak maksimal nilai berbeda dari ekspresi penjumlahan ini tidak akan lebih dari banyaknya semua ekspresi yang mungkin, diperoleh

\[N\leq {2012 \choose 1006}\]

Akan ditunjukan bahwa $N={2012 \choose 1006}$, dengan menunjukan bahwa terdapat nilai $x_i$ sedemikian sehingga $\sum_{k=1}^n (-1)^k x_{\pi(k)}$ bernilai berbeda untuk sebarang permutasi $\pi$.

Misalkan $x_k=2^k$, dan anggap ada dua permutasi $\pi$ dan $\sigma$ sedemikian sehingga

\[\sum_{k=1}^n (-1)^k 2^{\pi(k)}=\sum_{k=1}^n (-1)^k 2^{\sigma(k)}\]

Misalkan $\pi(u)=\sigma(v)$, apabila $u$ dan $v$ mempunyai paritas yang sama maka kedua suku $(-1)^u2^{\pi(u)}$ dan $(-1)^{v}2^{\sigma(v)}$ saling menghilangkan, sedangkan apabila $u$ dan $v$ mempunyai paritas yang berbeda, maka kedua suku tersebut menggabung menjadi $ \pm 2^{u+1}$ yang bisa berada di sisi kiri atau di sisi kanan, dengan demikian setelah disisihkan, akan diperoleh

\[2^{u_1+1}+2^{u_2+1}\cdots + 2^{u_k+1}= 2^{v_1+1} +2^{v_2+1}+\cdots \cdots +2^{v_l+1}\]

dimana semua $u_i,v_i$, berbeda, bagi kedua ruas dengan $2^{\min{v_i+1,u_i+1}}$, diperoleh salah satu dari sisi kanan atau kiri adalah bilangan genap dan sisi lain nya bilangan ganjil, kontradiksi.

yang tidak mungkin. Jadi $N={2012 \choose 1006}$.

Continue Reading

OSN Matematika 2012 Hari Kedua

OSN Matematika 2012 Hari Kedua

00:39:00   Olimpiade Matematika,

Ini solusi hari kedua, again geometri nya saya skip :D :p


Soal 5 (Stefanus Lie). Diberikan bilangan asli $m$ dan $n$. Misalkan $P$ dan $Q$ adalah dua kumpulan $m\times n$ bilangan $0$ dan $1$ yang disusun dalam $m$ baris dan $n$ kolom. Contoh salah satu kumpulan itu untuk $m=3$ dan $n=4$ adalah
\[\left[ \begin{array}{cccc}1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0\end{array}\right] .\]

Misalkan kedua kumpulan tersebut memenuhi empat sifat berikut.

(i) Pada setiap baris di $P$, bilangan dari kiri ke kanan tidak pernah naik (boleh sama atau turun),

(ii) pada setiap kolom di $P$, bilangan dari atas ke bawah tidak pernah naik (boleh sama atau turun),

(iii) jumlah bilangan pada sebarang baris di $P$ sama dengan jumlah bilangan pada baris yang sama di $Q$, dan

(iv) jumlah bilangan pada sebarang kolom di $P$ sama dengan jumlah bilangan pada kolom yang sama di $Q$.

Tunjukkanlah bahwa bilangan pada baris ke-$i$ kolom ke-$j$ di $P$ sama dengan bilangan pada baris ke-$i$ kolom ke-$j$ di $Q$ untuk setiap $i=1,2,\ldots ,m$ dan $j=1,2,\ldots ,n$.

Solusi:  Kita akan membuktikan hal ini dengan induksi terhadap $m+n$.

Apabila $m+n=2$, maka pernyataan jelas benar. Apabila $m+n=3$, terdapat dua kemungkinan $m=2$ dan $n=1$ atau $m=1$ dan $n=2$, pernyataan benar dengan menggunakan iii) dan iv).

Untuk $m+n=4$, apabila $n=1$ maka karena setiap baris hanya mempunyai satu angka berdasarkan iii) soal langsung terbukti, begitu juga apabila $m=1$, soal terbukti dengan iv). Apabila $m=n=2$, maka $P$ akan berbentuk

\[\left[ \begin{array}{cc}1 & 1 \\ 1 & 1\end{array}\right],  \left[ \begin{array}{cc}1 & 1 \\ 0 & 0\end{array}\right], \left[ \begin{array}{cc}1 & 0 \\ 1 & 0\end{array}\right], \left[ \begin{array}{cc}0 & 0 \\ 0 & 0\end{array}\right], \left[ \begin{array}{cc}1 & 1 \\ 1 & 0\end{array}\right], \]

Perhatikan bahwa dari sifat iii) baris $[1 \,\, 1]$ pada $P$ akan menghasilkan baris yang sama di $Q$, begitu pula kolom $\left[\begin{array}{c}1 \\ 1\end{array}\right]$ dengan sifat iv). Hal yang sama jg berlaku untuk baris $[0\,\, 0]$ dan $\left[\begin{array}{c} 0 \\ 0\end{array}\right]$. Jadi pada empat bentuk pertama dari $P$ diatas, dapat disimpulkan bahwa $Q$ akan berbentuk sama. Sedangkan untuk $P$ yang  berbentuk $\left[ \begin{array}{cc}1 & 1 \\ 1 & 0\end{array}\right]$, $Q$ akan berbentuk $\left[ \begin{array}{cc}1 & 1 \\ 1 & x\end{array}\right]$, tapi berdasarkan iv) $1+x=1+0$, jadi $x=0$, sehingga $P$ dan $Q$ sama juga untuk bentuk ini.

Sekarang misalkan soal benar untuk setiap kumpulan $a \times b$ dimana $a+b\leq k$. Akan dibuktikan bahwa soal juga benar untuk setiap kumpulan $x\times y$ dimana $x+y=k+1$.

Kasus 1. Jika terdapat bilangan pada baris pertama dari $P$ yang sama dengan nol, dan misalkan $u$ adalah indeks pertama dari kiri sedemikian sehingga bilangan ke-$u$ dari kiri pada baris pertama $P$ sama dengan nol, berdasarkan sifat i) semua bilangan ke -$u+1$, $u+2, \cdots, y$ pada baris pertama dari $P$ semuanya  juga samadengan nol. 

Dari sifat  ii) diperoleh kolom ke-$u$, $u+1,u+2,\cdots, y$ dari $P$  semuanya mempunyai bilangan samadengan nol, yang berarti hasil penjumlahan bilangan dari masing-masing kolom samadengan $0$.  

Berdasarkan sifat iii) dan iv)  kolom ke-$u$, $u+1,u+2,\cdots, y$ dari $Q$ masing-masing juga mempunyai hasil penjumlahan yang sama dengan nol, lalu karena bilangan yang mungkin hanya $0$ atau $1$, maka  kolom ke-$u$, $u+1,u+2,\cdots,y$ dari $Q$ juga semuanya nol. Kita telah memperoleh  kolom ke-$u$, $u+1,u+2,\cdots,y$ dari $P$ dan  kolom ke-$u$, $u+1,u+2,\cdots,y$ dari $Q$ mempunyai bilangan yang sama. Selanjutnya akan dibuktikan  kolom ke-$1$, $2,\cdots,u-1$ dari $P$ dan kolom ke-$1$, $2,\cdots,u-1$ dari $Q$ juga mempunyai bilangan yang sama.

Sekarang kita mempunyai $x \times u-1$ kumpulan bilangan sisa yang belum diketahui nilai nya, anggap $x\times u-1$ kumpulan bilangan pada $P$ sebagai $P^{\prime}$ dan $x\times u-1$ kumpulan bilangan pada $Q$ sebagai $Q^{\prime}$. Karena $P^{\prime}$ berasal dari $P$, maka $P^{\prime}$ juga memenuhi sifat i), ii). Lalu karena kolom-kolom yang dibuang sebelumnya bernilai nol, maka hasil penjumlahan bilangan pada  kolom dan hasil penjumlahan bilangan pada baris $P^{\prime}$ dan $Q^{\prime}$ tidak berubah, sehingga sifat iii) dan iv) juga tetap berlaku untuk $P^{\prime}$ dan $Q^{\prime}$.

 Ditambah lagi $x+u-1 < x+y=k+1$, jadi $x+u-1\leq k$, dan berdasarkan hipotesa induksi soal benar untuk $a+b \leq k$, jadi bilangan-bilangan di $P^{\prime}$ sama dengan bilangan -bilangan pada $Q^{\prime}$. Kita peroleh $P$ dan $Q$ memuat bilangan yang sama pada setiap posisi nya.

Kasus 2. Jika semua bilangan pada baris pertama dari $P$ tidak samadengan nol, dengan kata lain semua bilangan samadengan 1. Diperoleh baris pertama dari $P$ mempunyai hasil jumlah $y$, jadi berdasarkan iii) $Q$ juga mempunyai hasil jumlah $y$, yang menyebabkan semua bilangan pada baris pertama dari $Q$ juga semuanya samadengan 1,  yakni $P$ dan $Q$ mempunyai baris pertama yang sama.

Sekarang misalkan $\overline{P}$ dan $\overline{Q}$ adalah bagian dari $P$ dan $Q$ secara berurutan mulai dari baris kedua sampai baris ke-$x$. Karena $\overline{P}$ berasal dari $P$ maka sifat i) dan ii) juga berlaku untuk $\overline{P}$. Lalu karena setiap baris dari $\overline{Q}$ adalah baris dari $Q$, dan setiap baris dari $\overline{P}$ adalah baris dari $P$, mak sifat iii) juga berlaku untuk $\overline{P}$ dan $\overline{Q}$. Untuk tiap kolom dari $\overline{P}$ dan tiap kolom dari $\overline{Q}$, hasil penjumlahan bilangan pada kolom tersebut samadengan hasil penjumlahan bilangan pada kolom $P$ dan $Q$ secara berurutan dikurang $1$, jadi  iv) juga berlaku untuk $\overline{P}$ dan $\overline{Q}$.

$\overline{P}$ dan $\overline{Q}$ masing-masing mempunyai ukuran $x-1 \times y$, dan $x-1+y=k-1$, jadi berdasarkan hipotesa induksi, $\overline{P}$ dan $\overline{Q}$ adalah kumpulan bilangan yang sama. 

Soal 6 (Fajar Yuliawan) Misalkan $\mathbb{R}^{+}$ menyatakan himpunan semua bilangan real positif. Tunjukkan bahwa tidak ada fungsi $f:\mathbb{R}^{+}\rightarrow \mathbb{R}^{+}$ yang memenuhi
\[f\left( x+y\right) =f\left( x\right) +f\left( y\right) +\frac{1}{2012}\] untuk setiap bilangan real positif $x$ dan $y$.

Solusi:

Misalkan fungsi tersebut ada, dengan menggunakan induksi matematika kita peroleh untuk sebarang bilangan asli $n$ berlaku

\[f(nx)=nf(x)+\frac{n-1}{2012}\]

untuk sebarang $x\in \mathbb{R}^+$.

Apabila disubtitusi $x=\frac{1}{n}$, maka diperoleh untuk sebarang bilangan asli $n$

\[f(1)=nf\left(\frac{1}{n}\right)+\frac{n-1}{2012}\]

Berdasarkan Archimedian Property, apabila diberikan bilangan real $K$ maka terdapat bilangan asli $n$ sedemikian sehingga $n>K$.

Berdasarkan Archimedian Property, karena $2012f(1)+1 \in \mathbb{R}^+$ maka terdapat bilangan asli $n$ yang memenuhi

\[n>2012f(1)+1 \Rightarrow \frac{f(1)}{n}-\frac{1}{2012}+\frac{1}{2012n}< 0\]
Sedangkan

\[f\left(\frac{1}{n}\right)=\frac{f(1)}{n}-\frac{1}{2012}+\frac{1}{2012n}< 0\]
kontradiksi. Sehingga tidak ada fungsi yang memenuhi

Soal 7 (Nanang Susyanto) Misalkan $n$ bilangan asli. Buktikan bahwa persamaan
\[\sqrt{x}+\sqrt{y}=\sqrt{n}\] memiliki solusi pasangan bilangan asli $\left( x,y\right) $ jika dan hanya jika $n$ habis dibagi oleh suatu bilangan kuadrat yang lebih besar daripada 1.


Solusi:

Misalkan terdapat bilangan asli $x,y,$ dan $n$ yang memenuhi $\sqrt{x}+\sqrt{y}=\sqrt{n}$, setara dengan $\sqrt{x}=\sqrt{n}-\sqrt{y}$, kuadratkan kedua ruas kita peroleh
\[x=n+y-2\sqrt{yn}\]
yang berarti $yn$ adalah bilangan kuadrat. Secara similar dari $\sqrt{y}=\sqrt{n}-\sqrt{x}$ diperoleh $xn$ adalah bilangan kuadrat.

Misalkan tidak ada bilangan kuadrat yang lebih besar dari $1$ yang membagi $n$, sehingga $n$ berbentuk $p_1p_2\cdots p_k$, dengan $p_i$ bilangan prima. Maka untuk setiap $i$, diperoleh prima $p_i$ membagi $n$, tapi $p_i^2$ tidak membagi $n$. Karena $p_i | xn$ dan $xn$ bilangan kuadrat maka $p_i^2 | xn$, dan dari $p_i^2 \not | n$ kita peroleh $p_i | x$. Secara similar kita juga memperoleh $p_i | y$,

Jadi untuk sebarang bilangan prima $p | n$ diperoleh $p | x$ dan $p | y$, yakni

\[x=(p_1p_2\cdots p_k) a =na \qquad y=(p_1p_2\cdots p_k) b=nb\]
 untuk suatu bilangan asli $a$ dan $b$.

Apabila disubstitusi balik, diperoleh $\sqrt{a}+\sqrt{b}=1$, sehingga salah satu dari $a$ atau $b$ harus nol, kontradiksi.

Untuk sebaliknya, apabila ada $d$ sedemikian sehingga $d^2 | n$, maka $n=kd^2$, sehingga
\[\sqrt{n}=d\sqrt{k}=d-1\sqrt{k} + \sqrt{k}=\sqrt{(d-1)^2 k} + \sqrt{k}\]
jadi terdapat solusi yakni $x=(d-1)^2 k$ dan $y=k$.

Soal 8 (Fajar Yuliawan) Diberikan sebarang segitiga $ABC$ dan garis bagi $\angle BAC$ memotong sisi $BC$ dan lingkaran luar segitiga $ABC$ berturut-turut di $D$ dan $E$. Misalkan $M$ dan $N$ berturut-turut titik tengah $BD$ dan $CE$. Lingkaran luar segitiga $ABD$ memotong $AN$ di titik $Q$. Lingkaran yang melalui $A$ dan menyinggung $BC$ di $D$ memotong garis $AM$ dan sisi $AC$ berturut-turut di titik $P$ dan $R$. Tunjukkan bahwa empat titik $B,P,Q,R$ terletak pada satu garis.

Continue Reading

[Eksplorasi] Soal 1 hari pertama ON MIPA 2011

[Eksplorasi] Soal 1 hari pertama ON MIPA 2011

08:20:00   Olimpiade Matematika, ON MIPA, Univ,

Soal berikut adalah soal ON MIPA tahun 2010 hari pertama soal nomor 1 [dapet dari blog Raja Oktovin ]
Saya tidak hanya akan mencoba membahas soal ini (tapi sedikit memodifikasi/memberi komentar yang berhubungan dengan soalnya, dan akan saya lakukan untuk soal-soal yang lain :D)

Soal 1.  Misalkan $N$ adalah subgroup berhingga dari $G$. Misalkan $G=\langle T \rangle$ dan $N=\langle S \rangle$ dimana $S,T \subseteq G$. Buktikan bahwa $N$ subgroup normal jika dan hanya jika $tSt^{-1} \subseteq N$ untuk setiap $t\in T$.Gunakan definisi: $\langle X \rangle = \{x_1x_2\cdots x_n | x_i \in X\}$

Solusi:
$\Rightarrow$ Misalkan $N$ subgroup normal, maka untuk setiap $s \in S$ diperoleh $s\in N$ sehingga $g s g^{-1} \in N$ untuk setiap $g\in G$, secara khusus karena $T\subset G$ diperoleh $tst^{-1} \in N$ untuk setiap $t\in T$, diperoleh $tSt^{-1} \in N$.

$\Leftarrow$ Misalkan $tSt^{-1} \subseteq N$ untuk setiap $t\in T$. Ambil sebarang $n \in N$ dan sebarang $g\in G$, maka $$n=s_1 s_2 \cdots s_k \qquad g=t_1t_2\cdots t_l$$ dimana $s_i \in S$ dan $t_i\in T$.
Jadi
\begin{align*}gng^{-1} &= \prod_{i=1}^l t_i \prod_{i=1}^k s_i \prod_{i=1}^l t_{l-i+1}^{-1}\\
&= \prod_{i=1}^{l-1}t_i \left(\prod_{j=1}^k t_l s_j t_l^{-1}\right) \prod_{i=2}^l t_{l-i+1}^{-1}
\end{align*}

Berdasarkan sifat tertutup dari $N$ dan karena $t_l s_j t_l^{-1} \in N$ maka  $\left(\prod_{j=1}^k t_l s_j t_l^{-1}\right) \in N$. Sehingga $\prod_{j=1}^k t_l s_j t_l^{-1} = \prod_{i=1}^{k_1} s_i^{(1)}$ dimana $s_i^{(1)}\in S$. Jadi
\begin{align*}
gng^{-1}=\prod_{i=1}^{l-1}t_i \prod_{i=1}^{k_1} s_i^{(1)} \prod_{i=2}^l t_{l-i+1}^{-1}
\end{align*}

Pada perkalian diatas, banyak suku $t_i$ sudah berkurang sebuah. Dengan cara yang serupa, kita dapat mengurangi jumlah suku dari $\prod_{i=1}^{l-1}t_i$  dan $\prod_{i=2}^l t_{l-i+1}^{-1}$ sehingga setelah $l-1$ kali kita peroleh

\[gng^{-1}=t_1 \prod_{i=1}^{k_{l-1}} s_i^{(l-1)} t_1^{-1} = \prod_{i=1}^{k_{l-1}} (t_1 s_i^{(l-1)}t_1^{-1}) \in N\]
terbukti.

Modifikasi

Karena notasi $\langle X \rangle$ biasanya digunakan untuk subgroup terkecil yang memuat $X$, yaitu
\[\langle X \rangle := \bigcap \{H : X \subseteq H \text{ dan $H$ adalah subgroup dari $G$} \} \]
Irisan dari semua subgroup dari $G$ yang memuat $X$.
Definisi ini adalah yang umum digunakan untuk $\langle X \rangle$. Jelas bahwa $X\subseteq \langle X\rangle$, dan apabila $H$ adalah sebarang subgrup yang memuat $X$ maka $\langle X \rangle \subseteq H$.

Cukup natural apabila juga dipertanyakan:

Apabila definisi $\langle X \rangle$ diganti menjadi subgroup terkecil yang memuat $X$, apakah soal tetap benar?

Jawabannya : tidak selalu, lihat counterexample dibawah.

Soal 1 (Modifikasi Pertama).  Misalkan $G$ adalah grup berhingga dan $N$ adalah subgroup dari $G$. Misalkan $G=\langle T \rangle$ dan $N=\langle S \rangle$ dimana $S,T \subseteq G$. Buktikan bahwa $N$ subgroup normal jika dan hanya jika $tSt^{-1} \subseteq N$ untuk setiap $t\in T$.$\langle X \rangle$ adalah subgroup terkecil dari $G$ yang memuat $X$.

Soal 1 (Modifikasi Kedua).  Misalkan $N$ adalah subgroup berhingga dari $G$. Misalkan $G=\langle T \rangle$ dimana $T \subseteq G$. Buktikan bahwa $N$ subgroup normal jika dan hanya jika $tNt^{-1} \subseteq N$ untuk setiap $t\in T$.

$\langle X \rangle$ adalah subgroup terkecil dari $G$ yang memuat $X$.

Pembuktian dari  kiri ke kanan, similar. Jadi berikutnya kita hanya akan membuktikan dari kanan ke kiri. Berikut adalah sebuah lemma yang berkaitan dengan $\langle X \rangle$

(Lemma 1)  Untuk $\langle X \rangle$ adalah subgrup terkecil dari $G$ yang memuat $X$ maka anggota-anggota di $\langle X\rangle$ berbentuk : \[x_1x_2 \cdots x_v\] dimana $x_i \in X$ atau $x_i^{-1}\in X$.

Bukti: 
Misalkan $S$ adalah himpunan yang memuat hasil kali  yang berbentuk $x_1 x_2 \cdots x_v$ dengan $x_i \in X$ atau $x_i^{-1}\in X$. Pertama-tama, kita buktikan bahwa $S$ adalah subgroup dari $G$. Perhatikan bahwa jika $d=x_1 x_2 \cdots x_v$ dan $e=x_1^{\prime} x_2^{\prime} \cdots x_u^{\prime}$ dimana $x_i, x_i^{\prime} \in X$ atau $x_i^{-1},{x_i^{\prime}}^{-1} \in X$
maka
\[de=x_1 x_2 \cdots x_v x_1^{\prime} x_2^{\prime} \cdots x_u^{\prime} \]
jelas memenuhi syarat sebagai anggota $S$, jadi $S$ tertutup.  Kemudian $d^{-1}=x_v^{-1}\cdots x_2^{-1}x_1^{-1}$ memenuhi $x_i^{-1}\in X$ atau $x_i = (x_i^{-1})^{-1} \in X$, sehingga $S$ memenuhi sifat inverse. Jadi $S$ adalah subgroup dari $G$.

Kemudian karena $X \subset S$, maka $S$ adalah suatu subgroup yang memuat $X$, hal ini menyebabkan $\langle X \rangle \subset S$. Kemudian untuk sebarang $s \in S$, maka $s$ adalah perkalian dari anggota-anggota $X$ atau yang inverse nya ada di $X$, yakni $s$ adalah perkalian dari anggota-anggota yang berada di $\langle X \rangle$, karena $\langle X\rangle$ tertutup terhadap perkalian maka $s\in \langle X \rangle$, jadi $S=\langle X\rangle$.

Apabila $G$ grup berhingga maka  $\langle X\rangle$ yang ada di ON MIPA sama dengan yang di Lemma 1.

(Lemma 2)  Apabila $G$ adalah grup berhingga, maka $\langle X \rangle= \{x_1x_2\cdots x_v | x_i \in X\}$ (definisi yang sama dengan soal di ON MIPA)

Bukti : 
Perhatikan bahwa dengan cara yang sama seperti bukti sebelumnya himpunan $S=\{x_1x_2\cdots x_v | x_i \in X\}$ tertutup terhadap operasi pada $G$, dan karena $G$ berhingga, maka $S$ adalah subgroup. Dengan cara yang sama seperti bukti sebelum nya diperoleh $\langle X \rangle=S$.

Dengan Lemma 2 ini, soal modifikasi pertama berubah menjadi soal ON MIPA, dengan demikian soal selesai.

Apabila $G$ tidak berhingga, maka soal modifikasi pertama tersebut salah. Counterexample (diberikan oleh Arturo Magidin)

$G=\langle S \cup \{x\}\rangle$ dimana  $S=\left\{\left.\left(\begin{array}{cc}1 & m\\ 0 & 1\end{array}\right)\in G\ \right|\ m\in\mathbb{Z}\right\}$ dan $x = \left(\begin{array}{cc} 2 & 0\\ 0 & 1\end{array}\right).$ Pada kasus ini $N=S$ dan $tNt^{-1} \subset N$ namun $N$ tidak normal di $G$, karena $x^{-1}\left(\begin{array}{cc}1 & 1\\ 0 & 1\end{array}\right)x \not\in N$.

Untuk soal 1 modifikasi kedua,  kita gunakan Lemma berikut:

(Lemma 3)  Jika $G=\langle T \rangle$ dan $N$ adalah subgroup dari $G$ yang memenuhi $tNt^{-1} = N$ maka $N$ adalah subgroup normal.

Bukti :
Ambil sebarang $g\in G$, maka
\[g=t_1t_2\cdots t_k\]
dimana $t_i\in T$ atau $t_i^{-1}\in T$. Dari hipotesis diperoleh $tNt^{-1}$ mengakibatkan $t^{-1}Nt=N$, jadi untuk setiap $t_i$ (tidak harus di $T$ asalkan inverse nya di $T$) berlaku $t_iNt_i^{-1}=N$. Sehingga untuk setiap $n \in N$ diperoleh
\[gng^{-1}= t_1t_2\cdots \underbrace{(t_k n t_k^{-1})}_{\in N} \cdots t_1^{-1} \in N.\]
Jadi $N$ adalah subgroup normal.

Untuk $N$ subgrup berhingga, maka $t^{-1}Nt \subset N$ akan menyebabkan $t^{-1} Nt = N$ (Bukti untuk fakta ini hampir selalu ada di setiap buku aljabar abstract yang membahas subgroup normal).

Sehingga dengan Lemma 3 dan karena $N$ subgrup berhingga soal 1 modifikasi kedua selesai :D

Continue Reading

IMO Problem-Linear Code-Probabilistic Method

IMO Problem-Linear Code-Probabilistic Method

06:48:00   Olimpiade Matematika, soal-soal,

Yesterday on some studying session, we solved the following Combinatorics Problem which is an IMO 1998 problem 2 day 1.

IMO 1998/2
In a contest, there are $m$ candidates and $n$ judges, where $n\geq 3$ is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most \(k\) candidates. Prove that
\[\frac{k}{m} \geq \frac{n-1}{2n}\]

On my way home from the session, I tried to transform the problem into following statement which might be related to Coding Theory


Given $v_1,v_2,\cdots,v_n$ are all vectors in $\mathbb{F}_2^m$ where $n\geq 3$ is an odd integer. If $k$ is an integer such that

\[k \leq \left\lfloor \frac{(n-1)m}{2n} \right\rfloor\]

then there exist vectors $v_i$ and $v_j$ with $1\leq i < j \leq n$, such that $d_H(v_i,v_j) \leq n-k-1$, where $d_H$ denotes the Hamming Distance on $\mathbb{F}_2^m$
Recall that Hamming Distance gives us the number of different components on two vectors.

To see how the second form is derived, we create an $m \times n$ matrix $A$ where the rows represent the candidates and the columns represent the judges. We assign to this matrix, the $ij$-component as follows:

\[[A]_{ij}= \begin{cases} 1 &\text{If candidate $i$ is accepted by judge $j$} \\\ 0 &\text{If candidate $i$ is rejected by judge $i$}\end{cases}\]

Now denote the $i$-th column vectors of $A$ by $v_i$ which is clearly in $\mathbb{F}_2^m$. The Hamming Distance $d_H(v_j,v_i)$ represents the number of different result obtained by judge $i$ compared to judge $j$. Since $v_i \in \mathbb{F}_2^n$, the number of the same results obtained by the pair of judges $i$ and judges $j$ is $n-d_H(v_j,v_i)$

By IMO 1998 problem, if the above quantity is known to be at most $k$ for every pairs $(v_i,v_j)$ then the inequality $\frac{k}{m} \geq \frac{n-1}{2n}$ holds. The contraposition of this statement asserts that:

If the inequality $\frac{k}{m} \geq \frac{n-1}{2n}$ failed to hold then there exist at least one pairs $(v_i,v_j)$ such that $n-d_H(v_j,v_i)$ is greater than $k$. Which is simplified to

If $k \leq \left\lfloor \frac{(n-1)m}{2n} \right\rfloor$ then $d_H(v_j,v_i) \leq n-k-1$.

Next we will use the standard notation of Linear Code in Coding Theory which is $(n,k,d)$ and immediately deduce the following Corollary

Corollary

For any odd integers $k\geq 3$ and integers $n$, there is no linear code $(n,k,d)$ whenever $d > \frac{2k^2-kn+n}{2k}$.

Proof : If such a code exists, then $d > \frac{2k^2-kn+n}{2k}$ implies $k-d < \frac{-n+kn-2k^2 + 2k^2}{2k} = \frac{n(k-1)}{2k}$ thus there exists two vectors $v_j$ and $v_i$ on $\mathbb{F}_2^n$ with $ d_H (v_i , v_j )< k-( k- d) = d$. Contradiction, since $d$ is the minimum distance.

The Official Solution can be found on IMO Compendium Book.

We can also prove this by Probabilistic Method which is a powerful method for proving existence (see The Probabilistic Method by Noga Alon & Joel H. Spencer)

Solution:

Take two judges randomly and uniformly, let $X$ be a random variable which count the number of times the random pairs of judges agree. We wish to prove the contraposition, that is whenever $\frac{k}{m} < \frac{n-1}{2n}$ then $X$ is greater than $k$, with positive probability (i.e $\text{Prob}(X > k) > 0$).

For, $i=1,2,\cdots,m$, let $X_i$ be the $\{0,1\}$-valued random variable which represent wether or not the candidates $i$ being agreed by the pair of judges. Here $X_i=1$ if the pair of judges agree and $0$ otherwise. Thus we have
\[X=X_1+\cdots+X_m\]
taking the Expected Value of the both sides and using the linearity of Expected Value, we have
\[E[X]=E[X_1]+\cdots+E[X_m]\]

Next, we calculate $E[X_i]=\sum_{X_i \in \{0,1\} } X_i \cdot \text{Prob}(X_i)$, since $X_i$ only has value $0$ or $1$, we have $E[X_i]=\text{Prob}(X_i=1)$. Let's calculate $\text{Prob}(X_i=1)$, which is the probability that the candidate $i$ being agreed by the pairs of judges. There are ${n \choose 2}$ possible pairs. Suppose that $t_i$ is the number of judges who accept candidate $i$, then $n-t_i$ is the number of judges who reject candidate $i$. The number of pairs of judges who accept $i$ is ${t_i \choose 2}$, and the number of pairs of judges who reject $i$ is ${n-t_i \choose 2}$. The total number of pairs of judges who agree on $i$ is ${t_i \choose 2}+{n-t_i \choose 2}$. And so

$E[X_i]=\text{Prob}(X_i=1) = \frac{{t_i \choose 2}+{n-t_i \choose 2}}{{n\choose 2}}$

Thus

\[E[X]=\sum_{i=1}^m \frac{{t_i \choose 2}+{n-t_i \choose 2}}{{n\choose 2}}\]

We prove that for odd $n$, the inequality ${t_i\choose 2}+{n-t_i \choose 2} \geq \frac{(n-1)^2}{4}$. Indeed, the inequality is equivalent to

\[(n-2t_i)^2 \geq 1 \Rightarrow t_i \leq \frac{n-1}{2} \mbox{ or } t_i \geq \frac{n+1}{2}\]

which is true, since the candidate is either being failed/accepted by at most $\frac{n-1}{2}$ judges or being failed/accepted by at least $\frac{n+1}{2}$.

Using this inequality we have

\[E[X]\geq m \frac{\left(\frac{n-1}{2}\right)^2}{\frac{n(n-1)}{2}} = \frac{m(n-1)}{2n}\]

by hypothesis $\frac{m(n-1)}{2n} > k$, so we have $E[X]>k$, thus $\text{Prob}(X>k) >0$, and hence we are done.

The essence of proof is actually no different with the official proof, which is shorter. But what all I want to rephrase here is the probabilistic method :D

Continue Reading

OSN 2010 hari kedua

OSN 2010 hari kedua

03:41:00   Olimpiade Matematika,

Soal hari kedua sedikit lebih susah dari hari pertama, ini adalah solusi untuk soal-soal hari kedua (keuali soal no 8, dengan alasan yang sama). Untuk solusi untuk soal no 5,  ide awal nya (invariant principle) bukan ide saya sepenuh nya (at the beginning I even didn't understand the problem ^^)


Soal 5. (Hendrata Darmawan) 
Sebanyak $m$ orang anak laki-laki dan $n$ orang anak perempuan $(m> n)$ duduk mengelilingi meja bundar diawasi oleh seorang guru, dan mereka melakukan sebuah permainan sebagai berikut. Mula-mula sang guru menunjuk seorang anak laki-laki untuk memulai permainan. Anak laki-laki tersebut meletakkan sekeping uang logam di atas meja. Kemudian bergiliran searah jarum jam, setiap anak melakukan gilirannya masing-masing. Jika anak tersebut laki-laki, ia menambahkan sekeping uang logam ke tumpukan di atas meja, dan jika anak tersebut perempuan, ia mengambil sekeping uang logam dari tumpukan tersebut. Jika tumpukan di atas meja habis, maka permainan berakhir saat itu juga. Perhatikan bahwa tergantung siapa yang ditunjuk oleh sang guru untuk memulai langkah pertama, maka permainan tersebut bisa  cepat berakhir, atau bisa saja berlangsung paling sedikit $1$ putaran penuh. Jika sang guru menginginkan agar permainan tersebut berlangsung paling sedikit $1$ putaran penuh, ada berapa pilihan anak laki-laki yang dapat beliau tunjuk untuk memulai?

Solusi:

Sebut anak laki-laki pada permainan tersebut jack jika dan hanya jika apabila permainan dimulai dari anak tersebut, maka permainan akan berlangsung setidaknya satu putaran. Anak laki-laki yang tidak demikian disebut non-jack.

Pertama-tama kita pahami maksud soal ini lebih baik, sebanyak $m+n$ orang anak sudah duduk di meja bundar, dan sang guru harus memilih satu orang jack, diantara $m$ orang anak laki-laki tersebut,  yang akan dicari adalah ada beberapa banyak pilihan jack dari $m$ orang anak laki-laki yang ada.

Ambil sebarang jack, kita tinjau apa yang terjadi apabila permainan sudah berlangsung satu putaran, misalkan pada saat putaran terjadi, terdapat $x$ koin di meja. Pada saat itu, $n$ orang anak perempuan telah ikut bermain. Untuk mencari berapa kemungkinan jack yang mungkin, kita lakukan langkah berikut:
Untuk tiap-tiap satu anak perempuan pada permainan, kita keluarkan dari permainan, diikuti dengan tepat satu pemain laki-laki, yang bukan jack  yang memulai permainan.
Hal ini tidak mengubah banyak koin yang ada di meja, dan karena ada $n$ anak perempuan dan $m>n$, maka prosedur ini dapat terus dilakukan hingga tersisa $m-n$ orang anak laki-laki.

Apabila permainan dimulai dari salah satu dari $m-n$ orang anak laki-laki ini, dengan memasukan kembali semua anak perempuan dan anak laki-laki yang telah di keluarkan pada prosedur sebelumnya ke tempatnya semula, kita peroleh bahwa $m-n$ orang anak laki-laki tersebut adalah jack.


Jadi jawaban nya adalah $m-n$.


Soal 6. (Raja Oktovin)
Cari semua bilangan asli $n>1$ demikian sehingga

\[\tau(n)+\varphi(n)=n+1.\]

Dalam hal ini, $\tau(n)$ menyatakan banyaknya bilangan asli yang habis membagi $n$ dan $\varphi(n)$ menyatakan banyaknya bilangan asli yang kurang dari $n$ dan relatif prima terhadap $n$.

Solusi:

Misalkan \[X_n:=\{d \in \mathbb{N} : d | n\}\qquad Y_n:=\{m \in \mathbb{N} : \text{FPB}(m,n)=1\}.\]
Maka $\tau(n)=|X_n|$ dan $\varphi(n)=|Y_n|$, dan kita harus mencari $n$ sehingga $|X_n|+|Y_n|=n+1$. Perhatikan juga bahwa $X_n \cap Y_n = \{1\}$, sehingga $|X_n \cup Y_n|=|X_n|+|Y_n|-1$, dan Jika $n$ adalah bilangan yang memenuhi syarat pada soal maka haruslah \[|X_n \cup Y_n| = n\]

Karena untuk setiap $x\in X_n$ berlaku $1\leq x \leq n$ dan $X_n \subset N_n$ dan $Y_n \subset N_n$ dimana $N_n=\{1,2,\cdots,n\}$. Jadi $X_n \cup Y_n \subset N_n$ dan karena $|X_n \cup Y_n|=n= |N_n|$ maka $X_n \cup Y_n = N_n$.

Misalkan $p$ adalah faktor prima terkecil dari $n$, dan $\alpha$ adalah bilangan asli sehingga $p^{\alpha} | n$ dan $p^{\alpha+1} \not | n$. Jika $p^{\alpha+1}\leq n$ maka $p^{\alpha+1} \in N_n$ sehingga $p^{\alpha+1} \in X_n \cup Y_n$, namun $\text{FPB}(p^{\alpha+1},n) \neq 1$ dan $p^{\alpha+1} \not | n$, jadi tidak mungkin $p^{\alpha+1} \leq n$. Kita peroleh $p^{\alpha+1}>n$, dan karena $p$ adalah bilangan prima terkecil yang membagi $n$, maka haruslah $n=p^{\alpha}$, karena jika ada bilangan prima lain katakanlah $q\neq p$ sedemikian sehingga $q | n$, maka $p^{\alpha}q | n$ mengakibatkan $p^{\alpha}{q}<n<p^{\alpha+1}$, kontradiksi dengan $p$ adalah faktor prima terkecil. Dari $n=p^{\alpha}$ kita peroleh $\tau(n)=\alpha+1$, semua bilangan yang tidak relatif prima dengan $p^{\alpha}$ pasti berbentuk $kp$ dimana $k=1,2,\cdots,p^{\alpha-1}$, jadi ada $p^{\alpha}-p^{\alpha-1}$ bilangan diantara $1$ sampai $p^{\alpha}$ yang relatif prima dengan $p^{\alpha}$, diperoleh $\varphi(n)=p^{\alpha}-p^{\alpha-1}$, dan syarat pada soal menjadi
\[(\alpha+1)+p^{\alpha}-p^{\alpha-1}=p^{\alpha}+1 \Longleftrightarrow \alpha=p^{\alpha-1}\]  
Jadi sekarang akan dicari semua pasangan bilangan $(\alpha,p)$ yang memenuhi $\alpha=p^{\alpha-1}$ dimana $p$ bilangan prima.

Perhatikan bahwa untuk sebarang prima $p$ dan $\alpha=1$, maka persamaan diatas selalu benar, jadi jika $n$ bilangan prima maka persamaan $\tau(n)+\varphi(n)=n+1$ terpenuhi.  Sekarang akan dicari solusi yang bukan bilangan prima.

Jika $\alpha=2$ maka diperoleh $2=p$ sehingga $n=4$, dapat dicek bahwa $\tau(4)+\varphi(4)=5=4+1$. Sekarang misalkan $\alpha \geq 3$, berdasarkan ketaksamaan bernoulli (atau dengan teorema binomial) diperoleh
\[\begin{align*}\alpha&=p^{\alpha-1}\\ &=(1+p-1)^{\alpha-1}\\ &\geq 1+(p-1)(\alpha-1)\\ &=1+(p-1)\alpha-(p-1)\\ &=2+(p-1)\alpha-p\end{align*}\]

dengan tanda samadengan terjadi jika dan hanya jika $\alpha-1=1$ atau $p-1=0$, dimana untuk kasus ini tidak mungkin terjadi. Jadi kita peroleh $\alpha=p^{\alpha-1}$ mengakibatkan $\alpha>2+(p-1)\alpha -p$ yang setara dengan $\alpha(p-2)>\alpha(p-2)$, kontradiksi. Jadi tidak ada solusi untuk $\alpha\geq 3$.

Sehingga bilangan asli $n>1$ yang memenuhi adalah $n=4$ dan $n$ bilangan prima.


Soal 7. (Raja Oktovin)
Misalkan $a$ dan $b$ bilangan real positif. Diberikan polinom $F(x)=x^{2}+ax+b$ dan $G(x)=x^{2}+bx+a$ sehingga semua akar dari polinom $F(G(x))$ dan $G(F(x))$ adalah bilangan real. Buktikan bahwa $a$ dan $b$ lebih dari $6$.

Solusi: 

Dengan memfaktorkan $F(x)$ kita peroleh

\[F(x)=\left[x-\left(\frac{-a+\sqrt{a^2-4b}}{2}\right)\right]\left[x-\left(\frac{-a-\sqrt{a^2+4b}}{2}\right)\right].\]

Jadi

\[F(G(x))=\left[G(x)+\left(\frac{a-\sqrt{a^2-4b}}{2}\right)\right]\left[G(x)+\left(\frac{a+\sqrt{a^2-4b}}{2}\right)\right].\]

Karena $F(G(x))$ harus mempunyai akar real maka $G(x)+\left(\frac{a-\sqrt{a^2-4b}}{2}\right)$ dan $G(x)+\left(\frac{a+\sqrt{a^2-4b}}{2}\right)$ juga harus punya akar real, jadi mempunyai kedua diskriminant persamaan kuadrat diatas harus tak-negatif. Sehingga diperoleh
\[b^2-4\left(\frac{3a}{2}-\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\qquad b^2-4\left(\frac{3a}{2}+\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\]
Tambahkan kedua ketaksamaan diatas kita peroleh
\[b^2\geq 6a\]
Secara similar, dengan menukar peran $a$ dan $b$, dan karena $G(F(x))$ mempunyai akar real diperoleh
\[a^2\geq 6b\]
Jadi $b^4\geq 36a^2 \geq 6b \Rightarrow b^3\geq b \Rightarrow b\geq 6$, secara similar $a^4\geq 36b^2 \Rightarrow a\geq 6.$

Jika $a=6$, karena $a^2 \geq 6b$ diperoleh $36\geq 6b$ jadi kita peroleh $b \leq 6$, sehingga $b=6$. Begitu juga jika $b=6$ maka $a=6$. Namun untuk $a=b=6$, maka $F(G(x))=G(F(x))$ pandang lagi ketaksamaan diskriminant
\[b^2-4\left(\frac{3a}{2}+\frac{\sqrt{a^2-4b}}{2}\right)\geq 0\]
Jika $a=b=6$ maka ketaksamaan diatas setara dengan $-\sqrt{12}\geq 0$ yang jelas salah, jadi diskriminant tidak positif, untuk $a=b=6$, dan disimpulkan $a>6$ dan $b>6$.


Soal 8. (Raja Oktovin)
Diberikan segitiga lancip $ABC$ dengan titik pusat lingkaran luar $O$ dan titik tinggi $H$. Misalkan $K$ sebarang titik di dalam segitiga $ABC$ yang tidak sama dengan $O$ maupun $H$. Titik $L$ dan $M$ terletak di luar segitiga $ABC$ sedemikian sehingga $AKCL$ dan $AKBM$ jajaran genjang. Terakhir, misalkan $BL$ dan $CM$ berpotongan di titik $N$ dan misalkan juga $J$ adalah titik tengah $HK$. Buktikan bahwa bahwa $KONJ$ jajaran genjang.

Solusi:

Continue Reading

OSN 2010 hari pertama

OSN 2010 hari pertama

21:19:00   Olimpiade Matematika, soal-soal,

Sedikit rileks, dengan soal-soal SMA, yang tidak mudah dan lumayan menarik. OSN tahun ini diadakan di Medan. Berikut adalah soal-soal beserta solusi nya (kecuali soal no 2, karena saya kurang begitu paham geometri). Solusi saya tulis sedetil mungkin, agar (menurut pendapat saya) mendapat nilai penuh di OSN untuk masing-masing soal.

Soal 1 (Fajar Yuliawan)
Misalkan $a,b,c$ adalah bilangan asli yang berbeda. Buktikan bahwa barisan \[a+b+c, ab+ac+bc, 3abc\]
tidak mungkin membentuk barisan geometri maupun aritmatika.

Solusi:
Misalkan barisan diatas membentuk barisan geometri, maka berlaku \[3abc(a+b+c)=(ab+ac+bc)^2\]
Misalkan $x=ab$, $y=bc$ dan $z=ac$ maka diperoleh

\[3(xy+yz+xz)=(x+y+z)^2 \Longleftrightarrow \frac{(x-y)^2+(y-z)^2+(x-z)^2}{2} =0.\]

Jadi diperoleh $x=y=z$, atau $ab=bc=ac$, dan karena $a,b,c \neq 0$, diperoleh $a=b=c$, kontradiksi.

Misalkan barisan tersebut membentuk barisan aritmatika, maka

\[a+b+c+3abc=2(ab+ac+bc)\]

persamaan diatas setara dengan

\[b(a-1)(1-c)+c(b-1)(1-a)+a(c-1)(1-b)=0.\]

Perhatikan bahwa karena $a,b,c$ bilangan asli maka

\[k=b(a-1)(1-c) \leq 0 \qquad l=c(b-1)(1-a) \leq 0\] \[m=a(c-1)(1-b) \leq 0.\]

Salah satu dari $k,l$ atau $m$ harus samadengan $0$, karena jika tidak demikian, $0=k+l+m<0+0+0=0$, kontradiksi.

Tanpa mengurangi keumuman, misalkan $k=0$, atau $b(a-1)(1-c)=0$, karena $b \neq 0$, maka $a=1$ atau $c=1$. Jika $a=1$ maka $l=0$ yaitu $k=l=0$, dan jika $c=1$ maka $m=0$ yaitu $k=m=0$ Jadi dapat kita simpulkan setidaknya dua buah  dari variabel $k,l$ atau $m$ samadengan $0$, dan karena $k+l+m=0$ maka $k=l=m=0$. Ini mengakibatkan

 \[b(a-1)(1-c)=0 \qquad a(c-1)(1-b)=0 \qquad c(b-1)(1-a)=0\]

Perhatikan $b(a-1)(1-c)=0$ dan $a(c-1)(1-b)=0$, jika $c\neq 1$ maka diperoleh $a=1$ dan $b=1$ kontradiksi karena $a$ dan $b$ berbeda,  jadi haruslah $c=1$, akan tetapi hal ini menyebabkan $0=c(b-1)(1-a)=(b-1)(1-a)$ yang setara dengan $a=1$ atau $b=1$, atau dengan kata lain salah satu dari $a$ atau $b$ samadengan $c$, kontradikisi karena $a,b$ dan $c$ semua berbeda.

Soal 2 (Fajar Yuliawan)
 Diberikan segitiga lancip $ABC$ dengan $AC>BC$ dan titik pusat lingkaran luar $O$ . Garis tinggi segitiga $ABC$ dari  $C$ memotong  $AB$ dan lingkaran luar segitiga  $ABC$ lagi berturut-turut di titik $D$ dan $E$. Garis melalui $O$ sejajar $AB$ memotong garis  $AC$ di titik $F$. Buktikan bahwa garis $CO$, garis melalui  $F$ tegak lurus $AC$, dan  garis melalui $E$  sejajar  $DO$ bertemu di satu titik.

Solusi:

Soal 3 (Raymond Christoper Sitorus)
Suatu kompetisi matematika diikuti oleh $120$ peserta dari beberapa kontingen. Pada acara penutupan, setiap peserta memberikan $1$ souvenir pada setiap peserta dari kontingen yang sama dan $1$ souvenir pada salah seorang peserta dari tiap kontingen lainnya. Di akhir acara, diketahui terdapat $3840$ souvenir yang dipertukarkan.
Berapa banyak kontingen maksimal sehingga kondisi di atas dapat terpenuhi?


Solusi:
Misalkan banyaknya kontingen adalah $n$, dimana kontingen ke-$i$ mempunyai $x_i$ orang peserta. Kita akan menghitung banyaknya souvenir yang dipertukarkan. Pertama-tama, setiap dua peserta pada satu kontingen pasti melakukan transaksi, dengan demikian pada tiap-tiap  kontingen ke-$i$ terjadi ${x_i\choose 2}$ transaksi.   Jika $a$ memberikan souvenir ke $b$ maka $b$ juga memberikan souvenir pada $a$, jadi setiap transaksi melibatkan dua buah souvenir. Jadi untuk masing-masing kontingen ke-$i$, banyaknya souvenir yang dipertukarkan di dalam satu kontingen adalah $2{x_i\choose 2}=x_i(x_i-1)$, untuk $i=1,2,\cdots,n$. Secara total banyaknya souvenir yang ditukarkan sesama peserta satu kontingen adalah

\[\sum_{i=1}^n x_i(x_i-1)\]

Selanjutnya akan dihitung jumlah souvenir yang ditukarkan antar kontingen. Setiap satu peserta pada kompetisi tersebut memberikan tepat satu souvenir pada tepat satu orang dari tiap kontingen yang lain, dan karena ada $n-1$ buah kontingen yang lain, maka tiap satu peserta memberikan $n-1$ buah souvenir. Karena ada $120$ peserta maka, total souvenir yang ditukarkan keluar kontingen adalah

\[120(n-1)\]

Jadi total souvenir yang dipertukarkan adalah

\[\sum_{i=1}^n x_i(x_i-1)+120(n-1)=3840.\]

Karena $\sum_{i=1}^n x_i =120$ maka

\[\sum_{i=1}^n x_i^2 +120(n-2)=3840 \Longleftrightarrow \sum_{i=1}^n x_i^2 +120n=4080\]

Perhatikan bahwa dengan RMS-AM diperoleh $\sqrt{\frac{\sum_{i=1}^nx_i^2}{n}}\geq \frac{\sum_{i=1}^n x_i}{n}=\frac{120}{n}$, jadi $\sum_{i=1}^n x_i^2 \geq \frac{120^2}{n}$. Diperoleh

\[4080\geq 120n +\frac{120^2}{n} \Longrightarrow 34 \geq n + \frac{120}{n} \Longrightarrow (n-30)(n-4)\leq 0 \] sehingga \[ 4\leq n \leq 30\]

Jadi $n$ maksimal adalah 30.

Sekarang akan ditunjukan bahwa , $n=30$, tercapai. Misalkan $a_{ij}$ menyatakan peserta ke-$i$ dari kontingen ke-$j$.  Jika kontingen dinyatakan sebagai $k_1, k_2, \cdots, k_{30}$, mak $k_i=\{a_{i1},a_{i2},a_{i3},a_{i4}\}$, sehingga $|k_i|=4$. Diperoleh banyak pertukaran souvenir adalah $30 \times 4(4-1)+120(29)=3840$.

Soal 4 (Nanang Susyanto)
Diketahui bahwa  $m $ dan $n$ adalah bilangan-bilangan asli dengan sifat

\[(mn)|(m^{2010}+n^{2010}+n)\]

Buktikan bahwa terdapat bilangan asli  $k$ sehingga $n=k^{2010}$.

Solusi:
Misalkan $d=\text{FPB}(m,n)$. Pertama-tama akan dibuktikan bahwa $d^{2010}|n$. Perhatikan bahwa $m=k d$ untuk suatu $k \in \mathbb{Z}$ dan $n=l d$ untuk suatu $l \in \mathbb{Z}$, jadi

\[d^{2010} k^{2010} + d^{2010} l^{2010} + n =x  kl d^2\]

atau setara dengan
\[\frac{n}{d^2}=x kl-d^{2008}k^{2010}-d^{2008}l^{2010} \in \mathbb{Z}\]

dengan kata lain $d^2 | n$. Apabila benar bahwa $d^i | n$, dimana $2\leq i\leq 2009$, diperoleh $n=l_id^i$ untuk suatu $l_i \in \mathbb{Z}$, sehingga

\[\begin{align*}d^{2010} k^{2010} + d^{2010} l^{2010} + n &= x kl_i d^{i+1} \Leftrightarrow \\ \frac{n}{d^{i+1}} &= x kl_i-d^{2009-i} k^{2010}-d^{2009-i}k^{2010} \in \mathbb{Z}.\end{align*}\]

Dengan demikian $d^i | n \Rightarrow d^{i+1} | n$ untuk $i=2,3,\cdots, 2009$, dan karena diketahui $d^2 | n$ maka $d^3 | n , d^4 | n, \cdots d^{2010} | n$, sehingga diperoleh $d^{2010} | n$.

Misalkan $n=s d^{2010}$, untuk suatu $s \in \mathbb{Z}$. Akan dibuktikan bahwa $s=1$. Kita peroleh

\[\begin{align*}d^{2010} k^{2010} + d^{2010^2} s^{2010} + s d^{2010} &= x m s d^{2010} \Longrightarrow \\ k^{2010}+d^{2009\cdot 2010}s^{2010}+s&=x ms\end{align*}\]

sehingga diperoleh $s | k^{2010}$. Jika $s \neq 1$, maka ada bilangan prima $p$ sehingga $p | s$, dan karena $s | k^{2010}$, maka $p|k^{2010}$, mengakibatkan $p | k$. Ini berarti $m=kd=(pu)d = (pd) u$, untuk suatu $u \in \mathbb{Z}$ dan $n=sd^{2010}=(pv)d^{2010}=(pd)vd^{2009}$ untuk suatu $v \in \mathbb{Z}$, mengakibatkan  $pd | m$ dan $pd | n$, kontradiksi karena $pd>d = \text{FPB}(m,n)$.

Jadi $n=d^{2010}$.

Continue Reading