Soal Olimpiade Matematika Menarik Tentang Permutasi

Hello Sahabat ku semua. Kali ini saya masih ingin membahas problem matematika yang ada di Whatsapp saya.

1. Let $a_1,a_2,\cdots,a_{99}$ be a permutation of $1,2,3,\cdots,99$. Prove that there exist two equal numbers from

$\mid a_1-1\mid ,\mid a_2-2\mid ,\cdots,\mid a_{99}-99\mid$

Pembahasan : Kita artikan ke bahasa Indonesia dulu ya, jadi soalnya itu misalkan $a_1,a_2,\cdots,a_{99}$ merupakan permutasi dari $1,2,3,\cdots,99$. Buat kalian yang belum permutasi silahkan baca baca terlebih dahulu disini. Oke kita lanjut, kita diminta untuk membuktikan bahwa terdapat dua bilangan yang sama dari 

$\mid a_1-1\mid ,\mid a_2-2\mid ,\cdots,\mid a_{99}-99\mid$

Langsung saja kita buktikan ya, kita akan gunakan bukti kontradiksi disini. Yaitu misalkan

$\mid a_1-1\mid ,\mid a_2-2\mid ,\cdots,\mid a_{99}-99\mid$

semuanya berbeda. Perhatikan bahwa $0\leq \mid a_n-n\mid\leq 98$ dimana $n=1,2,3,\cdots,99$. Kemudian karena semuanya berbeda maka

$\begin{align}\mid a_1-1\mid +\mid a_2-2\mid +\cdots+\mid a_{99}-99\mid &=0+1+2+3+\cdots+98\\ &=\frac{99}{2}\times 98\\ &=351\end{align}$

Padahal kita tahu bahwa $a_1,a_2,\cdots,a_{99}$ merupakan permutasi dari $1,2,3,\cdots,99$. Sehingga jelas paritas dari $\mid a_1-1\mid +\mid a_2-2\mid +\cdots +\mid a_{99}-99\mid$ adalah genap. (Kontradiksi)

Jadi, Terbukti bahwa terdapat setidaknya dua bilangan yang sama.