Soal OSN No 8, Sub-(multi)-himpunan berjumlah nol

Soal OSN No 8, Sub-(multi)-himpunan berjumlah nol

01:13:00  

Diberikan bilangan bulat  $a_1$, $a_2$, ..., $a_{2n}$ yang memenuhi $a_i \in [-n,n]$ dan
\[\sum_{i=1}^{2n} a_i = n+1\]
Buktikan bahwa ada sekelompok dari $a_i$ yang apabila  dijumlahkan akan sama-dengan nol.

Salah satu cara untuk SOAL NO 2 dengan modifikasi, dapat digunakan disini.

Pertama-tama, perhatikan bahwa jika $a_i=0$ untuk suatu $i$, maka soal selesai dengan  mengambil singleton $\{a_i\}$. Jadi asumsikan saja tidak ada $a_i$ yang sama-dengan nol.  Misalkan ada $r$ buah yang negatif, jadi ada $s=2n-r$ buah yang positif.  Asumsikan

\[a_1 \leq a_2 \leq \cdots \leq a_r < 0 < a_{r+1} \leq a_{r+2} \leq \cdots  \leq a_{2n}\]

Definisikan $c_i= |a_i|$ untuk $i=1,2,...,r$,  dan  $b_j = a_{r+j}$ untuk $j=1,2,..., k$.

Maka  kita peroleh  $1\leq c_1,c_2,...,c_{r} \leq  n$ dan $1 \leq b_1,b_2,...,b_{s} \leq n$  dan

\[\sum_{j=1}^{2n}a_i  =n+1 \Longleftrightarrow \sum_{i=1}^{s} b_i - \sum_{j=1}^r c_i = n+1\]

Soalnya jadi ekuivalen dengan  membuktikan bahwa ada sekelompok dari $c_i$ dan sekolompok dari $b_i$ yang hasil penjumlahannya sama.

Seperti  cara no 2,  misalkan $C_0 =B_0 = 0$,  dan $B_k=\sum_{i=1}^k b_i$ dan $C_k = \sum_{i=1}^k c_k$, jadi kita peroleh $C_r - B_s = -(n+1) < 0$, sehingga $C_k  <  B_s$ untuk setiap $k \leq r$.

Jadi untuk setiap $i$,  barisan $C_i$ , $C_{i}-B_1$,  $C_{i}-B_2$, ...,  $C_{i}-B_{s}$ adalah barisan yang monoton turun dari positif menuju negatif. Sehingga  terdapat index $s_i$  sedemikian sehingga

\[C_i - B_{s_i} > 0 \qquad \text{dan} \qquad C_i - B_{s_i+1} < 0\]

dan karena $b_{s_i+1} \leq n$, diperoleh $1 \leq C_i - B_{s_i}  \leq n-1$ untuk  $i=1,2,..,r$.

Namun dari sini kita tidak bisa langsung melakukan PigeonHole Principle seperti pada soal  NO 2,  karena belum tentu $r\geq n$. Jadi  belum tentu bisa disimpulkan  $C_i - B_{s_i} = C_{j}-B_{s_j}$ untuk suatu $i$   dan $j$.

Untuk itu kita bisa menyelesaikan soal dengan menambahkan cara berikut:

Perhatikan bahwa karena $B_s- C_r = n+1$, maka $B_j -  C_r < n+1$ untuk setiap  $1\leq j\leq s-1$.

Untuk $1 \leq k\leq s-1$ pandang barisan

\[ 0 < B_k-C_0,  \qquad  B_{k}-C_1, \qquad  B_k - C_2, \qquad \cdots \qquad B_k - C_r <  n+1 \]

yang merupakan barisan yang mulai dari bilangan bulat positif dan menurun menuju bilangan dibawah $n+1$, misalkan $r_k$ adalah bilangan bulat non-negatif terkecil sedemikian sehingga

\[B_{k} - C_{r_k} < n+1 \]

Perhatikan bahwa $B_{k} - C_{r_k}>0$ karena jika $B_{k} - C_{r_k} \leq 0$, maka $r_k \neq 0$ (karena $B_k - C_0 = B_k$ positif) sehingga diperoleh $B_k - C_{r_k-1} \leq c_{r_k} \leq n < n+$, kontradiksi dengan $r_k$ terkecil.

Jadi kita peroleh $1 \leq B_k - C_{r_k} \leq  n$ untuk $k=1, 2, ..., s-1$.


Sampai saat ini yang telah kita peroleh adalah:

1. $r$ buah blangan berbeda $C_i - B_{s_i}$ ($i=1,2,..,r$) yang berada di interval $[1,n-1]$ 
2. $s-1$ buah bilangan  berbeda $B_k - C_{r_k}$ ($k=1, 2, ..., s-1$ ) yang berada di interval $[1,n]$

Jika $r\geq n$, maka dengan Pigeonhole Principle pada  (1) kita selesai. Jadi  diperoleh $r \leq n-1$. 

Lalu jika $s-1 \geq  n+1$ maka  dengan Pigeonhole Principle pada (2) kita selesai. Jadi diperoleh $s \leq n+1$. 

Namun $2n=s+r  \leq  s+n-1$, sehingga $s \geq n+1$,  jadi kita simpulkan $s=n+1$.  Dan karena semua bilangan  $B_k - C_{r_k}$ harus berbeda semua, maka mereka adalah $1$, $2$, ...,  $n$. 

Perhatikan bahwa $1 \leq b_1 \leq n$, sehingga terdapat $k$ sedemikian sehingga

\[B_k - C_{r_k} =  b_1\]

jadi diperoleh    $c_1 + c_2 +\cdots +c_{r_k} =  b_2 + \cdots +b_k$, terbukti.

Penulisan formal dapat dilihat di link berikut

Continue Reading

Soal No 2, OSN MATEMATIKA 2019, Kotak dan Bola

Soal No 2, OSN MATEMATIKA 2019, Kotak dan Bola

01:33:00  

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

Continue Reading

Soal No 4 , OSN Matematika 2019, Segitiga Kesatuan.

Soal No 4 , OSN Matematika 2019, Segitiga Kesatuan.

23:41:00  

Untuk bilangan asli $N$ dan bilangan asli $x \in \{1,2,..., N^2\}$ yang mempunyai paritas yang sama dengan $N$.  Kita akan sebut kesatuan segitiga dari $\{1,2,...,N^2\} \backslash \{x\}$ sebagai suatu cara untuk membentuk urutan penjumlahan
\begin{align*}

a_1+a_2 &= a_3 \\
a_4+a_5+a_6 &= a_7+a_8 \\
&\, \vdots \\
a_{N^2-2N+1}+\cdots+a_{N^2-N}&=a_{N^2-N+1}+\cdots+a_{N^2-1}
\end{align*}
dimana pada baris ke-$j$ terdapat $j+1$ suku disisi kiri dan $j$ suku disisi kanan. Buktikan bahwa $S(N^2,x)$ selalu ada apabila $x\equiv  N \pmod 2$.

Untuk solusinya, karena  terlalu panjang  untuk ditulis dipost ini, jadi saya ketik di pdf, dan dapat  dilihat pada link berikut

(Solusi Official, Video juga bisa dilihat di youtube)

Kali ini saya akan menunjukkan proses mendapatkan solusi yang sudah saya tulis formal diatas.

Hal pertama yang penting  diperoleh disini adalah, pada $S(N^2,x)$ kita mempunyai $N-1$ buah baris, ini bisa dibuktikan dengan double counting sederhana.

Ketika pertama kali mencoba soal ini, (setelah mencoba  kuli-kuli kasus kecil) saya  berpikir seperti mengerjakan persamaan linear.

Memang "proses linear" seperti mengkalikan semua suku dengan konstanta tidak mengubah tanda samadengan pada semua sistem diatas, namun memperbesar angka yang terlibat dalam segitiga kesatuan. Sebagai contoh jika semua suku dikalikan $2$, maka nanti $N^2$ akan menjadi $2N^2$ yang "kebesaran".

Untungnya apabila kita hanya menambahkan $+1$ pada semua sukunya, maka segitiga diatas tidak banyak berubah, dan masih bisa di kontrol, selanjutnya malah bisa kita modifikasi menjadi $S(N+1,y)$ untuk suatu $y$.

Contoh:

$S(4,2)$ dapat diubah menjadi $S(9,3)$ dengan cara berikut:

Mulai dari $S(4,2)$ yaitu  $1+3=4$, lalu kita grow $+1$ semua sukunya (1 jadi 2, 3 jadi 4, dan 4 jadi 5) dan diperoleh

\[2+4=5 + 1\]

Lalu untuk mengatasi kelebihan angka $+1$ pada kanan, kita dapat menyeimbangkan dengan membuat $+1$ tersebut  menjadi $(a+1)-a$, dimana $a$ salah satu dari angka yang tersisa yaitu  $1$,  $6$, $7$, $8$, $9$. Jadi apabila kita  pilih $a=6$ maka kita tambahkan ke kedua ruas dan diperoleh

\[2+4+6=5+7\]

angka sisanya yaitu $1$, $8$, dan $9$ bisa dijadikan baris pertama yaitu $1+8=9$. Sehingga kita peroleh  $S(9,3)$ yaitu

\begin{align*} 1+8&=9 \\ 2+4+6&=5+7\end{align*}

Contoh lain kita bisa membuat $S(4,2)$ menjadi $S(9,1)$ dengan cara serupa yakni:

\begin{align*}\boxed{1+3=4} \longrightarrow \boxed{2+4=5+1} \underbrace{\longrightarrow}_{\{7,8\}}  \boxed{2+4+7=5+8} \end{align*}
dengan $3+6=9$ diperoleh $S(9,1)$

\begin{align*}
3+6&=9\\
2+4+7&=5+8
\end{align*}

Berikut beberapa contoh hasil  lanjutan diatas:

$S(9,1) \rightarrow S(16,2)$

\begin{align*}
15+1&=16\\
11+4+7&=10+12 \\
13+3+5+8&=14+6+9
\end{align*}


$S(16,2) \rightarrow S(25,1)$

\begin{align*}
22+3&=25 \\
18+16+2&=17+19 \\
20+12+5+8&=11+13+21 \\
23+14+4+6+9&=15+7+10+24\\
\end{align*}


$S(16,16)\rightarrow S(25,25)$

\begin{align*}
23+1&=24\\
17+15+2&=16+18\\
19+3+9+11&=10+12+20 \\
21+4+5+7 +13&=6+8+14+22
\end{align*}


$S(16,16)\rightarrow S(25,21)$

\begin{align*}
24+1&=25\\
22+15+2&=23+16\\
19+3+9+11&=20+10+12 \\
17+4+5+7 +13&=18+6+8+14
\end{align*}

Untuk bukti formal bahwa  prosedur ini selalu dapat dilakukan bisa dilihat pada link berikut

Continue Reading