Soal 1 Seleksi tim Indonesia untuk IMC 2019 Day 1

Hai fans,hari ini merupakan hari pertama seleksi IMC 2019 yang mana akan diambil 7-9 orang terbaik untuk mewakili Indonesia dalam ajang International Mathematics Competition di Bulgaria (Jadi keinget tahun lalu hiks). Meskipun saya tidak diundang lagi, disini saya akan mencoba membagikan coretan saya ketika mengerjakan soal hari pertama pada tes kali ini. Berikut ini soalnya.
For \(1\leq r \leq k\), prove combinatorially that :
$$
\binom{n}{k}=\sum_{j=r}^{n+r-k} \binom{j-1}{r-1} \binom{n-j}{k-r}
$$

\(\textbf{Motivasi.}\)

Dimisalkan \(S=\{1,2,\dots,n\}\). Jika dilihat ruas kiri merupakan banyaknya subset $S$ yang mempunyai \(k\) anggota sehingga untuk mendapatkan ruas kanan kita harus mencari cara lain penghitungan banyaknya subset dari \(S\) yang mempunyai \(k\) anggota.

Perhatikan jumlahan di ruas kanan terdiri dari perkalian dua binomial yaitu \(\binom{j-1}{r-1}\) dan \(\binom{n-j}{k-r}\). Hal yang sering dilakukan adalah melihat jumlahan bagian atas dan bagian bawah dari kedua binom, perhatikan \(j-1+n-j=n-1\) dan \(r-1+k-r=k-1\) keduanya merupakan bilangan yang mempunyai selisih satu dengan \(n\) dan \(k\). Karena jumlahan ruas kanan menggunakan \(r\) sebagai titik awal dan binom bagian kiri naik sedangkan bagian kanan turun kita peroleh observasi berikut ini. (Disini barisan binom \( \binom{a_n}{b_n} \) dikatakan naik jika \(a_n \leq a_{n+1} \) dan turun jika \(a_n \geq a_{n+1} \) untuk setiap \(n\) bilangan asli).

• Untuk \(j=r\)
  $$
  \underbrace{1,2,\dots,r-1}_{r-1 ~anggota},r,\underbrace{r+1,\dots,n}_{n-r+1~anggota}
  $$
  
• Untuk \(j=r+1\)
  $$
  \underbrace{1,2,\dots,r}_{r ~anggota},r+1,\underbrace{r+2,\dots,n}_{n-r~anggota}
  $$
  $$\vdots$$
  
• Untuk \(r \leq j \leq n\)
  $$
  \underbrace{1,2,\dots,j-1}_{j-1 ~anggota},j,\underbrace{j+1,\dots,n}_{n-j~anggota}.
  
  $$
  

Sampai sini mungkin sudah terbayang argumen apa yang akan digunakan untuk memperoleh jumlahan pada ruas kanan.

$\textbf{Solusi.}$

Dimisalkan \(S=\{1,2,\dots,n\}\) dan \(1\leq k \leq n\). Misal \(\mathcal{T}=\{A~|~ A \subset S,|A|=k\}\), dipunyai \(|\mathcal{T}|=\binom{n}{k}\). Diambil sebarang \(r\) dengan \(1\leq r \leq k\).

Diambil sebarang himpunan \(A\in \mathcal{T}\). Akan ditentukan cara membentuk $A$, misalkan $A=\{a_1,a_2,\dots,a_k\}$ dengan $a_1 \lt a_2\dots \lt a_k$. Untuk sebarang $1 \leq j \leq n$, jika $a_r=j$ (elemen ke-$r$ dari $A$ adalah $j$) maka tersisa memilih $k-1$ bilangan dari $n-1$ bilangan dengan catatan ada $r-1$ bilangan kurang dari $j$ dan sisanya lebih dari $j$. Untuk memilih anggota \(A\) yang kurang dari \(j\) dapat dipilih \(r-1\) bilangan dari \(j-1\) bilangan yaitu \(\binom{j-1}{r-1}\) cara. Di sisi lain untuk memilih bilangan yang lebih dari \(j\) dapat dipilih \(k-1-(r-1)=k-r\) bilangan dari \(n-j\) bilangan yaitu \(\binom{n-j}{k-r}\) cara. Dengan menggunakan aturan perkalian diperoleh \(\binom{j-1}{r-1} \binom{n-j}{k-r}\) cara membentuk \(A\).

Jika $j \lt r$ maka $\binom{j-1}{r-1}=0$ sebab $j-1 \lt r-1$ (hal ini sesuai dengan kondisi elemen ke-$r$ dari $A$ harus lebih dari sama dengan $r$) dan jika \(j > n+r-k \) berakibat $\binom{n-j}{k-r}=0$ sebab $n-j \lt k-r$ maka total cara untuk membentuk \(A \in \mathcal{T}\) sama dengan
$$
\sum_{j=1}^{n} \binom{j-1}{r-1} \binom{n-j}{k-r}=\sum_{j=r}^{n+r-k} \binom{j-1}{r-1} \binom{n-j}{k-r}.
$$
Terbukti bahwa
$$
\binom{n}{k}=|\mathcal{T}|=
\sum_{j=r}^{n+r-k} \binom{j-1}{r-1} \binom{n-j}{k-r}
$$
\(\blacksquare\)

\(\textbf{PS :}\) Soal ini mirip soal onmipa nasional hari pertama nomor 3. Sayang beribu sayang soal ini harus dikerjakan dengan bukti kombinatorik, mungkin akan lebih seru jika boleh menggunakan metode grid atau snake oil. Saya akan mencoba mengerjakan soal ini dengan grid atau snake oil pada postingan berikutnya insya allah. Oh ya karena saya mengakui kombin saya busuk (red : lemah cupu) jadi jawaban saya disini belum tentu benar dan kepada pembaca diminta mengoreksinya ya wkwk. Kolom komentar di bawah disediakan untuk berdiskusi.