Soal Partisi Bilangan Bulat.
Beberapa hari yang lalu, saya diberi soal berikut oleh Erlang Wiratama Surya :
Katanya soal ini ada di Sesi Mandiri Pembinaan IMO Tahap 4.
Sebenarnya saya sudah pernah lihat soal ini sebelumnya (dan waktu itu saya tidak bisa menyelesaikannya). Tapi sudah lupa dimana.
Sampai sekarang, saya masih penasaran tentang dimana saya melihat soal ini (saya memang sering berasa tidak lega dan agak annoying kalo ada sesuatu berasa di ujung lidah seperti ini :/ )
Bahkan setelah beberapa hari, saya berhasil menyelesaikan soal ini, tapi masih belum tahu source nya (sampai bikin thread di math.stackexcange menanyakan sumber).
Saya (secara dejavu) merasa ini bukan soal yang bersumber dari olimpiade, tapi dari matematika popular yang saya pernah baca di blog-blog post beken (Terence Tao, Timothy Gowers, dll)
Anyway ini solusinya, lagi-lagi saya pakai sesuatu yang sering saya pakai beberapa bulan terakhir (lihat soal kompetisi olimpiade.org no 4 buatan saya dan juga teknik yang sama di mini-artikel yang saya tulis ini ) yaitu kombinasi dari Indicator Function + PigeonHole Principle.
Solusi:
Pertama-tama perhatikan bahwa apabila kita pilih bilangan asli $d$ sedemikian sehingga $a_i^{\prime}=a_i + d$ semua positif maka himpunan $X=X^{\prime} - d$ juga memenuhi
\[\mathbb{Z} = \bigcup_{i=1}^n (X^{\prime} + a_i^{\prime})\]
dan $X^{\prime} + a_i^{\prime} \cap X^{\prime} + a_j^{\prime} = \emptyset$. Lalu, apabila kita berhasil membuktikan $X^{\prime} + p^{\prime} = X^{\prime}$ maka diperoleh $X+p-d= X-d$, jadi $X+p=X$, dan soal terbukti. Ini berarti pengubahan $a_i \rightarrow a_i^{\prime}$ tidak mengubah maksud soal.
Sehingga tanpa kehilangan keumuman soal bisa diasumsikan semua $a_i$ positif, dan tanpa kehilangan keumuman juga bisa diasumsikan $a_n > a_{n-1} > \cdots > a_1$.
Sekarang kita definisikan fungsi indikator
\[v_i = \begin{cases} 1 & \text{jika $i\in X$, } \\ 0 & \text{jika tidak} \end{cases} \]
Idenya adalah dengan membuktikan bahwa fungsi indikator $v_i$ periodik, yakni $v_{i+p} =v_i$ untuk suatu $p$.
Maka dari kondisi $X+a_1, X+a_2, \cdots, X+a_n$ adalah partisi dari $\mathbb{Z}$, diperoleh untuk setiap bilangan bulat $r$ berlaku
\[v_{r-a_1} + v_{r-a_2} + \cdots + v_{r-a_n} = 1\]
Sekarang misalkan $\lambda=a_n - a_1$. Persamaan diatas adalah relasi rekursif, jadi apabila kita mempunyai informasi nilai awal paling banyak $\lambda=a_n-a_1$ buah, maka solusi rekursif tersebut akan unik.
Jadi apabila nilai dari
\[v_{r+1}, v_{r+2}, \cdots, v_{r+\lambda}\]
diketahui maka nilai $v_i$ akan bisa di-generate untuk setiap $i$. Karena $v_i$ hanya bisa nol atau satu, maka kemungkinan nilai awal diatas hanya ada $2^{\lambda}$. Jadi apabila kita bentuk block-block dengan panjang $\lambda$ :
\[\cdots , \{ v_{-\lambda-1}, \cdots, v_{-1}, v_0\} , \{v_1, v_2, \cdots, v_{\lambda} \} , \{v_{\lambda+1}, v_{\lambda+1}, \cdots, v_{2 \lambda}\} , \cdots , \{v_{r+1}, v_{r+2}, \cdots , v_{r+\lambda}\}, \cdots \]
maka berdasarkan prinsip PigeonHole terdapat $u_1$ dan $u_2$ sedemikian sehingga
\[v_{u_1+i}=v_{u_2+i} \qquad i=1, \cdots, \lambda \]
dan karena block $v_{u_1 + 1}, v_{u_1+2}, \cdots , v_{u_1 + \lambda}$ men-generate nilai $v_i$, maka $v_{u_2 + 1}, v_{u_1+2}, \cdots , v_{u_2 + \lambda}$ juga men-generate nilai $v_i$ yang sama, jadi nilai setelah $u_2$ mengulangi nilai setelah $u_1$, dan nilai sebelum $u_2+1$ mengulangi nilai sebelum $u_1+1$, sehingga $v_i$ periodic.
Ini berarti terdapat $p \neq 0$ sedemikian sehingga $v_{i+p} = v_i$, untuk setiap $i$. Sehingga jika $h \in X$ jika dan hanya jika $v_{h} = 1 = v_{h+p}$ jika dan hanya jika $h+p \in X$. Terbukti.
Diberikan himpunan $X \subset \mathbb{Z}$ dan misalkan $a_1, a_2, \cdots, a_n$ adalah bilangan bulat sedemikian sehingga
\[\mathbb{Z} = \bigcup_{j=1}^n (X+a_j)\]
dan $X+a_i \cap X+a_j = \emptyset$ untuk sebarang $i\neq j$. Buktikan bahwa terdapat bilangan bulat tak-nol $p$ sedemikian sehingga $X+p=X$.(Disini definisi dari $X+d:= \{x+d | x \in X\}$ ).
Katanya soal ini ada di Sesi Mandiri Pembinaan IMO Tahap 4.
Sebenarnya saya sudah pernah lihat soal ini sebelumnya (dan waktu itu saya tidak bisa menyelesaikannya). Tapi sudah lupa dimana.
Sampai sekarang, saya masih penasaran tentang dimana saya melihat soal ini (saya memang sering berasa tidak lega dan agak annoying kalo ada sesuatu berasa di ujung lidah seperti ini :/ )
Bahkan setelah beberapa hari, saya berhasil menyelesaikan soal ini, tapi masih belum tahu source nya (sampai bikin thread di math.stackexcange menanyakan sumber).
Saya (secara dejavu) merasa ini bukan soal yang bersumber dari olimpiade, tapi dari matematika popular yang saya pernah baca di blog-blog post beken (Terence Tao, Timothy Gowers, dll)
Anyway ini solusinya, lagi-lagi saya pakai sesuatu yang sering saya pakai beberapa bulan terakhir (lihat soal kompetisi olimpiade.org no 4 buatan saya dan juga teknik yang sama di mini-artikel yang saya tulis ini ) yaitu kombinasi dari Indicator Function + PigeonHole Principle.
Solusi:
Pertama-tama perhatikan bahwa apabila kita pilih bilangan asli $d$ sedemikian sehingga $a_i^{\prime}=a_i + d$ semua positif maka himpunan $X=X^{\prime} - d$ juga memenuhi
\[\mathbb{Z} = \bigcup_{i=1}^n (X^{\prime} + a_i^{\prime})\]
dan $X^{\prime} + a_i^{\prime} \cap X^{\prime} + a_j^{\prime} = \emptyset$. Lalu, apabila kita berhasil membuktikan $X^{\prime} + p^{\prime} = X^{\prime}$ maka diperoleh $X+p-d= X-d$, jadi $X+p=X$, dan soal terbukti. Ini berarti pengubahan $a_i \rightarrow a_i^{\prime}$ tidak mengubah maksud soal.
Sehingga tanpa kehilangan keumuman soal bisa diasumsikan semua $a_i$ positif, dan tanpa kehilangan keumuman juga bisa diasumsikan $a_n > a_{n-1} > \cdots > a_1$.
Sekarang kita definisikan fungsi indikator
\[v_i = \begin{cases} 1 & \text{jika $i\in X$, } \\ 0 & \text{jika tidak} \end{cases} \]
Idenya adalah dengan membuktikan bahwa fungsi indikator $v_i$ periodik, yakni $v_{i+p} =v_i$ untuk suatu $p$.
Maka dari kondisi $X+a_1, X+a_2, \cdots, X+a_n$ adalah partisi dari $\mathbb{Z}$, diperoleh untuk setiap bilangan bulat $r$ berlaku
\[v_{r-a_1} + v_{r-a_2} + \cdots + v_{r-a_n} = 1\]
Sekarang misalkan $\lambda=a_n - a_1$. Persamaan diatas adalah relasi rekursif, jadi apabila kita mempunyai informasi nilai awal paling banyak $\lambda=a_n-a_1$ buah, maka solusi rekursif tersebut akan unik.
Jadi apabila nilai dari
\[v_{r+1}, v_{r+2}, \cdots, v_{r+\lambda}\]
diketahui maka nilai $v_i$ akan bisa di-generate untuk setiap $i$. Karena $v_i$ hanya bisa nol atau satu, maka kemungkinan nilai awal diatas hanya ada $2^{\lambda}$. Jadi apabila kita bentuk block-block dengan panjang $\lambda$ :
\[\cdots , \{ v_{-\lambda-1}, \cdots, v_{-1}, v_0\} , \{v_1, v_2, \cdots, v_{\lambda} \} , \{v_{\lambda+1}, v_{\lambda+1}, \cdots, v_{2 \lambda}\} , \cdots , \{v_{r+1}, v_{r+2}, \cdots , v_{r+\lambda}\}, \cdots \]
maka berdasarkan prinsip PigeonHole terdapat $u_1$ dan $u_2$ sedemikian sehingga
\[v_{u_1+i}=v_{u_2+i} \qquad i=1, \cdots, \lambda \]
dan karena block $v_{u_1 + 1}, v_{u_1+2}, \cdots , v_{u_1 + \lambda}$ men-generate nilai $v_i$, maka $v_{u_2 + 1}, v_{u_1+2}, \cdots , v_{u_2 + \lambda}$ juga men-generate nilai $v_i$ yang sama, jadi nilai setelah $u_2$ mengulangi nilai setelah $u_1$, dan nilai sebelum $u_2+1$ mengulangi nilai sebelum $u_1+1$, sehingga $v_i$ periodic.
Ini berarti terdapat $p \neq 0$ sedemikian sehingga $v_{i+p} = v_i$, untuk setiap $i$. Sehingga jika $h \in X$ jika dan hanya jika $v_{h} = 1 = v_{h+p}$ jika dan hanya jika $h+p \in X$. Terbukti.
Post a Comment: