2009 August | Ivan Wangsa C.L.

Archive for August, 2009

A competition… for free.

2009
08.29

Posted in Mathematics, Quick Update | No Comments »

— English Version —

Indonesian version below this one.

I was just thinking about making a math competition here, in my website. The purpose is to broaden the mathematical skills of everyone.

The problems won’t be too hard, even obvious for some IMO competitor, as this competition act as an inspiration for starters in olympiad.

The language of the competiton will be Indonesian (Bahasa), and English. The problems will be posted at a subdomain of wangsacl.com. However, this is a competition for free and for fun.

This is just an idea, but it will be implemented and created somewhere along this week.

This competition acts as a replacement of a delayed competition created in olimpiade.org.

— Versi Bahasa Indonesia —

Saya baru berpikir untuk membuat sebuah kompetisi matematika olimpiade di sini, di situs ini. Tujuannya adalah untuk memperluas kemampuan matematika semua orang.

Soal-soalnya tidak akan terlalu sulit; bahkan beberapa akan tampak sangat mudah bagi para peserta IMO, karena kompetisi ini bertujuan untuk menginspirasi para peserta olimpiade.

Bahasa yang digunakan adalah bahasa Indonesia dan bahasa Inggris. Soal-soal akan dituliskan di sebuah subdomain pada wangsacl.com. Tetapi, kompetisi ini tidak berhadiah apa-apa, hanyalah kompetisi untuk kesenangan semata.

Saat ini, ini hanyalah sebuah ide, tapi akan diimplementasikan dalam seminggu ke depan.

Kompetisi ini adalah pengganti sebuah kompetisi yang terlambat diadakan.

1 Comment

eRepublik Indonesia

2009
08.19

Posted in eRepublik | 1 Comment »

eRepublik Indonesia - Klik untuk mendaftar

Bergabunglah bersama eRepublik Indonesia!
Sekarang eIndonesia sedang menyerang eUS bersama aliansi PEACE. Akibatnya, Amerika hanya terdiri dari 8 negara bagian sekarang. Kalahkan Amerika di eRepublik!

PS: Kalau mau kerja, coba ke perusahaan saya di sini, mungkin saya bisa bantu

No Comments

Twitter!

2009
08.13

Posted in Others | No Comments »

Tenang, ini bukan blog Matematika doang kok, apalagi yang udah liat postingan di bawah. Serem kan rumus semua?
Sama, saya juga bosen, jadi lupakan rumus.

Pertama-tama…. Gw punya TWITTER! OK, udah lama si, tapi baru di-announce sekarang..
Setelah sekian lama bosan dengan plurk (dan gw tinggal mati itu plurk. Huahahaha), akhirnya gw pun beralih ke Twitter, dengan harapan bisa ngelaporin bom (lo?)
OK, lupakan tentang bom.
BTW, akhir-akhir ini, yang lagi asik adalah mainin Erepublik!
Apaan tuh?
Erepublik itu game yang mensimulasikan kehidupan nyata ke dunia maya (bukan dunia mayat). Jadi lo bisa kerja (tenang, cuma 1 klik tombol doang, ga ada yang nyuruh lo banting tulang demi uang), training jadi tentara (kudu wajib!), bikin koran, perusahaan, dll sampai banyak sekaliii…
Mau join? Join di sini!

12 comments

OSN 2009 – Soal 8

2009
08.09

Posted in OSN 2009, Olimpiade Sains Nasional | 12 Comments »

Soal 8. Diberikan segitiga $\textstyle ABC$ lancip. Lingkaran dalam segitiga $\textstyle ABC$ menyinggung $\textstyle BC,CA,$ dan $\textstyle AB$ berturut-turut di $\textstyle D,E,$ dan $\textstyle F.$ Garis bagi sudut $\textstyle A$ memotong $\textstyle DE$ dan $\textstyle DF$ berturut-turut di $\textstyle K$ dan $\textstyle L$ . Misalkan $\textstyle AA_{1}$ adalah garis tinggi dan $\textstyle M$ titik tengah $\textstyle BC$ .

(a) Buktikan bahwa $\textstyle BK$ dan $\textstyle CL$ tegak lurus garis bagi sudut $\textstyle BAC$ .

(b) Tunjukkan bahwa $\textstyle A_{1}KML$ adalah segiempat talibusur.

Solusi 1.

(a) Misalkan $\textstyle \angle A=\alpha^o,\angle B=\beta^o,\angle C=\gamma^o$ . Misalkan juga $\textstyle AB=c,BC=a,CA=b$ . Tanpa mengurangi keumuman, asumsikan $\textstyle b\geq c$ .

Perhatikan bahwa:

$\angle BIK=\angle IAB+\angle IBA=\frac12(\alpha+\beta)^o$

dan

$\angle BDK=180^o-\angle EDC=180^o-\left(\frac{180^o-\angle ECD}{2}\right)$

$=180^o-90^o+\frac12\gamma^o$

Perhatikan bahwa:

$\angle BIK+\angle BDK=\frac12(\alpha+\beta)^o+90^o+\frac12\gamma^o$

$=90^o+\frac12(\alpha+\beta+\gamma)^o=90^0+\frac12\cdot180^o=180^o$

membuat $\textstyle BIKD$ sebuah segiempat tali busur. Akibatnya, $\textstyle \angle BKI=\angle BDI=90^o$ . Terbukti. Selanjutnya akan dibuktikan $\textstyle \angle CLA=90^o$ .

Perhatikan bahwa:

$\angle CIL=\angle IAC+\angle ICA=\frac12(\alpha+\gamma)^o$

dan

$\angle CDL=\angle BDF=\frac12(180-\angle FBD)^o$

$=\frac12(180-\beta)^o=\frac12(\alpha+\gamma)^o$

Karena $\textstyle \angle CIL=\angle CDL$ , jelas bahwa $\textstyle CIDL$ adalah segiempat tali busur. Akibatnya, $\textstyle \angle CLI=\angle CDi=90^o$ . Terbukti.

(b) Pertama-tama, soal ini akan dipecah menjadi 2 kasus:

(i) $\textstyle A_1K=A_1L$ . Maka, perhatikan bahwa karena $\textstyle BDA_1A$ dan $\textstyle AA_1LC$ segiempat tali busur, $\textstyle \angle A_1KL=\angle ABC$ , dan $\textstyle \angle A_1LK=\angle BCA$ . Akibatnya, $\textstyle \triangle A_1KL \sim\triangle ABC$ . Akibatnya, karena $\textstyle A_1K=A_1L$ , maka $\textstyle AB=AC$ . Jika $\textstyle AB=AC$ , maka titik $\textstyle A_1,K,L,M$ adalah satu titik, yang jelas siklis. Terbukti.

(ii) $\textstyle A_1K\neq A_1L$ .

Kita gunakan lemma untuk membuktikan kasus ini:

Lemma:

$MK=ML$

Bukti 1.

Misalkan $\textstyle B_1$ adalah titik potong $\textstyle BK$ dengan $\textstyle AC$ (atau perpanjangannya), dan $\textstyle C_1$ adalah titik potong $\textstyle C$ dengan $\textstyle AB$ (atau perpanjangannya).

Jelas bahwa $\textstyle BK=B_1K$ , dan $\textstyle CL=C_1L$ . Karena $\textstyle M$ titik tengah $\textstyle BC$ , maka $\textstyle \triangle BKM\sim \triangle BB_1C$ dan $\textstyle \triangle MCL\sim\triangle BCC_1$ . Perhatikan juga, dengan simetri, $\textstyle BB_1CC_1$ adalah trapesium sama kaki, sehingga $\textstyle B_1C=BC_1$ . Maka,

$MK=\frac12B_1C=\frac12BC_1\ML$

Terbukti.

Bukti 2.

Misalkan $\textstyle KM$ memotong $\textstyle CC_1$ di $\textstyle J$ .

Karena $\textstyle BK \parallel CJ$ , dan $\textstyle BM=MC$ , maka $\textstyle \triangle BKM\cong\triangle CJM$ . Akibatnya, $\textstyle MK=MJ$ .

Perhatikan bahwa karena $\textstyle \angle JLK=90^o$ , dan $\textstyle M$ adalah titik tengah $\textstyle JK$ , maka jelas bahwa $\textstyle ML=MJ=MK$ . Terbukti.

Bukti 3.

Buat titik $\textstyle D$ dan $\textstyle E$ , sehingga $\textstyle M$ terletak pada segmen $\textstyle DE$ , $\textstyle B,K,E$ kolinear dan $\textstyle C,D,L$ kolinear, sehingga $\textstyle DE$ tegak lurus $\textstyle BK$ dan $\textstyle CL$ .

Akan dibuktikan $\textstyle MK=ML$ , yang ekivalen dengan $\textstyle M$ terletak pada garis sumbu $\textstyle KL$ . Karena $\textstyle DE\perp BK\perp KL$ , maka $\textstyle DE\parallel KL$ . Karena $\textstyle KE\parallel LD$ , cukup dibuktikan $\textstyle ME=MD$ . Tapi, ini jelas, karena $\textstyle BE\parallel DC$ , dan $\textstyle BM=MC$ , membuat $\textstyle \triangle BEM \cong CDM$ , dan akibatnya, $\textstyle ME=MD$ , yang ekivalen dengan $\textstyle MK=ML$ . Terbukti.

Bukti 4.

Perhatikan bahwa $\textstyle BK=c\sin\frac{\alpha^o}{2}$ , dan $\textstyle CL=b\sin\frac{\alpha^o}{2}$ . Perhatikan juga:

$\angle KBM=\angle ABC-\angle ABK=\beta^o-\left(90^o-\frac{\alpha^o}{2}\right)$

$=\left(\frac12\alpha+\beta-90\right)^o$

dan

$\angle MCL=\angle ACL-\angle ACB=\left(90^o-\frac{\alpha^o}{2}\right)-\gamma^o$

$=\left(90-\frac12\alpha-\gamma\right)^o$

Selanjutnya, perhatikan bahwa:

$MK^2=ML^2$

$\Leftrightarrow BK^2+BM^2-2\cdot BK\cdot BM\cdot\cos \left(\frac12\alpha+\beta-90\right)^o$

$=CL^2+MC^2-2\cdot CL\cdot MC\cdot\cos\left(90-\frac12\alpha-\gamma\right)^o$

$\Leftrightarrow c^2\sin^2\frac{\alpha^o}2-2c\sin\frac{\alpha^o}2\cdot\frac12a\cdot\cos\left(\frac12(\beta-\gamma)\right)^o$

$=b^2\sin^2\frac{\alpha^o}2-2b\sin\frac{\alpha^o}2\cdot\frac12a\cdot\cos\left(\frac12(\beta-\gamma)\right)^o$

$\Leftrightarrow(b^2-c^2)\sin^2\frac{\alpha^o}2=a(b-c)\sin\frac{\alpha^o}2\cos\left(\frac12(\beta-\gamma)\right)^o$

$\Leftrightarrow(b+c)\sin\frac{\alpha^o}2=a\cos\left(\frac12(\beta-\gamma)\right)^o$

Identitas ini akan dibuktikan. Perhatikan bahwa:

$(b+c)\sin\frac{\alpha^o}2=2R(\sin\beta+\sin\gamma)\sin\frac{\alpha^o}{2}$

$=4R\sin\left(\frac{\beta+\gamma}2\right)^o\sin\left(\frac{\beta-\gamma}2\right)^o\sin\frac{\alpha^o}{2}$

$=4R\cos\left(\frac{\alpha^o}{2}\right)\sin\left(\frac{\alpha^o}{2}\right)\cos\left(\frac12(\beta-\gamma)\right)^o$

$=2R\sin\alpha\cos\left(\frac12(\beta-\gamma)\right)^2=a\cos\left(\frac12(\beta-\gamma)\right)^o$

Identitas terbukti.

Berdasarkan lemma di atas, akibatnya, $\textstyle MK=ML$ . Akibatnya, $\textstyle M$ terletak pada garis sumbu $\textstyle KL$ .

Selanjutnya, perhatikan bahwa $\textstyle \angle KA_1M=\angle BAK=\angle CAK=\angle LA_1M$ . Akibatnya, $\textstyle A_1M$ garis bagi $\textstyle \angle KA_1L$ .

Misalkan garis bagi $\textstyle \angle KA_1L$ memotong lingkaran luar $\textstyle \triangle KA_1L$ di $\textstyle X$ . Diketahui bahwa $\textstyle KA_1LX$ adalah segiempat tali busur. Maka, $\textstyle \angle XKL=\angle XA_1L=\angle XA_1K=\angle XLK$ , membuat $\textstyle XK=XL$ , atau $\textstyle X$ ada pada garis sumbu $\textstyle KL$ .

Karena perpotongan garis sumbu $\textstyle KL$ dan garis bagi $\textstyle \angle KA_1L$ hanya 1 (ini disebabkan $\textstyle A_1K\neq A_1L$ ), maka $\textstyle X=M$ . Kesimpulannya, $\textstyle A_1KLM$ merupakan segiempat tali busur.

Dari kedua kasus, dapat disimpulkan bahwa $\textstyle A_1KLM$ merupakan segiempat tali busur. Terbukti.

3 comments

OSN 2009 – Soal 7

2009
08.08

Posted in OSN 2009, Olimpiade Sains Nasional | 3 Comments »

Soal 7. Suatu pasangan bilangan bulat $\textstyle (m,n)$ dikatakan baik bila

$m\mid n^2+n \ \text{dan} \ n\mid m^2+m$

Diberikan sebarang dua bilangan asli $\textstyle a,b>1$ yang relatif prima, buktikan bahwa terdapat pasangan baik $\textstyle (m,n)$ dengan $\textstyle a\mid m$ dan $\textstyle b\mid n$ tetapi $\textstyle a$ tidak membagi $\textstyle n$ dan $\textstyle b$ tidak membagi $\textstyle m$ .

Solusi 1.

Akan dibuktikan ada tak hingga banyaknya pasangan baik yang memenuhi. Pertama-tama, akan dibuktikan Lemma berikut:

Lemma. Untuk sebarang $\textstyle a,b>1$ dengan $\textstyle \text{fpb}(a,b)=1$ , maka ada tak hingga banyaknya bilangan bulat $\textstyle p$ sedemikian sehingga:

$a\mid pb+1 \ \text{dan} \ b\mid pa+1$

Bukti. Perhatikan bahwa bentuk di atas ekivalen dengan:

$pb\equiv -1\mod a \ \text{dan} \ pa\equiv -1\mod b$

Karena $\textstyle \text{fpb}(a,b)=1$ , maka ada $\textstyle p_1,p_2\in\mathbb{Z}$ sedemikian sehingga:

$p_1\equiv -\frac1b\mod a \ \text{dan} \ p_2\equiv-\frac1a\mod b$

Maka, dapat ditarik kesimpulan:

$p\equiv-\frac1b\mod a \ \text{dan} \ p\equiv-\frac1a\mod b$

Menurut Chinese Remainder Theorem, $\textstyle p$ memiliki satu solusi unik dalam modulo $\textstyle ab$ . Misalkan $\textstyle d$ adalah salah satu solusi persamaan modulo di atas. Maka semua solusi $\textstyle p$ adalah berbentuk $\textstyle abq+d$ untuk setiap $\textstyle q\in\mathbb{Z}$ . Akibatnya, ada tak hingga $\textstyle p$ yang memenuhi $\textstyle a\mid pb+1$ dan $\textstyle b\mid pa+1$ . Lemma terbukti.

Ambil salah satu nilai $\textstyle p$ yang memenuhi $\textstyle a\mid pb+1$ dan $\textstyle b\mid pa+1$ . Ambil $\textstyle m=pa,n=pb$ . Didapat fakta-fakta berikut:

$\textstyle a\mid pa$ , atau $\textstyle a\mid m$ .
$\textstyle a\mid pb+1$ . Akibatnya, $\textstyle a\nmid pb$ , atau $\textstyle a\nmid n$ .
$\textstyle b\mid pa+1$ . Akibatnya, $\textstyle b\nmid pa$ , atau $\textstyle b\nmid m$ .
$\textstyle b\mid pb$ , atau $\textstyle b\mid n$ .

Selanjutnya, akan ditunjukkan bahwa $\textstyle (m,n)$ adalah pasangan yang baik. Perhatikan bahwa:

$m\mid n^2+n\Leftrightarrow pa\mid pb(pb+1)$

yang jelas benar, sebab $\textstyle p\mid pb$ , dan $\textstyle a\mid pb+1$ . Perhatikan juga:

$n\mid m^2+m\Leftrightarrow pb\mid pa(pa+1)$

yang jelas benar, sebab $\textstyle p\mid pa$ , dan $\textstyle b\mid pa+1$ .

Dapat ditarik kesimpulan bahwa $\textstyle (m,n)$ adalah pasangan yang baik. Karena kita dapat mengambil tak hingga nilai $\textstyle p$ yang memenuhi Lemma, maka ada tak hingga pasangan baik $\textstyle (m,n)$ yang memenuhi. Terbukti.

1 Comment

OSN 2009 – Soal 6

2009
08.08

Posted in OSN 2009, Olimpiade Sains Nasional | 1 Comment »

Soal 6. Tentukan nilai terkecil yang mungkin dari fungsi

$f(x) = x^{2008}-2x^{2007}+3x^{2006}-4x^{2005}+5x^{2004}+...-2006x^{3}$

$+2007x^{2}-2008x+2009$
untuk sebarang bilangan real $\textstyle x$ .

Solusi 1.

Perhatikan bahwa fungsi ekivalen dengan:

$f(x)=(x-1)^2(x^{2006}+2x^{2004}+3x^{2002}+\cdots+1004)+1005$

$\geq1005$

Artinya, fungsi mencapai nilai minimum ketika $\textstyle x=1$ , yaitu $\textstyle 1005$ .

1 Comment

OSN 2009 – Soal 5

2009
08.08

Posted in OSN 2009, Olimpiade Sains Nasional | 1 Comment »

Soal 5. Di dalam suatu laci terdapat paling banyak 2009 bola yang terdiri dari bola putih dan biru yang tercampur secara acak. Jika dua bola diambil secara acak tanpa pengembalian, maka diketahui probabilitas bahwa terambil keduanya bola warna putih atau keduanya bola warna biru adalah $\textstyle \frac12$ . Berapa banyak maksimum bola putih yang mungkin berada dalam laci sedemikian sehingga pernyataan tentang probabilitas tersebut tetap terpenuhi?

Solusi 1.

Misalkan ada $\textstyle a$ bola putih dan $\textstyle b$ bola biru. Agar dijamin terdapat $\textstyle a$ yang maksimum, maka pastilah $\textstyle a\geq b$ (jika $\textstyle a\leq b$ , maka kita dapat mengganti bola putih dengan bola biru, dan sebaliknya). Maka probabilitas yang diinginkan adalah:

$\frac{{a\choose2}+{b\choose2}}{{a+b\choose2}}=\frac12$

$\frac{\frac{a(a-1)}{2}+\frac{b(b-1)}{2}}{\frac{(a+b)(a+b-1)}{2}}=\frac12$

$\frac{a^2-a+b^2-b}{a^2+ab-a+ab+b^2-b}=\frac12$

$2(a^2+b^2-a-b)=a^2+2ab+b^2-a-b$

$2a^2+2b^2-2a-2b=a^2+2ab+b^2-a-b$

$a^2-2ab+b^2=a+b$

$(a-b)^2=a+b\leq 2009$

Misalkan $\textstyle a+b=k^2\leq 2009$ untuk suatu $\textstyle k\in\mathbb{N}$ . Maka didapat $\textstyle (a-b)^2=k^2\Leftrightarrow a-b=k$ . Maka,

$a=\frac{(a+b)+(a-b)}{2}=\frac{k^2+k}{2}$

Karena kita ingin memaksimalkan $\textstyle a$ , maka nilai $\textstyle k$ harus dimaksimalkan. Akibatnya, kita cukup mencari $\textstyle k$ terbesar sehingga $\textstyle k^2\leq 2009$ , yaitu $\textstyle k=44$ . Maka,

$a=\frac{44^2+44}{2}=\frac{1980}{2}=990$

Maka banyak bola putih maksimum agar pernyataan peluang tersebut tetap terpenuhi adalah $\textstyle 990$ .

No Comments

OSN 2009 – Soal 4

2009
08.08

Posted in OSN 2009, Olimpiade Sains Nasional | No Comments »

Soal 4. Di suatu pulau terdapat 7 kota dan ada jaringan kereta api yang melalui kota-kota tersebut. Setiap segmen rel menghubungkan tepat 2 kota, dan diketahui bahwa setiap kota memiliki paling sedikit 3 segmen ke kota lain. Buktikan bahwa terdapat rute perjalanan kereta api yang mengunjungi 4 kota yang berbeda masing-masing sekali dan kembali ke kota asalnya. (Contoh: rute $\textstyle A - B - C - D - A$ ).

Solusi 1.

Ambil satu kota, sebutlah A. A pasti terhubung dengan minimal 3 kota lain. Misalkan A terhubung dengan $\textstyle B_1,B_2,B_3$ . Dan sebutlah tiga kota sisanya sebagai $\textstyle C_1,C_2,C_3$ . Sebut kumpulan 3 kota pertama sebagai himpunan kota $\textstyle B (B_1,B_2,B_3)$ , dan 3 kota terakhir sebagai himpunan kota $\textstyle C (C_1,C_2,C_3)$

Jika ada $\textstyle k$ sehingga $\textstyle B_iC_k$ dan $\textstyle B_jC_k$ terhubung dengan rel, maka ada rute yang memenuhi, yaitu $\textstyle A-B_i-C_k-B_j-A$ , dan kita selesai.

Jika ada $\textstyle i,j,k$ sehingga $\textstyle B_iB_j$ dan $\textstyle B_jB_k$ terhubung dengan rel, maka rute yang memenuhi adalah $\textstyle A-B_i-B_j-B_k-A$ , dan kita selesai. Asumsikan sebaliknya.

Jika ada satu tipe rel $\textstyle B_iB_j$ , sebutlah $\textstyle B_1B_2$ , maka $\textstyle B_1$ memiliki minimal satu jalur ke himpunan kota $\textstyle C$ , $\textstyle B_2$ memiliki minimal satu jalur ke himpunan kota $\textstyle C$ , dan $\textstyle B_3$ memiliki minimal 2 jalur ke himpunan kota $\textstyle C$ . Maka total ada minimal 4 jalur ke himpunan kota $\textstyle C$ . Tetapi, $\textstyle C$ hanya terdiri dari 3 kota. Menurut prinsip sangkar merpati, pasti ada satu kota yang dihubungkan dengan minimal 2 jalur ke himpunan kota $\textstyle B$ , yaitu ke 2 kota berbeda pada himpunan kota $\textstyle B$ . Maka kita selesai.

Jika ada satu tipe rel $\textstyle B_iB_j$ , maka $\textstyle B_1$ memiliki minimal 2 jalur ke himpunan kota $\textstyle C$ , $\textstyle B_2$ memiliki minimal 2 jalur ke himpunan kota $\textstyle C$ , dan $\textstyle B_3$ memiliki minimal 2 jalur ke himpunan kota $\textstyle C$ . Maka total ada minimal 6 jalur ke himpunan kota $\textstyle C$ . Tetapi, $\textstyle C$ hanya terdiri dari $\textstyle 3$ kota. Menurut prinsip sangkar merpati, pasti ada satu kota yang dihubungkan dengan minimal 2 jalur ke himpunan kota $\textstyle B$ , yaitu ke 2 kota berbeda pada himpunan kota $\textstyle B$ . Maka kita selesai.

Dari semua kasus, dipastikan ada jalur yang memenuhi, dan kita selesai. Terbukti.

Solusi 2.

Misalkan kota-kota itu adalah $\textstyle A$ , $\textstyle B$ , $\textstyle C$ , $\textstyle D$ , $\textstyle E$ , $\textstyle F$ , $\textstyle G$ .
Tanpa mengurangi keumuman, misalkan $\textstyle A$ dan $\textstyle B$ terhubung.
Selanjutnya, perhatikan $\textstyle A$ . Maka $\textstyle A$ dapat memiliki minimal 2 rel ke kota lain. Definisikan $\textstyle X$ dan $\textstyle Y$ terhubung jika ada satu rel kereta api yang menghubungkan keduanya.
Tanpa mengurangi keumuman, $\textstyle A$ terhubung ke $\textstyle C$ dan $\textstyle D$ .
Selanjutnya, perhatikan kota $\textstyle B$ . Ada 2 kemungkinan:

(i) $\textstyle B$ terhubung dengan $\textstyle E$ dan $\textstyle F$ .

Selanjutnya, perhatikan kota $\textstyle D$ . Jika $\textstyle D$ terhubung dengan $\textstyle F$ , kita selesai. Jika $\textstyle D$ terhubung dengan $\textstyle E$ , kita selesai. Maka, tersisa 2 kemungkinan: antara $\textstyle D$ terhubung dengan minimal 2 dari $\textstyle B$ , $\textstyle C$ , atau $\textstyle G$ .

Jika $\textstyle D$ terhubung dengan $\textstyle B$ . Jika $\textstyle D$ terhubung dengan $\textstyle C$ , maka kita selesai. Asumsikan tidak, maka perhatikan $\textstyle C$ . $\textstyle C$ dapat terhubung dengan 2 kota lain. Jika $\textstyle C$ terhubung dengan $\textstyle B, D, E, F$ , maka kita selesai. Karena kota yang tersisa adalah $\textstyle G$ , maka $\textstyle C$ pasti terhubung dengan minimal salah satu dari $\textstyle B,D,E,F$ , dan kita selesai.

Maka, asumsikan $\textstyle D$ terhubung dengan $\textstyle C$ dan $\textstyle G$ .
Selanjutnya, perhatikan $\textstyle E$ dan $\textstyle F$ . Jika $\textstyle F$ terhubung dengan $\textstyle C$ atau $\textstyle D$ , maka kita selesai. Asumsikan tidak. Maka, $\textstyle F$ hanya dapat terhubung dengan minimal 2 dari $\textstyle E,G,A$ . Jika $\textstyle F$ terhubung dengan $\textstyle A$ , dan jika $\textstyle F$ terhubung dengan $\textstyle E$ , maka kita selesai. Asumsikan tidak, maka perhatikan $\textstyle E$ . Jika $\textstyle E$ terhubung dengan $\textstyle C,D,F,A$ , maka kita selesai. Karena kota yang tersisa adalah $\textstyle G$ , maka $\textstyle C$ pasti terhubung dengan minimal salah satu dari $\textstyle C,D,F,A$ , dan kita selesai.

Maka, asumsikan $\textstyle F$ terhubung dengan $\textstyle E$ dan $\textstyle G$ .
Perhatikan $\textstyle G$ . Jika $\textstyle G$ terhubung dengan $\textstyle A$ atau $\textstyle B$ , maka kita selesai, maka asumsikan tidak, maka $\textstyle G$ pasti terhubung dengan $\textstyle C$ dan $\textstyle E$ . Tapi, ini membuat rute $\textstyle G-E-B-F-G$ atau $\textstyle G-C-A-D-G$ , dan kita selesai.

Selanjutnya, perhatikan kasus kedua.

(ii) $\textstyle B$ terhubung dengan $\textstyle D$ dan $\textstyle E$ .

Perhatikan $\textstyle D$ . Jika $\textstyle D$ terhubung dengan $\textstyle C$ dan $\textstyle E$ , maka kita selesai. Maka kota tersisa agar $\textstyle D$ dapat dihubungkan adalah $\textstyle F$ dan $\textstyle G$ . Tanpa mengurangi keumuman, $\textstyle D$ terhubung dengan $\textstyle F$ .

Perhatikan $\textstyle F$ . Jika $\textstyle F$ terhubung dengan $\textstyle E$ , $\textstyle B$ , $\textstyle C$ , ataupun $\textstyle A$ , maka kita selesai. Tetapi, dari $\textstyle F$ harus dibuat minimal 2 rel, sehingga $\textstyle F$ pasti terhubung dengan minimal salah satu dari $\textstyle E,B,C,A$ , dan kita selesai.

Selanjutnya, perhatikan kasus ketiga.

(iii) $\textstyle B$ terhubung dengan $\textstyle C$ dan $\textstyle D$ .

Jelas bahwa $\textstyle A-C-B-D-A$ membentuk hubungan yang kita inginkan. Maka kita selesai.

Dari ketiga kasus, maka telah dibuktikan bahwa pasti ada rute yang diinginkan. Terbukti.

4 comments

OSN 2009 – Soal 3

2009
08.08

Posted in OSN 2009, Olimpiade Sains Nasional | 4 Comments »

Soal 3. Pada segitiga $\textstyle ABC$ , titik-titik $\textstyle D$ , $\textstyle E$ , dan $\textstyle F$ berturut-turut terletak pada segmen $\textstyle BC$ , $\textstyle CA$ , dan $\textstyle AB$ . Nyatakan $\textstyle P$ sebagai titik perpotongan $\textstyle AD$ dan $\textstyle EF$ . Tunjukkan bahwa

$\frac{AB}{AF}\times DC+\frac{AC}{AE}\times DB=\frac{AD}{AP}\times BC$

Solusi 1.

Akan dibagi menjadi 2 kasus.

(a) $\textstyle EF$ sejajar $\textstyle BC$ . Dalam kasus ini, $\textstyle \frac{AB}{AF}=\frac{AC}{AE}=\frac{AD}{AP}$ .

Akibatnya, soal ekivalen dengan:

$DC+DB=BC$

yang jelas benar. Terbukti.

(b) $\textstyle EF$ tidak sejajar $\textstyle BC$ . Misalkan $\textstyle EF$ memotong $\textstyle BC$ di $\textstyle K$ .

Soal dapat diubah menjadi:

$\frac{AB}{AF}\times DC+\frac{AC}{AE}\times DB=\frac{AD}{AP}\times BC$

$\Leftrightarrow DC\cdot\left(1+\frac{BF}{FA}\right)+DB\cdot\left(1+\frac{CE}{EA}\right)=BC\cdot\left(1+\frac{DP}{PA}\right)$

$\Leftrightarrow DC+DC\cdot\frac{BF}{FA}+DB+DB\cdot\frac{CE}{EA}=BC+BC\cdot\frac{DP}{PA}$

$\Leftrightarrow \frac{BF}{FA}\cdot DC+\frac{CE}{EA}\cdot DB=\frac{DP}{PA}\cdot BC\cdots(1)$

Menurut teorema Menelaos:

$\frac{BF}{FA}\cdot\frac{AP}{PD}\cdot\frac{DK}{KB}=1 \ \text{dan} \ \frac{CE}{EA}\cdot\frac{AP}{PD}\cdot\frac{DK}{KC}=1$

$\frac{BF}{FA}=\frac{PD\cdot KB}{AP\cdot DK} \ \text{dan} \ \frac{CE}{EA}=\frac{PD\cdot KC}{AP\cdot DK}$

Substitusikan 2 bentuk di atas ke dalam (1), didapat:

$\frac{PD\cdot KB}{AP\cdot DK}\cdot DC+\frac{PD\cdot KC}{AP\cdot DK}\cdot DB=\frac{PD}{AP}\cdot BC$

$\frac{KB\cdot DC}{DK}+\frac{KC\cdot DB}{DK}=BC$

$KB\cdot DC+KC\cdot DB=BC\cdot DK$

$KB\cdot DC+(KB+BD+DC)\cdot BD=(BD+DC)\cdot(KB+BD)$

$KB\cdot DC+KB\cdot BD+BD^2+BD\cdot DC$

$=BD\cdot KB+DC\cdot KB+BD^2+BD\cdot DC$

yang jelas benar. Akibatnya, pernyataan yang akan dibuktikan benar.

Dari 2 kasus di atas, jelas bahwa pernyataan yang akan dibuktikan benar. Terbukti.

Solusi 2.

Definisikan $\textstyle [XYZ]$ sebagai luas segitiga $\textstyle XYZ$ . Perhatikan bahwa:

$\frac{AD}{AP}\cdot\frac{AB}{AF}\cdot\frac{BC}{BD}=\frac{[ABD]}{[APF]}\cdot\frac{BC}{BD}=\frac{[ABD]}{[APF]}\cdot\frac{[ABC]}{[ABD]}=\frac{[ABC]}{[APF]}$

$\frac{AD}{AP}\cdot\frac{AC}{AE}\cdot\frac{BC}{DC}=\frac{[ADC]}{[APE]}\cdot\frac{BC}{DC}=\frac{[ADC]}{[APE]}\cdot\frac{[ABC]}{[ADC]}=\frac{[ABC]}{[APE]}$

Dari 2 persamaan di atas, didapat:

$\frac{AP}{AD}\left(\frac{AF}{AB}\cdot\frac{BD}{BC}+\frac{AE}{AC}\cdot\frac{DC}{BC}\right)=\frac{[APE]+[APF]}{[ABC]}$

$=\frac{[AEF]}{[ABC]}=\frac{AE\cdot AF}{AB\cdot AC}$

$\frac{AF}{AB}\cdot\frac{BD}{BC}+\frac{AE}{AC}\cdot\frac{DC}{BC}=\frac{AE\cdot AF\cdot AD}{AB\cdot AC\cdot AP}$

$AF\cdot BD\cdot AC+AE\cdot DC\cdot AB=\frac{AE\cdot AF\cdot AD\cdot BC}{AP}$

$\frac{AC}{AE}\cdot BD+\frac{AB}{AF}\cdot DC=\frac{AD}{AP}\cdot BC$
Terbukti.

4 comments

OSN 2009 – Soal 2

2009
08.08

Posted in OSN 2009, Olimpiade Sains Nasional | 4 Comments »

Soal 2. Misalkan untuk setiap bilangan real $\textstyle x$ didefinisikan $\textstyle \left\lfloor x\right\rfloor$ sebagai bilangan bulat terbesar yang lebih kecil atau sama dengan $\textstyle x$ . Diberikan $\textstyle a_{1},a_{2},a_{3},\ldots$ suatu barisan bilangan asli yang memenuhi $\textstyle a_{1}>1$ dan

$\left\lfloor \frac{a_{1}+1}{a_{2}}\right\rfloor =\left\lfloor \frac{a_{2}+1}{a_{3}}\right\rfloor =\left\lfloor \frac{a_{3}+1}{a_{4}}\right\rfloor =\cdots$

Buktikan bahwa

$\left\lfloor \frac{a_{n}+1}{a_{n+1}}\right\rfloor \leq 1,$

untuk setiap bilangan asli $\textstyle n$ .

Solusi 1.

Asumsikan sebaliknya. Misalkan:

$\left\lfloor \frac{a_{n}+1}{a_{n+1}}\right\rfloor>1$

berlaku untuk sebarang $\textstyle n\in\mathbb{N}$ . Akibatnya,

$\frac{a_n+1}{a_{n+1}}>1$

$a_n+1>a_{n+1}$

Karena $\textstyle a_n,a_{n+1}\in\mathbb{N}$ , maka ketaksamaan di atas dapat diperkuat menjadi:

$a_n+1\geq a_{n+1}+1$

$a_n\geq a_{n+1}$

Karena ini berlaku untuk sebarang $\textstyle n\in\mathbb{N}$ , maka:

$a_1\geq a_2\geq a_3\geq\cdots$

Akibatnya, dapat ditemukan suatu nilai $\textstyle k$ sehingga $\textstyle a_k=a_{k+1}=a_{k+2}=\ldots$ . Jika $\textstyle a_k=p>1$ , maka:

$1<\left\lfloor\frac{a_k+1}{a_{k+1}}\right\rfloor=\left\lfloor\frac{p+1}{p}\right\rfloor=\left\lfloor1+\frac1p\right\rfloor=1+\left\lfloor\frac1p\right\rfloor=1$

Kontradiksi. Untuk kasus $\textstyle a_k=1$ , akan digunakan lemma berikut: