[OSN 2014] Barisan yang naik-semu

Soal. Diberikan barisan bilangan bulat positif a_1,a_2,\dots yang memenuhi

a_k+a_{\ell}=a_m+a_n

untuk setiap bilangan bulat positif k,\ell,m,n yang memenuhi k \ell = mn. Buktikan bahwa jika p habis membagi q, maka a_p \le a_q.

Solusi. Perhatikan bahwa berlaku a_1+a_{k \ell}=a_k+a_{\ell} untuk setiap bilangan asli k dan a_l. Dengan demikian, berlaku a_{k \ell}  = a_k+a_{\ell} - a_1 untuk setiap bilangan asli $latex  k$ dan \ell. Sekarang, kita tinggal menunjukkan bahwa a_n \ge a_1 untuk setiap bilangan asli n.

Asumsikan, dengan tujuan mencapai kontradiksi, untuk suatu n>1, berlaku a_n < a_1. Perhatikan bahwa dari persamaan di soal, berlaku a_{n^2} = 2a_n - a_1 < a_n. Selanjutnya,

a_{n^3}=a_{n^2}+a_n-a_1 < a_{n^2}

a_{n^4}=a_{n^3}+a_n-a_1<a_{n^3}

dst.

Secara induktif, kita klaim bahwa a_1>a_n>a_{n^2}>a_{n^3}>\dots. Perhatikan bahwa jika benar bahwa a_1>a_n>a_{n^2}>\dots>a_{n^k}, maka akan berlaku juga a_{n^{k+1}}=a_{n^k}+a_n-a_1<a_{n^k}. Sehingga berlaku a_1>a_n>\dots>a_{n^{k+1}}. Namun, tidak mungkin terdapat barisan tak hingga bilangan asli yang turun tegas(*). Jadi, asumsi a_n<a_1 untuk suatu n tidak mungkin. Terbukti bahwa a_n \ge a_1 untuk semua bilangan asli n.

Refleksi. Ketika diskusi memilih soal untuk OSN 2014, saya adalah salah satu yang paling semangat mendukung soal ini supaya terpilih buat OSN 2014. Habis, menurut saya soalnya cantik sekali. Ternyata benar, soalnya  dipilih oleh para pembina waktu itu. Saya kurang tahu ini siapa yang mem-propose soal ini ke OSN. Sepertinya Pak Fajar Yuliawan atau Pak Nanang Susyanto.

Oh ya, terkait materi soal, zaman dulu saya  belum tahu untuk soal OSN seharusnya sesulit apa. Setelah dipikir-pikir, sepertinya  soalnya cukup sulit untuk soal nomor 1 atau 5 karena menggunakan sifat (*) yang biasanya  disebut Fermat’s Method of Infinite Descent. Seharusnya, soal nomor 1 atau 5 untuk soal OSN benar-benar soal “gembira” saja. 🙂

Advertisements
This entry was posted in Uncategorized and tagged , , , , , , . Bookmark the permalink.

One Response to [OSN 2014] Barisan yang naik-semu

  1. loh, ini bukannya masih unyu unyu gitu ya, secara kan masih pakai satu teknik langsung jadi ._.
    beda ama 2015/5 :”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s