Monday 8 July 2019


Diberikan 200 kotak merah yg berisi masing-masing maksimal 19 bola dan minimal 1 bola dan 19 kotak biru yg masing-masing berisi maksimal 200 bola dan minimal 1 bola.
Diketahui banyak bola biru < banyak bola merah . Buktikkan ada sekelompok kotak merah yg jumlah bolanya sama dengan sekelompok kotak biru.

Soal ini sebenarnya soal yang sama dengan soal Putnam 1993 A4, dan pernah saya kasi (dalam bentuk general) pada pelatihan IMO Indonesia 2017.

Bagi yang pernah membaca buku  Combinatorics dari Pranav (yang dapat diperoleh gratis  disini) , pada awal-awal buku tersebut, terdapat proses heuristic/algoritma  yang sering bisa  diterapkan untuk soal-soal seperti ini, saya biasanya sebut ini "Discrete Intermediate Value Theorem" (meskipun ga fitting sih).

Intinya jika anda  mempunyai barisan $b_1$, $b_2$ , ..., $b_{N}$ dan anda ingin mencari suku pada barisan ini yang sama-dengan nol, maka  saat yang paling rentan terjadi kontradiksi (Pranav bilang unsafe) adalah ketika $b_i$ berpindah dari positif menjadi negatif atau dari negatif menjadi positif.

Mari kita lihat generalisasi dari  soal OSN 2019 no 2;

Mario has $m$ mushrooms and $n$ flowers, their weights when expressed in grams, are all positive integers, and two (mushrooms or  flowers) are not necessarily to have the same weight . It is known that each mushrooms weight no more than $n$ grams, and each flowers weigh no more than $m$ grams. Prove that Mario can choose a non-empty subset of mushrooms and flowers of the same weight. 

Apabila kita menyatakan berat masing-masing mushroom sebagai $a_1$, $a_2$ , ..., $a_m$ dan berat masing-masing flowers  sebagai $b_1$, $b_2$, ..., $b_n$; dimana $1\leq a_i \leq n$  dan $1 \leq b_i \leq m$, maka kita ingin membuktikan bahwa

\[\sum_{j=l_1}^{l_2} b_j = \sum_{i=k_1}^{k_2} a_i \]

Perlu diketahui bahwa jumlah yang sama memang tidak harus berurutan seperti $a_4+a_5+a_6+a_7=b_{10}+b_{11}+b_{12}$, karena bisa saja  "lompat-lompat" seperti $a_5+a_{10}+a_{13} = b_{10}+b_{11}+b_{23}$.

Namun hal ini sebenarnya hanya bergantung pada pelabelan $a_i$'s dan $b_i$'s kita diawal yang masih random, jadi kasus yang "lompat" tersebut sebenarnya bisa jadi kasus yang berurutan apabila diawal kita melakukan pelabelan (peng-indeks-an) yang berbeda.
Biasanya, dalam mengerjakan soal saya menetapkan asumsi pengurutan (seperti WLOG $a_n$ terbesar, dan sebagainya ) ini diakhir-akhir ketika diperlukan sebagai last resort (saya sering anggap itu kartu AS).

Lanjut ke solusi soal no 2;

Untuk setiap $k$, definisikan $A_k = \sum_{j=1}^k a_j$ dan $B_k = \sum_{j=1}^k b_j$, dan kita lihat hasil pengurangan $A_i - B_j$; Soal akan terbukti apabila kita peroleh salah  satu dari hasil berikut:

  • $A_i - B_j =0$  untuk suatu $i$  dan $j$.
  • $A_i - B_j = A_{i^{\prime}} - B_{j^{\prime}}$ untuk suatu $i$, $j$, $i^{\prime}$ dan $j^{\prime}$.
  • $A_i - B_j = A_{i^{\prime}}$ atau $A_i - B_j = -B_{j^{\prime}}$
Untuk menggabungkan dua kondisi terakhir, kita bisa mendefinisikan $A_0 = B_0=0$ sehingga $A_i - B_j = A_{i^{\prime}}$ dapat ditulis menjadi $A_i - B_j = A_{i^{\prime}} - B_0$ dan $A_i - B_j = -B_{j^{\prime}}$ menjadi $A_i - B_j = A_0-B_{j^{\prime}}$; Jadi kondisi kedua dan ketiga bisa digabung.


Karena ada banyak $(i,j)$ maka bisa  kita tulis dalam bentuk tabel:

\begin{align*}
&A_0 - B_0&  & A_0 - B_1&  & A_0 - B_2 & &\cdots & &A_0-B_n& \\
&A_1 - B_0&  &  A_1 - B_1&  & A_2- B_2 & &\cdots & &A_1 -  B_n& \\
&\vdots & &\ddots& &\vdots & &\cdots &&\vdots&\\
&A_m- B_0 & &  A_m-B_1 & & A_m-B_2 & & \cdots & & A_m- B_n
\end{align*}

Kita akan asumsikan bahwa tidak ada satupun entri pada tabel diatas yang  sama-dengan nol (Jika ada soal selesai). Perhatikan bahwa dari kiri ke kanan entri pada tabel diatas monoton turun. Sedangkan dari atas kebawah entri pada tabel nilainya monton naik. Kita sebut baris pertama sebagai baris  ke-0, dan baris terakhir sebagai baris  ke-$m$, begitu juga kolom.

Pada baris ke $m$, dimulai dari $A_m-B_0$ yang bernilai positif dan  nilainya menurun ketika ditelusuri dari kiri  ke kanan sampai pada saat paling minimum di $A_m-B_n$.

Disini kita  akan menggunakan (Kartu As) dengan mengasumsikan WLOG  $A_m < B_n $ (jika $A_m=B_n$ soal langsung selesai.) Asumsi ini diambil, karena kita ingin ada entri yang nol, dan karena disebelah paling kiri entri bernilai positif dan terus menurun ke sebelah kanan maka "chance" mendapat  angka nol, akan lebih tinggi ketika barisan bergerak dari  positif menuju negatif.

Asumsi $A_m < B_n$ otomatis membuat semua entri pada kolom ke $m$ bernilai negatif.

Sekarang kita terapkan argumen dari buku Pranav pada setiap baris.    Karena pada setiap baris, entri berubah dari positif menjadi negatif, maka ada  "unsafe moment"  ketika mereka pertama kali berubah tanda.

Misalkan pada baris ke $j \geq 1$, kita punya $A_{j} -  B_{k_j} > 0$  sedangkan $A_{j}- B_{k_j+1} < 0$.

Perhatikan bahwa $0 < A_j - B_{k_j} < m$, karena jika $A_j - B_{k_j} \geq m$ maka diperoleh

\[b_{k_j+1} = A_j-B_{k_j} -  (A_j - B_{k_j +1}) > m\]
kontradiksi.


Jadi untuk setiap baris kita berhasil mendapatkan entri

\[A_1 - B_{k_1} ,  A_2 - B_{k_2} , \cdots  , A_m -B_{k_m}\]

yang semuanya berada  pada interval $[1,m-1]$, sehingga dengan PigeonHole Principle diperoleh $A_s-B_t = A_{s^{\prime}} - B_{t^\prime}$, dan soal terbukti.


Untuk bukti formal dapat dilihat  dari pdf berikut












Post a Comment: