Processing math: 100%

Tuesday, 3 August 2010

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

5 comments

Assalamualaikum
kak 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 ????

Reply

masukin n=sd^{2010} ke persamaan awal (m^{2010}+n^{2010}+n=x (mn))

Reply

oke,, sip..
kak, dapat ide ngambil d=gcd(m,n) dari mana sih..???
makasih..

Reply

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

Reply

oohh,, gitu ya..
oke deh..
makasih banyak ya kak..
ntar kapan-kapan saya tanya2 lagi ya..
wassalam

Reply