OSP 2016 Esai Soal 5

Soal. Diberikan tripel bilangan asli berbeda (x_{0}, y_{0}, z_{0}) yang memenuhi x_{0} + y_{0} + z_{0} = 2016. Setiap jam ke-i, dengan i \geq 1, dibentuk tripel baru
(x_{i}, y_{i}, z_{i}) = (y_{i - 1} + z_{i - 1} - x_{i - 1}, z_{i - 1} + x_{i - 1} - y_{i - 1}, x_{i - 1} + y_{i - 1} - z_{i - 1}).
Tentukan bilangan asli n terkecil sehingga pada jam ke-n pasti ditemukan minimal satu di antara x_{n}, y_{n}, atau z_{n} merupakan bilangan negatif.

Jawaban:

Dari rumus tripel baru, perhatikan bahwa hasil jumlah x_i+y_i+z_i akan selalu sama untuk setiap i \ge 0, yaitu selalu 2016.

Misalkan (x,y,z) adalah tripel sehingga salah satu dari -x+y+z,x-y+z,x+y-z negatif mensyaratkan bahwa x+y+z < 2 \max\{x,y,z\}. Berarti, kita ingin mencari n terkecil sehingga \max\{x_{n-1},y_{n-1},z_{n-1}\} \ge 1009.

Perhatikan bahwa diperoleh juga sifat bahwa

x_i = 2016-2x_{i-1}
y_i = 2016-2y_{i-1}
z_i = 2016-2z_{i-1}.
Definisikan a_i = \max\{x_i,y_i,z_i\} dan b_i=\min\{x_i,y_i,z_i\}, maka dari sifat terakhir, berlaku

a_i = 2016-2b_{i-1}
b_i = 2016-2a_{i-1}.

Jadi, untuk i \ge 2, berlaku sifat

a_i = 2016-2(2016-2a_{i-2})
= 4a_{i-2}-2016.
Misalkan c_i=a_i-672, maka diperoleh c_i=4c_{i-2} untuk setiap i \ge 2. Jadi, berlaku c_{2n}=4^nc_0 dan c_{2n+1}=4^nc_1. Perhatikan bahwa c_0=a_0-672=\max\{x_0,y_0,z_0\}-672 \ge 673-672=1 dan c_1=a_1-672=\max\{x_1,y_1,z_1\}-672=1344-2\min\{x_0,y_0,z_0\} \ge 1344-2 \cdotp 2.

Syarat pada soal ekivalen dengan mencari n terkecil agar dijamin c_{n-1} =a_{n-1}-672\ge 1009-672=337. Akan ditunjukkan bahwa n=10 cukup. Perhatikan bahwa untuk n=10, berlaku c_9=4^4 c_1 \ge 4^4 \cdotp 2 \ge 512 > 337 dan juga c_{10}=4^5 \cdotp c_0 \ge 4^5 \cdotp 1 \ge 1024>337.
Sekarang, kita cukup berikan contoh tripel (x_0,y_0,z_0)  sehingga x_i,y_i,z_i \ge 0 untuk setiap i=1,2,\dots,9.

n x y z
0 671 672 673
1 674 672 670
2 668 672 676
3 680 672 664
4 656 672 688
5 704 672 640
6 608 672 736
7 800 672 544
8 416 672 928
9 1184 672 160
Advertisements

One thought on “OSP 2016 Esai Soal 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