Salah satu soal simulasi minggu lalu, diambil dari Problem 11666 AMM, October 2012. Solusi diterbitkan di AMM , December 2014, ini screenshot nya . Berikut ini saya berikan solusi lain dengan menggunakan Combinatorial Nullstellensatz dan Lucas Theorem
Kita bisa memandang $W_m$ sebagai $\mathbb{F}_{2^m}=GF(2^m)$, lapangan berhingga dengan karakteristik $2$, yang mempunyai aturan penjumlahan sama dengan soal, namun juga mempunyai aturan perkalian (yang bukan per-komponen).
Continue Reading
Untuk bilangan asli $m \geq 2$, misalkan $W_m$ merupakan himpunan yang berisikan untaian $(a_1, a_2,...,a_m)$ dimana $a_i \in \{0,1\}$. Untuk $s,t \in W$, dimana $s=(a_1, \cdots, a_m)$ dan $t=(a_2,\cdots, a_m)$ kita definisikan $s+t$ sebagai untaian $(c_1, c_2,...,c_m)$ dimana $c_i = a_i+b_i \pmod 2$. Diberikan himpunan $A, B \subseteq W$, definisikan $A+B$ sebagai himpunan yang berisikan $s+t$ dimana $s\in A$ dan $t\in B$. Misalkan $n$ adalah bilangan asli terbesar yang memenuhi $|A|+|B| > 2^n$. Buktikan bahwa $|A+B| \geq 2^n$.
Solusi:
Sekarang misalkan $|A|=a$, $|B|=b$ dan $|A+B|=c$.
Dari kondisi pada soal kita peroleh $2^n +1 \leq a+b \leq 2^{n+1}$.
Suku banyak ini mempunyai derajat yang samadengan $2^n-1$, dan sama-dengan nol untuk setiap $(x,y)\in A \times B$. Pandang koefisien $X^{a-1} Y^{2^n-1-a+1}$ pada suku-banyak diatas, koefisien tersebut sama dengan ${2^n-1 \choose a-1}$. Perhatikan juga bahwa $2^n-1-a+1 \leq b-1$.
Dari kondisi pada soal kita peroleh $2^n +1 \leq a+b \leq 2^{n+1}$.
Soal akan selesai jika berlaku $c \geq |A|+|B|-1$, karena itu akan menyebabkan $c\geq 2^n+1-1=2^n$. Sekarang misalkan $c\leq |A|+|B|-2$. Untuk keperluan kontradiksi kita asumsikan berlaku $c\leq 2^n-1 \leq a+b-2$.
Kondisi diatas membuat kita bisa mengambil himpunan $U \supseteq A+B$ yang memenuhi kondisi $|U|=2^n-1$ (kita tinggal tambah himpunan $A+B$ dengan anggota-anggota di $W_m$ sampai $U$ mempunyai kardinalitas $2^n-1$), kemudian pandang suku-banyak
\[f(X,Y)= \prod_{\mu \in U} (X+Y-\mu)\]
Suku banyak ini mempunyai derajat yang samadengan $2^n-1$, dan sama-dengan nol untuk setiap $(x,y)\in A \times B$. Pandang koefisien $X^{a-1} Y^{2^n-1-a+1}$ pada suku-banyak diatas, koefisien tersebut sama dengan ${2^n-1 \choose a-1}$. Perhatikan juga bahwa $2^n-1-a+1 \leq b-1$.
Dengan Teorem lucas ${2^n -1 \choose k}$ ganjil untuk setiap $k$, jadi merupakan bilangan tak-nol di $GF(2^m)$. Jadi dengan Combinatorial Nullstellensatz untuk $|A|>a-1$ dan $|B|>b-1\geq 2^n-1-a+1$ terdapat $\alpha \in A$ dan $\beta \in B$ sedemikian sehingga
\[f(\alpha, \beta) \neq 0\]
kontradiksi.