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.

Continue Reading

[Problem] Soal Dengan Pangkat Irasional

[Problem] Soal Dengan Pangkat Irasional

00:02:00   Olimpiade Matematika, soal-soal,

Beberapa minggu terakhir, saya menemukan soal-soal (di problem set olimpiade) yang ternyata bisa saya selesaikan dengan menggunakan Teorema Kalkulus.

Teorema yang akan kita pakai pada post berikut ini adalah Teorema Nilai Antara. Teorema ini termasuk teorema Kalkulus yang memang tidak termasuk pada kurikulum IMO, tapi penggunaannya tidak dilarang.

(Teorema Nilai Rata-Rata)
Misalkan $A\subset \mathbb{R}$ dan $f: A \rightarrow \mathbb{R}$ adalah fungsi yang kontinu pada interval $[a,b] \subset A$ dan terdiferentialkan pada interval $(a,b)$. Maka terdapat $\xi \in (a,b)$ sedemikian sehingga
\[\frac{f(b)-f(a)}{b-a}=f^{\prime}(\xi)\]

Bukti teorema ini (hampir?) selalu pasti ada di buku textbook Calculus.

Berikut adalah sebuah soal yang bisa diselesaikan dengan menggunakan Teorema Nilai Rata-Rata. Tapi menurut saya soal ini harusnya tidak ada di olimpiade SMA, karena menggunakan definisi dari pangkat irasional, yang mana hal tersebut menggunakan fungsi logaritma natural.

[Edit: Ternyata soal ini adalah soal Putnam 1971 A6]

Diberikan bilangan real $r>0$ sedemikian sehingga $n^r \in \mathbb{Z}$ untuk setiap $n \in \mathbb{N}$. Buktikan bahwa $r \in \mathbb{Z}$.

Solusi:

Definisikan fungsi $f(x)=x^r$. Kemudian untuk sebarang bilangan $w \in \mathbb{N}$ kita definisikan barisan fungsi $f_0(w), f_1(w), f_2(w), ....$ sebagai
\[f_0(w) = f(w) \qquad f_j(w) = f_{j-1}(w+1)-f_{j-1}(w) \quad j\geq 1\]

Dari hipotesa soal dan definisi diatas, diperoleh $f_j(w)$ selalu merupakan bilangan bulat untuk setiap bilangan asli $j$ dan $w$. Selanjutnya kita akan membutuhkan lemma berikut:

Lemma
Untuk bilangan asli $1 \leq k \leq j$ terdapat bilangan real $w_k \in (w, w+k)$ sedemikian sehingga
\[f_j (w) = f_{j-k}^{(k)}(w_k)\]

Bukti Lemma: Pertama-tama kita buktikan dulu untuk $k=1$ dan $k=2$ (agar lebih jelas). Dengan menggunakan Teorema Nilai Rata-Rata,  terdapat $w_1 \in (w, w+1)$ yang memenuhi
\[f_j(w) = f_{j-1}(w+1) - f_{j-1}(w) = f_{j-1}^{\prime}(w_1)\]
Sedangkan $f_{j-1}^{\prime}(w_1) = f_{j-2}^{\prime}(w_1+1) - f_{j-2}^{\prime}(w_1)$ yang dengan menggunakan Teorema Nilai Rata-Rata lagi, diperoleh $w_2 \in (w_1, w_1+1) \subset (w,w+2)$ yang memenuhi \[f_{j-2}^{\prime}(w_1+1) - f_{j-2}^{\prime}(w_1) = f_{j-2}^{\prime \prime}(w_2)\]
Sekarang kita bisa lanjutkan dengan menggunakan induksi matematika, yaitu jika $f_j(w)=f_{j-k}^{(k)}(w_k)$ untuk suatu $w_k \in (w, w+k)$ maka
\[f_j(w)=f_{j-k}^{(k)}(w_k) = f_{j-k-1}^{(k)}(w_k+1)- f_{j-k-1}^{(k)}(w_k) =  f_{j-k-1}^{(k+1)}(w_{k+1})\]
dimana $w_{k+1} \in (w_k , w_{k}+1) \subset (w, w+k+1)$. Jadi Lemma Terbukti.

Sekarang kembali ke soal,  tulis $r = \lfloor r \rfloor + \{r\}$ , dan tulis juga $s={\lfloor r \rfloor}+1$,  definisikan juga  $A=\prod_{k=1}^s (r-k+1)$, jadi kita bisa tulis turunan ke-$s$ dari $f(x)$ adalah $A \cdot x^{r-s}$.

Asumsikan  $r$ bukan bilangan bulat, maka diperoleh $A>0$.

Sekarang karena $s-r>0$ kita bisa memilih bilangan asli $w$ yang memenuhi $w^{s-r}> A$. Kemudian dengan menggunakan lemma untuk $k=j=s$ diperoleh

\[f_{s} (w)=f^{(s)}(w_s)= A \cdot w_s^{r-s} \]

dimana $w_s \in (w, w+s)$.  Perhatikan bahwa $r-s+1 > 0$ namun  $r-s$ negatif,  sehingga diperoleh $A>0$ dan $w_s^{r-s} < w^{r-s}$.  Kita simpulkan

\[0< f_{s} (w) < A \cdot w^{r-s}< 1 \]

Hal ini kontradiksi dengan observasi sebelumnya bahwa $f_s(w)$ selalu bilangan bulat.

Edit : Dari komentar Yosua Yonathan dan Erlang di Facebook, soal ini juga benar apabila  "untuk setiap $n \in \mathbb{Z}$" diganti dengan "$n \in \{2,3,5\}$".  Lebih lanjut lagi untuk $n \in \{2,3\}$ masalah ini dipercaya masih merupakan open problem.

Masalah yang berhubungan dengan soal ini adalah Six Exponentials Theorem dan Four Exponentials Conjecture

Continue Reading