Jump to content
Sign in to follow this  
Louiscahyadi

IMO 2015 Hari Kedua Soal 6

Recommended Posts

Barisan bilangan bulat $a_1, a_2, ...$ memenuhi kondisi - kondisi berikut :


(i) $1 \leq a_j \leq 2015$ untuk setiap $j \geq 1$ ;


(ii) $k + a_k \neq l + a_l$ untuk setiap $1\leq k < l$.


Buktikan bahwa terdapat dua bilangan bulat positif $b$ dan $N$ sehingga $$ \left | \sum_{j=m+1}^{n}(a_j -b) \right | \leq 1007^2$$ untuk setiap bilangan bulat $m$ dan $n$ yang memenuhi $n > m \geq N$.


Share this post


Link to post
Share on other sites

No 6 -nya relatif lebih mudah dari No 5 ... careful estimation ala analysis  works flawlessly :)

 

 

Definisikan $b_i:= a_i + i$. Berdasarkan sifat ii)  $b_i$ adalah bilangan bulat yang berbeda satu sama lain dan dari sifat i) berlaku  \[i \leq b_i \leq s+i.\]


Pertama-tama kita buktikan dulu lemma berikut.

 

Lemma 1
Terdapat himpunan $\mathcal{B} \subset \mathbb{N}$ yang memenuhi $|\mathcal{B}|=b \leq s$ sedemikian sehingga jika $x \in \mathbb{N}$ dan $x \neq b_j$ untuk setiap $j$ maka $x \in \mathcal{B}$.  Dengan kata lain, hanya ada berhingga banyaknya bilangan yang tidak berada pada himpunan $R=\{b_1, b_2,  b_3, \cdots, \}$.

Bukti Lemma:

 

Misalkan tidak demikian, maka ini berarti $R=\{b_1, b_2,  b_3, \cdots, \}=\mathbb{N}$ atau himpunan $\mathcal{B}$ yang demikian mempunyai banyak anggota lebih dari $s$ (bisa saja punya tak berhingga anggota).  Kemungkinan pertama $R=\mathbb{N}$ tidak mungkin karena $1< 1+i \leq a_i + i =b_i$.

Kemudian misalkan  kemungkinan kedua terjadi yaitu $\mathcal{B}$ mempunyai lebih dari $s$ anggota, ini berarti terdapat lebih dari $s$ buah bilangan yang tidak berada di $R$. Misalkan $1=r_1 <  r_2 <  \cdots < r_{s+1}$ adalah $s+1$ buah bilangan pertama yang tidak berada di $R$. Perhatikan bahwa

\[\begin{align*} 2 & \leq b_1 \leq s+1 \\
3 &\leq b_2 \leq s+2 \\
\,  &\,  \cdots \,  \,   \\
r_{s+1} +1 &\leq b_{r_{s+1}} \leq s+r_{s+1}\end{align*} \]

Ini berarti $b_1, b_2, \cdots, b_{r_{s+1}}$ adalah $r_{s+1}$ buah bilangan berbeda yang berada pada interval $[2,s+r_{s+1}]$,  sehingga terdapat $s+r_{s+1}-1 - (r_{s+1})=s-1$ buah bilangan lain yang berada pada interval tersebut,  $s-1$ buah bilangan yang tersisa ini bisa mungkin anggota $R$ bisa juga tidak,  ini berarti pada interval $[2,s+r_{s+1}]$ terdapat paling banyak $s-1$ buah bilangan yang bukan anggota $R$, akan tetapi $r_2, r_3 , \cdots, r_{s+1}$ semuanya juga berada di interval $[2, s+r_{s+1}]$ dan  merupakan $s$ buah bilangan yang juga bukan anggota $R$, kontradiksi. Lemma terbukti.

 

Sekarang kita akan mengestimasi nilai dari jumlah parsial

\[\sum_{j=m+1}^n b_j\]

untuk $m$ cukup besar.

 

Kita notasikan sebagai $\mathcal{N}_j = \{1,2, \cdots, j\}$ . Jelas bahwa $\mathcal{N}_i \subset \mathcal{N}_j$ untuk setiap $i < j$.

Berdasarkan Lemma 1, himpunan $\mathcal{B}$ adalah himpunan yang berhingga, yang mempunyai $b$ buah anggota dimana $b \leq s$. Jadi di himpunan $\mathcal{B}$ terdapat anggota yang paling besar di himpunan tersebut, sebutlah $N$. Dengan demikian, untuk setiap $x \in \mathcal{B}$ selalu berlaku $x \leq N$, sehingga $x \in \mathcal{N}_N$, diperoleh $\mathcal{B}\subseteq \mathcal{N}_N$.

Diperoleh, untuk setiap $n > m \geq N$ maka berlaku \[\mathcal{B} \subseteq \mathcal{N}_N \subseteq \mathcal{N}_m \subset \mathcal{N}_n\]

Lemma 2


Untuk sebarang $v>N$ berlaku
\[\mathcal{N}_{v+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_v\}\subseteq \mathcal{N}_{v+s} \setminus \mathcal{B}.\]

 


Bukti Lemma: 
Misalkan terdapat $x \in \mathcal{N}_{v+1} \setminus \mathcal{B}$  dan $x \neq b_j$ untuk $1 \leq j \leq v$. Karena $x \not \in \mathcal{B}$, maka $x=b_k$ untuk suatu $k$ dan karena $x \neq b_j$ untuk $1\leq j \leq v$  maka haruslah $k>v$, kita simpulkan $x=b_{k}$ dimana $k \geq v+1$. Lalu karena $x \in \mathcal{N}_{v+1}$ diperoleh $x \leq v+1$, jadi
\[v+1 \geq x=b_k \geq k+1 \geq v+2 \]
kontradiksi, jadi terbukti $\mathcal{N}_{v+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_v\}$.
Sekarang ambil sebarang $x \in  \{b_1, b_2 , \cdots, b_v\}$, maka $x \not \in \mathcal{B}$, dan $x=b_k$ untuk suatu $k \leq v$, diperoleh $x=b_k \leq k+s \leq v+s$, jadi $x \in \mathcal{N}_{v+s}$, bersama dengan $x \not \in \mathcal{B}$ dapat disimpulkan bahwa $x \in \mathcal{N}_{v+s}\setminus \mathcal{B}.$ Lemma terbukti.

Lemma 3
Untuk $m>N$ , terdapat tepat  $b-1$ buah bilangan di $\{m+2, m+3, \cdots, m+s\}$ yang merupakan anggota dari $\{b_1, b_2, \cdots, b_m\}$

 

Bukti Lemma :
Dari Lemma 2, karena $m>N$ berlaku $\mathcal{N}_{m+1} \setminus \mathcal{B} \subseteq \{b_1, b_2 , \cdots, b_m\}$, dan karena $|\mathcal{N}_{m+1} \setminus \mathcal{B}| = m+1-b$ dan $|\{b_1, b_2 , \cdots, b_m\}| = m$ maka terdapat tepat $m-(m+1-b)=b-1$ buah suku dari himpunan $\{b_1, b_2 , \cdots, b_m\}$ yang berada pada himpunan $\{m+2, m+3, \cdots, m+s\}$.

 

 

Kita akan menghitung nilai minimum dari $\sum_{j=m+1}^n b_j$. Jumlahan ini dapat ditulis

\[\sum_{j=1}^{n} b_j - \sum_{j=1}^{m} b_j\]

agar minimum, maka $\sum_{j=1}^{m} b_j$ harus sebesar-besarnya, dan dar Lemma terdapat $b-1$ buah suku pada $\{b_1, b_2, \cdots, b_{m}\}$ yang berada di $\{m+2, m+3, \cdots, m+s\}$, jadi agar  sebesar-besarnya, $b-1$ buah suku ini adalah $m+s , m+s-1, \cdots , m+s-b+2$.

Kemudian suku-suku pada $\{b_{m+1}, b_{m+2}, \cdots, b_n\}$ harus sekecil-kecilnya, dan karena untuk $j \geq m+1$ berlaku $b_{j} \geq j+1 \geq m+2$, maka yang terkecil adalah mulai dari $m+2, m+3, \cdots$ dan seterusnya, tapi perhatikan dari paragraf sebelumnya bahwa nilai $m+s-b+2, m+s-b+3, \cdots, m+s$ sudah terpakai untuk pada suku-suku di $\{b_1, b_2, \cdots, b_{m+1}\}$ (dan harus terpakai). Ini berarti pada himpunan $\{m+1, m+2, \cdots, m+s\}$ kita hanya boleh menggunakan

\[\{m+2 , m+2 , \cdots, m+s-b+1 \}\]

karena $\sum_{j=m+1}^n b_j$ memuat $n-m$ suku, dan kita baru memakai $|\{m+2 , m+2 , \cdots, m+s-b+1 \}| = s-b$ suku, maka masih harus ada $n-m-s-b$ buah suku lain, dan kemungkinan terkecil nya adalah setelah melangkahi $\{m+s-b+2, \cdots, m+s\}$ (karena sudah terpakai) yaitu

\[\{m+s+1, m+s+2, \cdots , n+b \}\]

Sehingga diperoleh
\[\begin{align*}\sum_{j=m+1}^{n} b_j &\geq \sum_{j=m+2}^{m+s-b+1} j + \sum_{j=m+s+1}^{n+b} j \\ &= \left( \frac{2m+s-b+3}{2} \right)(s-b) + \left(\frac{n+m+s+b+1}{2}\right) \left(n+b-m-s\right) \\ &= \left(\frac{s-b}{2}\right) (m-2b-n+2) +(n-m)\left( \frac{n+m+s++b+1}{2}\right) \\ &= (n-m) \left(\frac{n+m+2b+1}{2}\right) -(b-1)(s-b) \end{align*}\]

Jadi
\[\begin{align*}\sum_{j=m+1}^n (a_j - b) = \sum_{j=m+1}^n (b_j-j-b) &= \sum_{j=m+1}^n b_j -\sum_{j=m+1}^n j - (n-m)b \\ &\geq (n-m) \left(\frac{n+m+2b+1}{2}\right) -(b-1)(s-b) - \sum_{j=m+1}^n j - (n-m) b \\ &= -(b-1)(s-b)\end{align*}\]

Diperoleh
\[\sum_{j=m+1}^n (a_j - b) \geq -(b-1)(s-b) \qquad (1)\]

 

 

Sekarang akan di estimasi nilai maksimum dari $\sum_{j=m+1}^n b_j$.  Berdasarkan Lemma 3, karena $n > N$, maka terdapat tepat $b-1$ buah anggota $\{n+2, n+3, \cdots, n+s\}$ yang juga anggota $\{b_1, b_2, \cdots, b_n\}$. Jadi agar maksimum, $b-1$ buah anggota-anggota ini haruslah yang sebesar-besarnya yaitu $n+s-b + 2, n+s-b+3, \cdots, n+s$. 

Karena $\sum_{j=m+1}^n b_j$ mempunyai $n-m$ suku, maka yang perlu dibatasi masih $n-m-b+1$ buah suku lagi dan mereka harus berasal dari himpunan $\{1,2 ,\cdots, n+1\}$ (jika tidak demikian maka $\{n+2, \cdots, n+s\}$ memuat lebih dari $b-1$ buah suku), dan agar maksimum dipilih $n-m-b+1$ buah anggota terbesar di $\{1,2, \cdots, n+1\}$ yaitu $n+1, n, \cdots,  m + b +1$.

Diperoleh
\[\begin{align*}\sum_{j=m+1}^n b_j &\leq \sum_{j=n+s-b+2}^{n+s} j + \sum_{j=m+b+1}^{n+1} j \\  &= \left(\frac{2n+2s-b+2}{2} \right)\left(b-1\right) + \left(\frac{n+m+b+2}{2}\right) \left(n-m-b+1\right) \\ &= \left(\frac{n-m+2s-2b}{2} \right)(b-1)+ \left(\frac{n+m+b+2}{2}\right) \left(n-m\right) \\ &=(b-1)(s-b) + (n-m) \left(\frac{n+m+2b+1}{2}\right)
\end{align*}\]

Sehingga
\[\begin{align*}\sum_{j=m+1}^n (a_j - b) = \sum_{j=m+1}^n (b_j-j-b) &= \sum_{j=m+1}^n b_j -\sum_{j=m+1}^n j - (n-m)b \\ &\leq (n-m) \left(\frac{n+m+2b+1}{2}\right) +(b-1)(s-b) - \sum_{j=m+1}^n j - (n-m) b \\ &= (b-1)(s-b)\end{align*}\]

Digabungkan dengan ketaksamaan (1) diperoleh

\[-(b-1)(s-b) \leq \sum_{j=m+1}^n (a_j - b) \leq (b-1)(s-b) \Rightarrow \left| \sum_{j=m+1}^n (a_j - b) \right| \leq (b-1)(s-b) \]

Dengan menggunakan AM-GM diperoleh $(b-1)(s-b) \leq \left(\frac{b-1+s-b}{2}\right)^2 = \left(\frac{s-1}{2}\right)^2$. Sehingga

\[\left| \sum_{j=m+1}^n (a_j - b) \right| \leq \left(\frac{s-1}{2}\right)^2. \]

Pada soal diatas $s=2015$.

Q.E.D

  • Upvote 2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

×