OSN Matematika 2012 Hari Pertama
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}$.
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}$.
1 comments :
:P
Reply