OSN 2010 hari kedua
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:
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:
Post a Comment: