Soal Batu
Beberapa bulan yang lalu, di olimpiade.org, sayakalah (Erlang) mem-posting soal berikut:
Bagi saya soal ini sangat susah, karena beratnya yang harus bilangan real positif. Saya menyelesaikan soal ini dengan menggunakan Hamel Basis, dan argumen yang similar juga berlaku ketika "berat" batu boleh bilangan negatif. (solusi saya di olimpiade.org dapat dilihat dengan mengklik soal diatas, saya=Adri :p )
Beberapa hari yang lalu, saya melihat soal serupa yang relatif lebih mudah dimana berat batu adalah bilangan bulat positif, yang merupakan soal Kompetisi Putnam ke-34 (saya kurang tahu Putnam tahun berapa itu, google saja). (Update: Soal yang sama ternyata juga ada di buku The USSR OLYMPIAD PROBLEM BOOK oleh Shklarsjy, Chentzov, Yaglom). Soal versi bilangan real ini muncul (tanpa solusi) di buku Problems From The Book, dan ada di bab yang membahas tentang Dirichlet Approximation (Kronecker's Theorem dan kawan2). Mungkin perlu dicoba mencari solusi yang menggunakan Dirichlet Approximation.
Argumen yang saya pakai di olimpiade.org ternyata bisa mengeneralisasi soal ini dimana "berat" batu merupakan Matriks berukuran $n \times n$ dengan komponen matriks berupa bilangan-bilangan kompleks, sebenarnya argumen saya juga berlaku untuk sebarang ruang vektor atas lapangan kompleks.
Untuk kemudahan, seperti pada post di olimpiade.org, kita sebut syarat :
"Jika diambil sebarang satu anggota, sisanya dapat dipartisi menjadi dua grup sama banyak dengan total kuantitas sama besar"
sebagai syarat bagus.
Kita telah membuktikan bahwa jika $2n+1$ buah bilangan real memenuhi syarat bagus maka $2n+1$ buah bilangan tersebut akan sama.
Dengan argument yang sama, kita akan buktikan untuk kasus bilangan kompleks.
Misalkan $z_j=x_j + i y_j$ untuk $j=1,2, \cdots, 2n+1$ adalah bilangan kompleks yang memenuhi syarat bagus. Maka berlaku $z_1=z_2= \cdots = z_{2n+1}$.
Solusi: Perhatikan bahwa apabila $z_k$ diambil, maka dengan syarat bagus kita peroleh terdapat dua himpunan disjoint $A_k, B_k \subseteq \{z_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ dan memenuhi
\[\sum_{j \in A_k} x_j + i \left( \sum_{j \in A_k} y_j \right) = \sum_{j \in B_k} x_j + i \left( \sum_{j \in B_k} y_j \right) \]
Ini berarti $\sum_{j \in A_k} x_j = \sum_{j \in B_k} x_j$ dan $\sum_{j \in A_k} y_j = \sum_{j \in B_k} y_j$, dengan kata lain bilangan real $x_1, x_2, \cdots, x_{2n+1}$ dan $y_1, y_2, \cdots, y_{2n+1}$ memenuhi syarat bagus, dan karena kita sudah membuktikan soal untuk bilangan real, maka diperoleh $x_1 = x_2 = \cdots = x_{2n+1}$ dan $y_1 = y_2 = \cdots =y_{2n+1}$. Dari sini kita peroleh $z_1 = z_2= \cdots = z_{2n+1}$ dan kita selesai. $\blacksquare$
Sekarang jelas bahwa argumen yang similar dapat digunakan apabila berat batu adalah anggota dari ruang vektor berdimensi hingga $V$ atas lapangan $\mathbb{C}$.
Diberikan $\mathbf{w}_1 , \mathbf{w}_2, \cdots, \mathbf{w}_{2n+1}$ adalah vektor-vektor di $V$ yang memenuhi syarat bagus. Misalkan $\mathbf{b}_1, \mathbf{b}_2, \cdots, \mathbf{b}_{m}$ adalah basis dari $V$. Kita tulis
\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i\]
dimana $\alpha_{si} \in \mathbb{C}$ untuk $1 \leq s \leq 2n+1$ dan $1 \leq i \leq m$.
Maka jika $\mathbf{w}_k$ dibuang, dari syarat bagus sisanya dapat dipartisi menjadi dua himpunan disjoint $A_k, B_k \subseteq \{\mathbf{w}_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ yang memenuhi
\[\left( \sum_{j \in A_k} \alpha_{j1} \right) b_1 + \cdots + \left( \sum_{j \in A_k} \alpha_{jm} \right) b_m = \left( \sum_{j \in B_k} \alpha_{j1} \right) b_1 + \cdots + \left( \sum_{j \in B_k} \alpha_{jm} \right) b_m \]
Ini berarti untuk setiap $i \in \{1, 2, \cdots, m\}$ bilangan kompleks $\alpha_{1i}, \alpha_{2i}, \cdots, \alpha_{2n+1 i}$ memenuhi syarat bagus, sehingga $\alpha_{1i}=\alpha_{2i}= \cdots=\alpha_{2n+1 i}$. Jadi diperoleh untuk sebarang $s, t \in {1, 2, \cdots, 2n+1}$ berlaku
\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i = \sum_{i=1}^m \alpha_{ti} \mathbf{b}_i = \mathbf{w}_{t}\]
dan kita selesai.
Dari sini kita bisa melihat bahwa jika "berat" batu merupakan vektor, matriks, atau bahkan ketika batu tersebut mempunyai "berat" polynomial, jika syarat bagus terpenuhi maka berat mereka sama.
Sebenarnya (mungkin )kita bisa mengeneralisasi lebih jauh, pada artikel "A Combinatorial Generalization of a Putnam Problem" oleh Ömer Egecioglu, di American Mathematical Monthly, dia membuktikan (dengan menggunakan Cyclotomic Polynomial ) pernyataan berikut:
Ketika $k=1$ dan $p=2$, kita peroleh versi bilangan kompleks yang telah kita buktikan diatas.
Jika digabung dengan argumen saya yang sebelumnya, teorema diatas harusnya juga berkerja untuk sebarang ruangan vektor atas bilangan kompleks. [ya kan? :p ]
Diberikan $2n+1$ buah batu dengan berat bilangan real positif. Untuk setiap $1 \leq i \leq 2n+1$, apabila batu dengan berat $a_i$ kita pisahkan, maka $2n$ buah batu sisanya dapat dikelompokan menjadi dua grup dengan $n$ anggota, dimana berat total kedua grup batu tersebut sama. Buktikan bahwa berat batu sama semua.
Bagi saya soal ini sangat susah, karena beratnya yang harus bilangan real positif. Saya menyelesaikan soal ini dengan menggunakan Hamel Basis, dan argumen yang similar juga berlaku ketika "berat" batu boleh bilangan negatif. (solusi saya di olimpiade.org dapat dilihat dengan mengklik soal diatas, saya=Adri :p )
Beberapa hari yang lalu, saya melihat soal serupa yang relatif lebih mudah dimana berat batu adalah bilangan bulat positif, yang merupakan soal Kompetisi Putnam ke-34 (saya kurang tahu Putnam tahun berapa itu, google saja). (Update: Soal yang sama ternyata juga ada di buku The USSR OLYMPIAD PROBLEM BOOK oleh Shklarsjy, Chentzov, Yaglom). Soal versi bilangan real ini muncul (tanpa solusi) di buku Problems From The Book, dan ada di bab yang membahas tentang Dirichlet Approximation (Kronecker's Theorem dan kawan2). Mungkin perlu dicoba mencari solusi yang menggunakan Dirichlet Approximation.
Argumen yang saya pakai di olimpiade.org ternyata bisa mengeneralisasi soal ini dimana "berat" batu merupakan Matriks berukuran $n \times n$ dengan komponen matriks berupa bilangan-bilangan kompleks, sebenarnya argumen saya juga berlaku untuk sebarang ruang vektor atas lapangan kompleks.
Untuk kemudahan, seperti pada post di olimpiade.org, kita sebut syarat :
"Jika diambil sebarang satu anggota, sisanya dapat dipartisi menjadi dua grup sama banyak dengan total kuantitas sama besar"
sebagai syarat bagus.
Kita telah membuktikan bahwa jika $2n+1$ buah bilangan real memenuhi syarat bagus maka $2n+1$ buah bilangan tersebut akan sama.
Dengan argument yang sama, kita akan buktikan untuk kasus bilangan kompleks.
Misalkan $z_j=x_j + i y_j$ untuk $j=1,2, \cdots, 2n+1$ adalah bilangan kompleks yang memenuhi syarat bagus. Maka berlaku $z_1=z_2= \cdots = z_{2n+1}$.
Solusi: Perhatikan bahwa apabila $z_k$ diambil, maka dengan syarat bagus kita peroleh terdapat dua himpunan disjoint $A_k, B_k \subseteq \{z_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ dan memenuhi
\[\sum_{j \in A_k} x_j + i \left( \sum_{j \in A_k} y_j \right) = \sum_{j \in B_k} x_j + i \left( \sum_{j \in B_k} y_j \right) \]
Ini berarti $\sum_{j \in A_k} x_j = \sum_{j \in B_k} x_j$ dan $\sum_{j \in A_k} y_j = \sum_{j \in B_k} y_j$, dengan kata lain bilangan real $x_1, x_2, \cdots, x_{2n+1}$ dan $y_1, y_2, \cdots, y_{2n+1}$ memenuhi syarat bagus, dan karena kita sudah membuktikan soal untuk bilangan real, maka diperoleh $x_1 = x_2 = \cdots = x_{2n+1}$ dan $y_1 = y_2 = \cdots =y_{2n+1}$. Dari sini kita peroleh $z_1 = z_2= \cdots = z_{2n+1}$ dan kita selesai. $\blacksquare$
Sekarang jelas bahwa argumen yang similar dapat digunakan apabila berat batu adalah anggota dari ruang vektor berdimensi hingga $V$ atas lapangan $\mathbb{C}$.
Diberikan $\mathbf{w}_1 , \mathbf{w}_2, \cdots, \mathbf{w}_{2n+1}$ adalah vektor-vektor di $V$ yang memenuhi syarat bagus. Misalkan $\mathbf{b}_1, \mathbf{b}_2, \cdots, \mathbf{b}_{m}$ adalah basis dari $V$. Kita tulis
\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i\]
dimana $\alpha_{si} \in \mathbb{C}$ untuk $1 \leq s \leq 2n+1$ dan $1 \leq i \leq m$.
Maka jika $\mathbf{w}_k$ dibuang, dari syarat bagus sisanya dapat dipartisi menjadi dua himpunan disjoint $A_k, B_k \subseteq \{\mathbf{w}_j | j\neq k\}$ dengan $|A_k| = |B_k|=n$ yang memenuhi
\[\left( \sum_{j \in A_k} \alpha_{j1} \right) b_1 + \cdots + \left( \sum_{j \in A_k} \alpha_{jm} \right) b_m = \left( \sum_{j \in B_k} \alpha_{j1} \right) b_1 + \cdots + \left( \sum_{j \in B_k} \alpha_{jm} \right) b_m \]
Ini berarti untuk setiap $i \in \{1, 2, \cdots, m\}$ bilangan kompleks $\alpha_{1i}, \alpha_{2i}, \cdots, \alpha_{2n+1 i}$ memenuhi syarat bagus, sehingga $\alpha_{1i}=\alpha_{2i}= \cdots=\alpha_{2n+1 i}$. Jadi diperoleh untuk sebarang $s, t \in {1, 2, \cdots, 2n+1}$ berlaku
\[\mathbf{w}_{s} = \sum_{i=1}^m \alpha_{si} \mathbf{b}_i = \sum_{i=1}^m \alpha_{ti} \mathbf{b}_i = \mathbf{w}_{t}\]
dan kita selesai.
Dari sini kita bisa melihat bahwa jika "berat" batu merupakan vektor, matriks, atau bahkan ketika batu tersebut mempunyai "berat" polynomial, jika syarat bagus terpenuhi maka berat mereka sama.
Sebenarnya (mungkin )kita bisa mengeneralisasi lebih jauh, pada artikel "A Combinatorial Generalization of a Putnam Problem" oleh Ömer Egecioglu, di American Mathematical Monthly, dia membuktikan (dengan menggunakan Cyclotomic Polynomial ) pernyataan berikut:
Misalkan $\xi$ sebuah akar primitif dari $x^q-1$ dimana $q=p^r$, dan $p$ adalah bilangan prima. Diberikan barisan $S$ yang terdiri dari $qn+1$ buah bilangan komplex $z_1, z_2, \cdots, z_{qn+1}$ dengan sifat : Untuk setiap $i \in \{1, 2, \cdots qn+1\}$. $S \backslash \{z_i\}$ dapat di partisi menjadi $q$ buah himpunan sama besar $S_{i0}, S_{i1}, \cdots, S_{i, q-1}$ dengan
\[\sum_{k=0}^{q-1} \xi^k \sum_{z_j \in S_{t,k}} z_j=0\]
maka $z_1 = z_2 = \cdots = z_{qn+1}=0$
Ketika $k=1$ dan $p=2$, kita peroleh versi bilangan kompleks yang telah kita buktikan diatas.
Jika digabung dengan argumen saya yang sebelumnya, teorema diatas harusnya juga berkerja untuk sebarang ruangan vektor atas bilangan kompleks. [ya kan? :p ]
Post a Comment: