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

ShareShare on Facebook

TweetShare on Twitter

Pin ItShare on Pinterest