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

ShareShare on Facebook

TweetShare on Twitter

Pin ItShare on Pinterest