Soal OSN 2020 No 4
Diberikan papan catur 2n \times 2n, dimana n\geq 1 bilangan asli. Setiap petak pada papan catur diwarnai dengan salah satu dari n buah warna. Buktikan bahwa terdapat 2 petak yang terletak pada satu baris atau satu kolom yang sama, sedemikian sehingga jika pewarnaan dua petak tersebut ditukar, maka terdapat persegi panjang yang keempat petak pada semua sudutnya memiliki warna yang sama.
Kita akan menggunakan Prinsip Pigeonhole, dan untuk kemudahan, akan direpresentasikan dalam bentuk rataan sebagai berikut:
Jika a_1, a_2, ..., a_n adalah bilangan real sehingga
\frac{a_1+a_2+\cdots+a_n}{n} > K
maka terdapat j \in \{1,2,...,n\} sedemikian sehingga a_j > K.
Sebagai contoh, dengan Pigeonhole biasa, karena kita mempunyai 2n \times 2n = 4n^2 petak dan hanya n buah warna, maka terdapat satu warna yang dipakai sebanyak \geq \frac{4n^2}{n}=4n kali. Untuk bentuk pigeonhole diatas, kita bisa menggunakan argumen seperti berikut:
Misalkan a_i adalah banyak petak yang diwarnai dengan warna ke i. Maka a_1+a_2+\cdots+a_n=4n^2 (semua kotak diwarnai), sehingga
\frac{a_1+a_2+\cdots+a_n}{n} = \frac{4n^2}{n}=4n > 4n-1/2
jadi ada j \in \{1,2,...,n\} sehingga a_j > 4n-1/2, dan karena a_j bilangan asli, diperoleh a_j\geq 4n. Hal ini sama saja dengan mengatakan, ada warna ke-j yang dipakai sebanyak \geq 4n kali.
Sekarang kembali lagi ke soal. Untuk menyelesaikan soal, kita akan pakai warna yang dipakai \geq 4n kali diatas, untuk kemudahan kita sebut saja warna itu, warna hitam. Jadi ada paling sedikit 4n buah petak yang berwarna hitam.
Sebuah pasangan terutut dari petak katakanlah (a,b), kita sebut bagus apabila a dan b terletak pada baris yang sama dan keduanya berwarna hitam. Petak a akan kita sebut absis dari pasangan terurut (a,b) tersebut.
Ambil sebarang baris, katakanlah baris ke-i. Misalkan pada baris ke-i ini ada b_i buah warna hitam (bisa saja b_i=0). Apabila b_i \geq 2 maka kita bisa membuat paling sedikit b_i-1 buah pasangan terurut bagus yang mana tidak ada diantara mereka yang mempunyai absis yang sama. Caranya begini, kita daftarkan semua petak hitam yang ada di baris ke-i secara berurut dari kiri ke kanan, dan beri nama x_1, x_2, ..., x_{b_i} seperti gambar berikut:
Jadi kita bisa membuat pasangan bagus (x_1, x_2), (x_2, x_3), (x_3, x_4), ..., (x_{b_i-1}, x_{b_i}), yaitu ada b_i-1 buah. Kita sebut mereka kandidat dari baris ke-i. Dari sini kita simpulkan banyak kandidat adalah b_i-1, jika b_i \geq 2.
Jika b_i=1 atau b_i=0 maka banyak kandidat adalah 0\geq b_i-1 buah. Sehingga kita simpulkan untuk setiap baris, banyak kandidat pada baris ke-i adalah paling tidak b_i-1 buah dimana b_i adalah banyak petak hitam pada baris ke-i.
Perhatikan bahwa kandidat pada baris yang sama pasti mempunyai absis yang berbeda.
Jadi total kandidat pada papan catur sedikitnya ada
(b_1-1)+(b_2-1)+\cdots+(b_{2n}-1) \geq (b_1+b_2+\cdots+b_{2n})-2n \geq 4n-2n =2n
Sekarang misalkan y_j adalah banyak kandidat diatas yang mempunyai absis di kolom ke-j. Kita peroleh y_{2n}=0 karena tidak ada kandidat yang mempunyai absis di kolom ke-2n, lalu
y_1+y_2+\cdots+y_{2n-1} = \text{banyak kandidat pada papan catur} \geq (b_1-1)+(b_2-1)+\cdots+(b_{2n}-1) \geq 2n
Sehingga
\frac{y_1+y_2+\cdots+y_{2n-1}}{2n-1} \geq \frac{2n}{2n-1}>1
diperoleh terdapat j sehingga y_j > 1, dan karena y_j bulat maka y_j\geq 2.
Jadi ada dua kandidat yang sama-sama mempunyai absis pada kolom ke-j. Sebut saja (a,b) dan (c,d) dimana a dan c berada pada kolom ke-j. Perhatikan petak e yang berada pada kolom yang sama dengan b dan baris yang sama dengan c (dan d), lihat gambar dibawah.
Apabila e berwarna hitam, maka abce adalah segiempat yang kita mau (jika harus menukar warna, tinggal tukar warna petak lain yang bukan a, b, c, d atau e). Jika e mempunyai warna lain, katakanlah hijau, maka kita tukar warna e dan d (dan mereka ini terletak pada baris yang sama), sehingga diperoleh segiempat abce yang memenuhi syarat soal.
Post a Comment: