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.