OSN 2010 hari pertama
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)$.
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}$.
5 comments
Assalamualaikum
Replykak ini Nurul,
mau nanya,
yang kita peroleh
d^{2010}k^{2010} + d^{2010}^2.s^{2010} + s.d^{2010} = xmsd^{2010}
datangnya dari mana ni ????
masukin $n=sd^{2010}$ ke persamaan awal $(m^{2010}+n^{2010}+n=x (mn)$)
Replyoke,, sip..
Replykak, dapat ide ngambil d=gcd(m,n) dari mana sih..???
makasih..
sebenarnya, ada bnyk ide standard kok.. kyk modulo, dan keterbagian.. cm aku mentok disana :p .. trus klo soal2 diophantine multivariable, biasanya cukup membantu klo kita liat gcd nya..
Replyoohh,, gitu ya..
Replyoke deh..
makasih banyak ya kak..
ntar kapan-kapan saya tanya2 lagi ya..
wassalam