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: