MA Hari Pertama

Solusi Soal OSN 2012 Matematika SMA/MA Hari Pertama Soal 1. Buktikan bahwa untuk sebarang bilangan asli a dan b, bilangan n = F P B (a, b) + KP K (a, b) − a − b adalah bilangan bulat genap tak negatif. Solusi. Pertama akan dibuktikan bahwa n adalah bilangan genap. Untuk membuktikan ini, kita akan tinjau 3 kasus: (i). a dan b keduanya ganjil, maka jelas bahwa F P B (a, b) dan KP K (a, b) keduanya ganjil sehingga n genap. (ii). a dan b keduanya genap, maka jelas bahwa F P B (a, b) dan KP K (a, b) keduanya genap sehingga n genap. (iii). a dan b beda paritas (satu genap yang lainnya ganjil), maka F P B (a, b) ganjil dan KP K (a, b) genap sehingga n genap. Sekarang, tinggal dibuktikan bahwa n ≥ 0. Misalkan F P B (a, b) = d maka kita dapat tulis a = dx dan b = dy untuk suatu bilangan asli x dan y dengan F P B (x, y) = 1. Substitusikan ke persamaan yang diberikan kita peroleh n = d + dxy − dx − dy+ ⇔ n = dxy − dx − dy + d ⇔ n = d (x − 1) (y − 1) yang jelas tak negatif karena d > 0, x − 1 ≥ 0, dan y − 1 ≥ 1. (terbukti)

Skema Penilaian: Membuktikan n genap: 3 poin dan n ≥ 0 : 4 poin. Parsial: Setiap kasus (parsial) untuk membuktikan n genap: 1 poin Menyatakan a dan b dalam d, x, dan y : 1 poin Menyatakan n = dxy − dx − dy + d: 1 poin Memfaktorkan: 1 poin Menyimpulkan d ≥ 0 : 1 poin

Soal 2. Diberikan bilangan asli n dan bilangan-bilangan real positif a1 , a2 , . . . , an . Buktikan bahwa (1 + a1 )2 (1 + a2 )3 · · · (1 + an )n+1 ≥ (n + 1)n+1 a1 a2 · · · an dan tentukan kapan kesamaan berlaku. Solusi 1. Dengan menggunakan ketaksamaan AM-GM diperoleh √ 2 (1 + a1 )2 ≥ (2 a1 ) = 22 a1  3  r 3 a2 1 1 a2 3 (1 + a2 ) = + + a2 ≥ 3 3 2 = 33 2 2 2 2 2 .. . n n  r an−1 an−1 1 1 n = nn . (1 + an−1 ) = + ··· + + an−1 ≥ nn n−1 n−1 n−1 (n − 1) (n − 1)n−1 Bila semua ketaksamaan di atas dikalikan diperoleh  
 3 a2  an−1 2 3 n 2 n (1 + a1 ) (1 + a2 ) · · · (1 + an−1 ) ≥ 2 a1 3 2 · · · n = nn a1 a2 · · · an−1 . n−1 2 (n − 1) 1 Kesamaan berlaku jika dan hanya jika 1 = a1 , 21 = a2 , . . . , n−1 = an−1 .

Solusi 2. (Induksi Matematika) Untuk n = 1, ketaksamaan benar karena (1 + a1 )2 = 1 + a21 + 2a1 ≥ 2a1 + 2a1 = 4a1 . Asumsikan pernyataan benar untuk suatu bilangan asli n = k − 1, yakni (1 + a1 )2 (1 + a2 )3 · · · (1 + ak−1 )k ≥ k k a1 a2 · · · ak−1 . Akan dibuktikan bahwa (1 + a1 )2 (1 + a2 )3 · · · (1 + ak−1 )k × (1 + ak )k+1 ≥ (k + 1)k+1 a1 a2 · · · ak−1 ak . Berdasarkan hipotesis induksi, diperoleh LHS ≥ k k a1 a2 · · · ak−1 × (1 + ak )k+1 . Jadi, cukup dibuktikan bahwa k k a1 a2 · · · ak−1 × (1 + ak )k+1 ≥ (k + 1)k+1 a1 a2 · · · ak−1 ak atau ekivalen dengan (k + 1)k+1 ak . kk Ketaksamaan terakhir ini dapat diselesaikan dengan AM-GM seperti di solusi official. (1 + ak )k+1 ≥

Skema Penilaian: Membuktikan ketaksamaan: 5 poin • Untuk Solusi 1 Menggunakan Ketaksamaan AM-GM atau sejenisnya untuk satu atau beberapa kasus n: 1 poin Menggunakan Ketaksamaan AM-GM atau sejenisnya untuk kasus 1, 2, . . . , n: 3 poin Memperoleh kesimpulan: 5 poin Perolehan poin di atas tidak ditambahkan. • Untuk Solusi 2 Membuktikan untuk kasus n = 1: 1 poin Mengubah ke masalah ekivalen: 2 poin Memperoleh kesimpulan: 2 poin Perolehan poin di atas ditambahkan. Memperoleh kesamaan: 2 poin • Hanya menebak (dan mengecek): 1 poin • Ditunjukkan cara mendapatkannya: 2 poin

Soal 3. Diberikan segitiga lancip ABC dengan titik pusat lingkaran luar O dan memenuhi AB > AC. Garis BO dan CO memotong garis bagi ∠BAC berturut-turut di titik P dan Q. Selanjutnya, garis BQ dan CP berpotongan di titik R. Buktikan bahwa AR tegak lurus BC. Solusi 1. Misalkan garis bagi ∠BAC memotong BC di titik U dan garis tinggi segitiga ABC dari titik A memotong garis CP di titik S. Yang harus dibuktikan adalah P U , CO dan BS konkuren. Kalau ini terbukti, maka S = R yang berakibat AR tegak lurus BC (karena AS sudah tegak lurus BC)

(1 pt) Pertama, karena AO = BO dan karena AS garis tinggi, maka 180◦ − ∠AOB 180◦ − 2∠ACB = = 90◦ − ∠ACB = ∠CAS. 2 2 Sekarang kembali ke soal, dengan teorema Ceva, cukup ditunjukkan bahwa ∠BAO =

BU CS P O · · = 1. U C SP OB (1 pt) Langkah pertama, dengan teorema garis bagi diperoleh BU AB = . UC AC (2 pts) Langkah kedua, 1 AS · AC · sin ∠CAS CS [ACS] AC · sin ∠CAS = = 21 = . SP [AP S] AP · sin ∠SAP AS · AP · sin ∠SAP 2

(2 pts) Langkah ketiga, dengan cara yang sama, PO AP · sin ∠P AO = . BO AB · sin ∠BAO (1 pt) Terakhir, ∠BAO = ∠CAS dan ∠P AO = ∠SAP , maka BU CS P O AB AC · sin ∠CAS AP · sin ∠P AO · · = · · = 1. U C SP OB AC AP · sin ∠SAP AB · sin ∠BAO Solusi 2. Kita gunakan notasi seperti solusi sebelumnya dan akan dibuktikan bahwa BU CS P O · · = 1. U C SP OB

Misalkan besar sudut-sudut seperti pada gambar. Kita mempunyai BU CS P O AB CS AP P O · · = · · · U C SP OB AC SP AP OB AB CS AP P O · · · = OB AC SP SP sin γ sin α sin θ sin β = · · · sin α sin θ sin β sin γ = 1 seperti yang diinginkan di solusi sebelumnya. Solusi 3. Misalkan garis bagi ∠BAC memotong BC di titik U . Refleksikan titik C terhadap garis AU menghasilkan titik C 0 . Ini berakibat, C 0 terletak di sisi AB dengan AC 0 = AC, C 0 P = CP dan ∠AP C 0 = ∠AP C. Misalkan juga garis AO dan C 0 P berpotongan di S.

Pertama, karena P U, CO, BR konkuren, dengan Teorema Ceva diperoleh BU CR P O · · = 1. U C RP OB Berikutnya, tinjau segitiga BP C 0 dengan transversal yang melalui A, S, O. Dengan Teorema Menelaus diperoleh BA C 0 S P O · · = 1. AC 0 SP OB Terakhir, Teorema Garis Bagi dan fakta AC 0 = AC menghasilkan BU AB AB = = . UC AC AC 0

Kombinasi tiga persamaan di atas menghasilkan CR C 0S = , SP RP sehingga RS sejajar CC 0 . Dengan demikian, S adalah bayangan dari titik R ketika dicerminkan terhadap garis AU . Ini berakibat ∠CAR = ∠BAO = 90◦ − ∠ACB sehingga AR tegak lurus AC.

Soal 4. Diberikan 2012 titik berbeda A1 , A2 , . . . , A2012 di bidang Cartesius. Untuk sebarang permutasi B1 , B2 , . . . , B2012 dari A1 , A2 , . . . , A2012 , didefinisikan bayangan dari titik P terhadap permutasi tersebut sebagai berikut. Titik P dirotasikan 180◦ dengan pusat B1 menghasilkan titik P1 , titik P1 dirotasikan 180◦ dengan pusat B2 menghasilkan titik P2 , ... titik P2011 dirotasikan 180◦ dengan pusat B2012 menghasilkan titik P2012 . Selanjutnya, titik P2012 dikatakan sebagai bayangan dari titik P terhadap permutasi B1 , B2 , . . . , B2012 . Misalkan N adalah banyak bayangan titik P yang berbeda terhadap semua permutasi dari A1 , A2 , . . . , A2012 . Tentukanlah nilai terbesar yang mungkin bagi N .

Solusi. 2012 Jawab: C1006

Misalkan koordinat P adalah (r, s), koordinat Ai adalah (xi , yi ) dan koordinat Bi adalah (pi , qi ). Koordinat P1 adalah (2p1 − r, 2q1 − s) karena B1 merupakan titik tengah dari P P1 . Koordinat P2 adalah (2p2 − 2p1 + r, 2q2 − 2q1 + s) karena B2 merupakan titik tengah dari P1 P 2. ... Koordinat P2012 adalah sebagai berikut: Absisnya adalah r + 2(p2 + p4 + · · · + p2012 ) − 2(p1 + p3 + · · · + p2011 ) Ordinatnya adalah s + 2(s2 + s4 + · · · + s2012 ) − 2(s1 + s3 + · · · + s2011 ) Perhatikan bahwa koordinat P adalah tetap, sehingga faktor utama yang mempengaruhi koordinat P2012 adalah Bi mana yang masuk ke posisi genap dan mana yang masuk ke posisi ganjil. Misalkan B1 , B3 , B5 ditukar-tukar, tidak akan mempengaruhi posisi P2012 . Demikian pula jika B2 , B4 ditukar. Semua Bi ini adalah permutasi dari Ai , sehingga ada 2012 C1006 cara untuk memilih Ai mana yang masuk ke posisi genap, dan sisanya akan masuk ke posisi ganjil. 2012 Kita sudah menunjukkan bahwa ada paling banyak C1006 bayangan P yang mungkin. Kita belum membuktikan bahwa misalnya B1 dan B5 ditukar, maka bayangan yang terbentuk pasti berbeda. 2012 Sekarang akan kita tunjukkan bahwa ada Ai sedemikian sehingga ada tepat C1006 bayangan P yang mungkin. Yakni, jika Bi dan Bj ditukar, di mana i genap dan j ganjil, maka bayangan yang terbentuk pasti berbeda. Buatlah koordinat Ai di (2i , 0) dan koordinat P di (0, 0). Misalkan a1 , . . . , a1006 adalah indeks yang terpilih untuk masuk posisi genap, dan b1 , . . . , b1006 adalah indeks yang terpilih untuk masuk posisi ganjil dalam permutasi Bi . Sekarang, posisi bayangan P tergantung dari jumlah berikut ini:

(2a1 + · · · + 2a1006 ) − (2b1 + · · · + 2b1006 ) = 2(2a1 + · · · + 2a1006 ) − (21 + · · · + 22012 ) Sekarang, nilai dari suku pertama akan tergantung oleh indeks mana saja yang terpilih masuk posisi genap. Jika X = 2a1 + · · · + 2a1006 , maka tinjau representasi biner dari X. Digit-digit yang berisi 1 adalah ai dan digit-digit yang berisi 0 adalah bi . Jika kita memilih indeks yang berbeda untuk masuk ke posisi genap dan ganjil, maka nilai X juga akan terubah, sehingga posisi bayangan P juga berubah. Skema Penilaian: 1. Dapat menentukan absis dan ordinat dari bayangan titik P : 1 poin 2. Sampai dapat menemukan banyak maksimum bayangan dari P yang mungkin: 3 poin 3. Dapat menemukan suatu konstruksi yang dapat menghasilkan bayangan dari P yang 2012 berbeda sebanyak C1006 : 4 poin Jumlah poin dari 1 dan 2 maksimum 3.

Solusi Soal OSN 2012 Matematika SMA/MA Hari Kedua Soal 5. Diberikan bilangan asli m dan n. Misalkan P dan Q adalah dua kumpulan m × n bilangan 0 dan 1 yang disusun dalam m baris dan n kolom. Contoh salah satu kumpulan itu untuk m = 3 dan n = 4 adalah   1 1 1 0    1 1 0 0 . 0 0 0 0 Misalkan kedua kumpulan tersebut memenuhi empat sifat berikut. (i) Pada setiap baris di P , bilangan dari kiri ke kanan tidak pernah naik (boleh sama atau turun), (ii) pada setiap kolom di P , bilangan dari atas ke bawah tidak pernah naik (boleh sama atau turun), (iii) jumlah bilangan pada sebarang baris di P sama dengan jumlah bilangan pada baris yang sama di Q, dan (iv) jumlah bilangan pada sebarang kolom di P sama dengan jumlah bilangan pada kolom yang sama di Q. Tunjukkanlah bahwa bilangan pada baris ke-i kolom ke-j di P sama dengan bilangan pada baris ke-i kolom ke-j di Q untuk setiap i = 1, . . . , m dan j = 1, . . . , n. Solusi. Jika m = 1 atau n = 1, kasus trivial. Selanjutnya asumsikan m, n > 1. Sebutlah kumpulan bilangan bernilai 0 atau 1 berbentuk persegi panjang baik jika pada suatu baris, bilangan-bilangan dari kiri ke kanan tidak pernah naik dan pada suatu kolom, bilanganbilangan dari atas ke bawah tidak pernah naik. Pertama-tama, akan dibuktikan lemma berikut : Lemma : Jika M adalah kumpulan bilangan baik, maka terdapat suatu baris atau suatu kolom pada M yang memiliki bilangan-bilangan yang sama (0 semua atau 1 semua). Bukti Lemma : Andaikan tak ada baris yang semua bilangannya sama semua. Karena bilangan pada satu baris tak pernah naik, haruslah untuk setiap baris, angka paling kiri adalah 1 dan angka paling kanan adalah 0. Dengan demikian, pada kolom paling kiri, semua bilangannya sama, yaitu 1. Terbukti. Kembali ke soal. Misalkan kita punya kumpulan mn bilangan P dan mn bilangan Q berbentuk persegi panjang yang asosiatif. Bilangan-bilangan pada P sudah terisi dan

bilangan-bilangan pada Q belum terisi. Kita akan membuktikan bahwa setiap bilangan pada baris dan kolom tertentu pada Q sama dengan bilangan pada baris dan kolom yang bersesuaian pada P . Jelas bahwa P baik. Menurut Lemma, terdapat baris atau kolom yang semua isinya sama (0 semua atau 1 semua). Tanpa mengurangi asumsi, terdapat baris yang isinya sama (kasus kolom yang isinya sama analog). Bandingkan baris tersebut pada P dan Q. Misal baris itu memiliki k bilangan. Perhatikan bahwa penyelesaian dari a1 + a2 + · · · ak = 0 atau a1 + a2 + · · · ak = k dengan ai = 0, 1 adalah berturut-turut ai = 0 untuk semua i atau ai = 1 untuk semua i. Dengan demikian, isi baris tersebut pada P dan Q adalah sama. Selanjutnya, kita warnai baris tersebut dengan warna hitam. Sekarang kita punya kumpulan bilangan P 0 dan Q0 berbentuk persegi panjang dengan P 0 semuanya terisi dan Q0 kosong. P 0 juga baik. Dengan mengulangi langkah ini (mewarnai suatu baris dengan warna hitam), dalam berhingga banyaknya langkah, semua bilangan pada Q berwarna hitam. Karena pada setiap langkah , kumpulan bilangan yang dihitamkan pada Q persis sama dengan kumpulan bilangan yang dihitamkan pada P , akhirnya kita peroleh bahwa P = Q. Jadi, P hanya asosiatif dengan dirinya sendiri. Skema Penilaian: 1. Dapat menunjukkan bahwa pada P ada baris atau kolom yang semua unsurnya 1 atau 0: 3 poin 2. Menunjukkan langkah awal awal untuk induksi: 1 poin 3. Langkah induksi pada baris saja atau kolom saja: 2 poin 4. Induksi pada jumlah baris dan kolom: 4 poin 5. Induksi tidak formal tetapi jelas: 4 poin Induksi tidak formal tetapi tidak jelas: 3 poin Jumlah poin dari 2 dan (4 atau 5) maksimum 4. Jumlah poin dari 2 dan 3 maksimum 2.

Soal 6. Misalkan R+ menyatakan himpunan semua bilangan real positif. Tunjukkan bahwa tidak ada fungsi f : R+ → R+ yang memenuhi f (x + y) = f (x) + f (y) +

1 2012

untuk setiap bilangan real positif x, y. Solusi 1. Andaikan ada fungsi f yang memenuhi syarat di atas. Untuk x > y, perhatikan bahwa x − y ∈ R+ dan f (x) = f (x − y) + f (y) +

1 1 > f (y) + 2012 2012

sehingga 1 . 2012 Dengan prinsip teleskopis, untuk sebarang bilangan asli n berlaku         1 1 1 f (1) = f (1) − f + f −f + ··· 2 2 3        1 1 1 + f −f +f n n+1 n+1   1 1 1 1 +f > + + ··· + 2012} n+1 |2012 2012{z f (x) − f (y) >

n

n > . 2012 Ini tidak mungkin karena untuk n cukup besar berlaku n > 2012f (1). Jadi pengandaian kita salah dan kesimpulan terbukti. Solusi 2. Andaikan ada fungsi f yang memenuhi syarat di atas. Perhatikan bahwa untuk setiap bilangan real positif x berlaku f (2x) = 2f (x) +

1 2012

1 2 = 3f (x) + 2012 2012 Dari pola ini, mudah dibuktikan dengan induksi bahwa f (3x) = f (2x) + f (x) +

n−1 2012 untuk setiap bilangan asli n dan bilangan real positif x.
Substitusi x = n1 dan karena f n1 ∈ R+ menghasilkan   1 n−1 n−1 + > f (1) = nf n 2012 2012 f (nx) = nf (x) +

untuk setiap bilangan asli n. Namun hal ini tidak mungkin terjadi karena untuk n cukup n−1 besar berlaku 2012 > f (1). Jadi pengandaian kita salah dan kesimpulan pada soal terbukti.

Soal 7. Misalkan n bilangan asli. Buktikan bahwa persamaan √

x+

√

y=

√ n

memiliki solusi pasangan bilangan asli (x, y) jika dan hanya jika n habis dibagi oleh suatu bilangan kuadrat yang lebih besar dari 1. √ √ √ √ √ √ Solusi. Persamaan x + y = n dapat kita tulis menjadi y = n − x. Dengan √ menguadratkan kedua ruas, kita peroleh y = n + x − 2 nx. Dari sini dapat kita simpulkan √ √ bahwa nx bilangan rasional, tetapi n dan x merupakan bilangan asli sehingga nx juga merupakan billangan asli yaitu nx = m2 untuk suatu bilangan asli m. Dari sini diperoleh 2 2 dengan m < n tentunya. (2 poin) solusi x = mn dan y = (n−m) n ⇐=) Perhatikan bahwa jika n habis dibagi oleh suatu bilangan kuadrat yang lebih besar dari 1, katakan p2 maka n = p2 t untuk suatu bilangan asli t. Untuk kasus ini, kita dapat memilih 2 2 m = pt yang jelas m < n dan mn = pptt = p ∈ N, yang artinya ada bilangan asli x dan y yang memenuhi persamaan. (2 poin) =⇒) Andaikan n tidak habis dibagi oleh kuadrat sempurnya lebih besar dari 1 maka n = p1 p2 ...pk untuk suatu bilangan-bilangan prima berbeda p1 , p2 , ..., pk . Kita tahu bahwa solusi dari 2 √ √ 2 √ persamaan x + y = n adalah x = mn dan y = (n−m) dengan m < n. Agar x bulat, n 2 2 haruslah n|m , artinya pi |m untuk setiap i, akibatnya pi |m yang tentu saja berakibat n|m. Hal ini tidaklah mungkin karena m < n. (3 poin)

Soal 8. Diberikan segitiga sebarang ABC dan garis bagi ∠BAC memotong sisi BC dan lingkaran luar segitiga ABC berturut-turut di titik D dan E. Misalkan M dan N berturutturut titik tengah BD dan CE. Lingkaran luar segitiga ABD memotong AN di titik Q. Lingkaran yang melalui A dan menyinggung BC di D memotong garis AM dan sisi AC berturut-turut di titik P dan R. Tunjukkan bahwa empat titik B, P, Q, R terletak pada satu garis. Solusi. Kita gunakan notasi // untuk kesejajaran dua garis dan ∼ untuk kesebangunan dua segitiga. Misalkan K adalah titik potong garis AN dan DR.

Pertama, karena lingkaran luar segitiga ADR menyinggung BC di D dan AD adalah garis bagi ∠BAC, maka ∠CDR = ∠DAR = ∠BAD sehingga ∠ADR = ∠ADC − ∠CDR = (∠ABD + ∠BAD) − ∠BAD = ∠ABD = ∠ABC = ∠AEC sehingga ADR ∼ ABD dan juga DR // EC. Ini berakibat K adalah titik tengah DR (karena N titik tengah EC) sehingga M K // BR (karena M titik tengah BD). Lebih lanjut, karena ADR ∼ ABD, maka ABM ∼ ADK dan AM D ∼ AKR (ini juga karena M titik tengah BD). Akibatnya ∠M AK = ∠M AD + ∠DAK = ∠M AD + ∠BAM = ∠BAD. Karena ∠CDR = ∠BAD, maka AM DK segiempat talibusur. Sekarang misalkan garis BR memotong AM di P 0 dan AN di Q0 . Akan dibuktikan bahwa P 0 = P dan Q0 = Q. Dari M K // BR dan AM DK segiempat talibusur, diperoleh ∠AP 0 R = ∠AM K = ∠ADK = ∠ADR sehingga ARDP 0 segiempat talibusur juga. Dengan kata lain, titik P 0 terletak pada lingkaran luar segitiga ARD dan juga terletak pada garis AM . Disimpulkan bahwa P 0 = P . Dari AM DK segiempat talibusur dan M K // BR diperoleh ∠AQ0 B = ∠AKM = ∠ADM = ∠ADB

sehingga ABDQ0 segiempat talibusur. Dengan kata lain, titik Q0 terletak pada lingkaran luar segitiga ABD dan juga terletak pada garis AN . Disimpulkan bahwa Q0 = Q. Jadi, titik P dan Q terletak pada garis BR atau dengan kata lain, B, P, Q, R terletak pada satu garis. Skema Penilaian: 1. Dapat menunjukkan bahwa ∠ADR = ∠AEC: 1 poin 2. Dapat menunjukkan bahwa DR sejajar EC: 1 poin 3. Dapat menunjukkan bahwa segitiga ABM sebangun dengan segitiga ADK dan segitiga AM D sebangun dengan segitiga AKR: 1 poin 4. Dapat menunjukkan bahwa AM DK adalah segiempat talibusur: 1 poin 5. Dapat menunjukkan bahwa P 0 = P : 1 poin 6. Dapat menunjukkan bahwa Q0 = Q: 1 poin 7. Dapat menunjukkan bahwa titik P dan Q terletak pada garis BR: 1 poin Jumlah poin dari 2 dan (4 atau 5) maksimum 4. Jumlah poin dari 2 dan 3 maksimum 2.