Soal IMO 2015 Nomor 6
IMO 2015, Soal 6
Diberikan barisan bilangan bulat a_1, a_2, \cdots, a_n, \cdots yang memenuhi
i) 1 \leq a_j \leq s untuk setiap j \geq 1
ii) k+a_k \neq l+a_l untuk setiap 1 \leq k < l.
Buktikan bahwa terdapat bilangan bulat N dan b sedemikian sehingga
\left| \sum_{i=m+1}^{n} (a_i-b) \right| \leq \left(\frac{s-1}{2}\right)
untuk setiap n> m \geq N
Solusi:
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+1 \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\}.
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.
Q.E.D
Diberikan barisan bilangan bulat a_1, a_2, \cdots, a_n, \cdots yang memenuhi
i) 1 \leq a_j \leq s untuk setiap j \geq 1
ii) k+a_k \neq l+a_l untuk setiap 1 \leq k < l.
Buktikan bahwa terdapat bilangan bulat N dan b sedemikian sehingga
\left| \sum_{i=m+1}^{n} (a_i-b) \right| \leq \left(\frac{s-1}{2}\right)
untuk setiap n> m \geq N
Solusi:
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+1 \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 \}
\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.
Q.E.D
Post a Comment: