19:15:00  

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

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:

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).

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}$.

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.

ShareShare on Facebook

TweetShare on Twitter

Pin ItShare on Pinterest