Monday, January 25, 2021

Home / Matematikamampus / Pertidaksamaan Tukar Menukar (Pembahasan Soal IMO Tahun 1975 Problem A1)

Pertidaksamaan Tukar Menukar (Pembahasan Soal IMO Tahun 1975 Problem A1)

by Admin K on Monday, January 25, 2021 in Matematikamampus

Hai hai semua ^_^ Aye Admin K. Di postingan ini, aye bakal ngebahas tentang salah satu soal IMO. Soal yang bakal aye bahas adalah soal IMO tahun 1975. Yap, soal jadul. Soal ini adalah soal pertidaksamaan bilangan riil. Langsung saja, kita lihat soalnya.

Problem A1

Let $x_1 \geq x_2 \geq ...\geq x_n$ , and $y_1 \geq y_2 \geq ...\geq y_n$ be real numbers. Prove that if $z_i$ is any permutation of the $y_i$ , then:

$\sum_{i=1}^{n}\left ( x_i - y_i \right )^2\leq \sum_{i=1}^{n}\left ( x_i - z_i \right )^2$ .

Terjemahan:

Misalkan $x_1 \geq x_2 \geq ...\geq x_n$ , dan $y_1 \geq y_2 \geq ...\geq y_n$ aadalah bilangan-bilangan riil. Buktikan jika $z_i$ adalah sebarang permutasi dari $y_i$ , maka:

$\sum_{i=1}^{n}\left ( x_i - y_i \right )^2\leq \sum_{i=1}^{n}\left ( x_i - z_i \right )^2$ .

Sebelum menjawab atau membuktikan, mari kita tinjau beberapa contoh sederhana, misal untuk n = 2, n = 3, dan n = 4. Bagi kalian yang tidak perlu atau ingin melihat contoh, kalian bisa skip ke bagian solusi.

Contoh untuk n = 2

Misalkan $x_1 = 9,x_2=-5,y_1=0.22167,y_2=-100$ , maka kita akan peroleh permutasi-permutasi dari $y_i$ adalah

${\color{Red} z_1=y_1=0.22167, z_2 = y_2 = -100}$

dan

${\color{Blue} z_1=y_2 = -100, z_2 = y_1=0.22167}$ .

Jadi, hanya ada dua kemungkinan permutasi. Untuk permutasi yang merah, jelas

$(x_1-y_1)^2+(x_2-y_2)^2=(x_1-z_1)^2+(x_2-z_2)^2$

$\Rightarrow (x_1-y_1)^2+(x_2-y_2)^2\leq (x_1-z_1)^2+(x_2-z_2)^2$

Adapun, untuk permutasi yang biru, perhatikan bahwa

$\sum_{i=1}^{2}\left ( x_i-y_i \right )^2=\left ( x_1-y_1 \right )^2+\left ( x_2-y_2 \right )^2=\left ( 9-0.22167 \right )^2+\left ( -5-(-100) \right )^2$

$\sum_{i=1}^{2}\left ( x_i-y_i \right )^2=9102.0590775889$

Sedangkan,

${\color{Blue} \sum_{i=1}^{2}\left ( x_i-z_i \right )^2=\left ( x_1-z_1 \right )^2+\left ( x_2-z_2 \right )^2=\left ( 9-(-100) \right )^2+\left ( -5-0.22167 \right )^2}$

${\color{Blue} \sum_{i=1}^{2}\left ( x_i-z_i \right )^2=11908.2658375889}$

Perhatikan, jelas bahwa

$\sum_{i=1}^{2}\left ( x_i-y_i \right )^2\leq {\color{Blue} \sum_{i=1}^{2}\left ( x_i-z_i \right )^2}$

Lanjut, ke contoh untuk n = 3

Contoh untuk n = 3

Misalkan $x_1 = 12,x_2=1,x_3=1,y_1=1.2,y_2=-1.5113,y_3=-5.313$ , maka terdapat 3! = 6 cara untuk menentukan $z_i$ . Misalkan $z_1=y_2, z_2=y_1, z_3=y_3$ . Diperoleh

$\sum_{i=1}^{3} \left ( x_i-y_i \right )^2 = \left ( 12-1.2 \right )^2 + \left ( 1-(-1.5113) \right )^2 + \left ( 1-(-5.313) \right )^2=162.80059669$

Sedangkan,

$\sum_{i=1}^{3} \left ( x_i-z_i \right )^2 = \left ( 12-{\color{Blue} (-1.5113)} \right )^2 + \left ( 1-{\color{Blue} 1.2} \right )^2 + \left ( 1-{\color{Blue} (-5.313)} \right )^2=222.44919669$ .

Jadi,

$\sum_{i=1}^{3}\left ( x_i-y_i \right )^2\leq {\color{Blue} \sum_{i=1}^{3}\left ( x_i-z_i \right )^2}$ .

Lanjut, ke contoh terakhir, untuk n = 4.

Contoh untuk n = 4

Misalkan $x_1=14,x_2=7.2,x_3,-5.58,x_4=-36$ , dan $y_1=1.57,y_2=0.67,y_3=0,y_4=-5.87119$ . Selanjutnya, misalkan permutasinya adalah $z_1=y_2, z_2=y_3, z_3=y_4, z_4=y_1$ . Diperoleh

$\sum_{i=1}^{4}\left ( x_i-y_i \right )^2=1136.0273920161$ (silakan hitung sendiri), sedangkan

$\sum_{i=1}^{4}\left ( x_i-z_i \right )^2=1641.1185916161$

Jadi, jelas bahwa

$\sum_{i=1}^{4}\left ( x_i-y_i \right )^2\leq {\color{Blue} \sum_{i=1}^{4}\left ( x_i-z_i \right )^2}$

Nah, seperti itulah contoh-contohnya. Mari kita lanjut ke solusi.

Solusi

Sebelum meninjau secara umum untuk sebanyak n suku, kita tinjau terlebih dahulu untuk jumlahan 2 suku. Perhatikan bahwa, untuk $x'\geq x$ dan $y'\geq y$ , berlaku

$(x-y)^2+(x'-y')^2\leq (x'-y)^2+(x-y')^2$ .

Adapun, buktinya adalah sebagai berikut.

Bukti:

Mengingat $x'\geq x$ , maka $x-x'\geq 0$ adalah bilangan non-negatif. Mengalikan $x-x'$ ke pertidaksamaan $y'\geq y$ tidak merubah tanda, sehingga diperoleh

$(x-x')y\geq (x-x')y'$

Bongkar-bongkar

$xy-x'y\geq xy'-x'y'$

Pindah-pindahin

$-xy'-x'y\geq -x'y'-xy$

Kalikan 2 > 0

$-2xy'-2x'y\geq -2x'y'-2xy$

Tambahkan $x^2 + y^2 + x'^2 + y'^2$ kedua ruas diperoleh

$x^2 + y^2 + x'^2 + y'^2 -2xy'-2x'y\geq x^2 + y^2 + x'^2 + y'^2 -2x'y' - 2xy$

Pindah-pindahin dengan sifat komutatif, kumpulin yang sama

$x^2-2xy' + y'^2 +x'^2-2x'y + y^2 \geq x^2 - 2xy + y^2 + x'^2 -2x'y' + y'^2$

Perhatikan bahwa terbentuk kuadrat-kuadrat sempurna

${\color{Red} x^2-2xy' + y'^2} +{\color{Blue} x'^2-2x'y + y^2} \geq {\color{Purple} x^2 - 2xy + y^2} + {\color{DarkGreen} x'^2 -2x'y' + y'^2 }$

Tinggal difaktorin deh, nanti dapet

${\color{Red} (x-y')^2} +{\color{Blue} (x'-y)^2} \geq {\color{Purple} (x-y)^2} + {\color{DarkGreen} (x'-y')^2 }.\blacksquare$

Nah, terbukti, kan?

Nah, dengan lemma ini, kita bisa membuktikan secara umum untuk n suku. Misalkan $x_1 \geq x_2 \geq ...\geq x_n$ , dan $y_1 \geq y_2 \geq ...\geq y_n$ aadalah bilangan-bilangan riil. Misalkan pula $z_i$ adalah sebarang permutasi dari $y_i$ , tinjau jumlahan berikut.

$\sum_{i=1}^{n}\left ( x_i-z_i \right )^2$

Jika untuk suatu $i<j$ berlaku $z_i\leq z_j$ , maka dengan lemma yang sudah dibuktikan di atas, apabila $z_i$ dan $z_j$ ditukar pada jumlahan tersebut, nilai jumlahan tersebut akan berkurang atau sama. Dengan demikian, apabila urutan dari $z_i$ dikembalikan menjadi $y_i$ maka nilai jumlahan akan terus mengecil dengan aturan penukaran: $y_1$ ditukar ke urutan pertama menggantikan $z_1$ , lanjut ke $y_2$ di urutan kedua, dan seterusnya. Setiap penukaran dapat mengecilkan nilai jumlahan. Dengan demikian terbukti bahwa

$\sum_{i=1}^{n}\left ( x_i-y_i \right )^2\leq \sum_{i=1}^{n}\left ( x_i-z_i \right )^2$ .

Baiklah, sekian postingan dari aye. Semoga bermanfaat dan semoga bisa paham. Kalo ada tambahan, koreksi, atau pertanyaan silakan sampaikan di kolom komentar. Sampai jumpa di postingan selanjutnya. Bye~