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: