Latihan Soal Prinsip Inklusi-Eksklusi

• Tentukan banyaknya bilangan asli kurang dari sama dengan $1000$ yang habis dibagi $7,10,$ atau $15$!
• Tentukan jumlah bilangan asli kurang dari sama dengan $1000$ yang habis dibagi $7,10,$ atau $15$!
• Cari banyaknya solusi dari $x_1+x_2+x_3+x_4+x_5=15$ dimana $0\le x_i\le 4$!
• Pada sebuah permainan dadu dilempat $6$ kali, pemain dikatakan menang bila dadu terakhir memiliki nilai yang sama dengan minimal $1$ dadu pada lemparan sebelumnya. Tentukan peluang menang pemain tersebut!
• Berapa banyak cara mengatur menyusun angka $1,2,3,4,5,6,7,8,9,10$ dengan syarat angka $1,2,3,4,5$ tidak berada pada posisi yang sama?
• Misalkan ada lima kota dengan masing-masing kota memiliki satu orang wakil, berapakah cara untuk menempatkan kelima wakil tersebut pada lima kota dengan syarat tidak ada wakil yang bertempat dengan kota asalnya?
• Misalkan $S=\{1,2,3,\cdots,280\}$. Cari bilangan terkecil $n$ sedemikian hingga jika kita mengambil sembarang $n$ elemen dari $S$ maka ada lima bilangan yang saling relatif prima
• Misalkan ada $1990$ ilmuwan yang datang ke suatu pesta. Tiap ilmuwan mengenal minimal $1327$ ilmuwan lainnya. Buktikan kita bisa mencari empat ilmuwan sedemikian hingga tiap pasangan ilmuwan (dari $4$ orang itu) saling mengenal!
• Misalkan $S=\{1,2,\cdots,2016\}$ dan $x_i$ merupakan permutasi dari $S$. Cari banyaknya permutasi jika $|x_1-1|=|x_2-2|=|x_3-3|=\cdots=|x_{2016}-2016|=a$ dengan $a\equiv 0 \pmod 3$!
• Cari banyaknya permutasi $\pi$ dari $\{1,2,3,\cdots,n\}$ yang memenuhi $\pi(i+1)\not = \pi(i)+1,\forall 1\le i \le n$!

Share if you like it:)

Prinsip Inklusi-Eksklusi

Pada kesempatan kali ini kita akan membahas tentang prinsip inklusi-eksklusi yang sering digunakan dalam kombinatorika khususnya dalam mencari jumlah seperti himpunan dan probabilitas.

Prinsip Inklusi-Eksklusi. Diberikan himpunan $A_1,A_2,\cdots,A_n$. Definisikan $S_k=\sum_{1\le i_1\le i_2\le \cdots \le i_k\le n}|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|$ yang berarti jumlah semua himpunan yang dipilih sebanyak $k$ dari $n$, maka
$$|A_1\cup A_2\cup \cdots \cup A_n|=S_1-S_2+S_3+\cdots+(-1)^{n-1}S_n$$

Bukti. Misal bilangan $x\in A_1\cup A_2\cup \cdots \cup A_n$ maka $x$ terhitung sekali di ruas kiri, kita akan buktikan jika $x$ juga terhitung sekali di ruas kanan. Misalkan $x\in A_{j_1},A_{j_2},\cdots,A_{j_m}$ dan $x$ tidak berada di himpunan selain mereka. Maka ada ${m \choose k}$ himpunan $A_{i_1},A_{i_2},\cdots,A_{i_k}$ sedemikian hingga $x\in A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}$. Hal ini berarti $x$ terhitung sebanyak ${m \choose k}$ pada jumlahan $\sum_{1\le i_1\le i_2\le \cdots \le i_k\le n}|A_{i_1}\cap A_{i_2}\cap \cdots \cap A_{i_k}|$ dengan kata lain, $x$ terhitung total sebanyak
$${m \choose 1}-{m \choose 2}+{m \choose 3}+\cdots +(-1)^{m-1}{m \choose m}=1+(1-1)^m=1$$
jadi $x$ hanya terhitung sekali di ruas kanan.

Latihan Soal Ketaksamaan Segitiga

• Misalkan segiempat konveks $ABCD$, titik $M$ dan $N$ merupakan titik tengah $AD$ dan $BC$.Buktikan $MN=\frac{AB+CD}{2}$ jika dan hanya jika $AB\parallel CD$!
• Titik $M$ berada di dalam segitiga $ABC$. Buktikan $AB+AC > MB + MC$!
• Titik $M$ adalah titik tengah segmen $AB$ dan titik $O$ adalah titik sembarang. Buktikan $|OA-OB|\le 2OM$!
• Misalkan $S$ adalah keliling segitiga $ABC$. Jika $T$ titik di dalam segitiga $ABC$ buktikan
  $$\frac{1}{2}S < TA+TB+TC < S$$
• Untuk sembarang segitiga, buktikan jumlah ketiga garis tinggi segitiga lebih kecil dari keliling segitiga!
• Titik $D,E,$ dan $F$ merupakan titik tengah dari $BC,CA,$ dan $AB$ pada segitiga $ABC$. Jika $S$ merupakan keliling segitiga $ABC$, buktikan
  $$\frac{3}{4}S < AD+BE+CF < S$$
• Misalkan ada garis $l$, titik $X$ dan $Y$ berada diatas garis $l$ dan titik $M$ berada di garis $l$. Cari letak titik $M$ agak panjang $MX+MY$ minimal!
• $7$ bilangan real diambil dari interval $(1,13)$. Buktikan minimal ada $3$ bilangan yang dapat dibentuk menjadi segitiga!
• Tentukan letak titik $X,Y,$ dan $Z$ pada sisi $BC,CA,$ dan $AB$ pada segitiga $ABC$ agak keliling segitiga $XYZ$ minimal!
• Untuk sembarang bilangan real positig $a,b,$ dan $c$ buktikan $\sqrt{a^2-ab+b^2}+\sqrt{b^2-bc+c^2}\ge \sqrt{a^2+ac+c^2}$!

Share if you like it:)

Ketaksamaan Segitiga

Pada kesempatan kali ini, kita tidak membahas tentang teorema tapi lebih tepatnya adalah sebuah prinsip atau lemma mendasar yang ada pada geometri yaitu ketaksamaan segitiga. Meskipun bukan sebuah teorema namun ketaksamaan segitiga ini sering sekali digunakan untuk membuktikan teorema-teorema yang ada.

Ketaksamaan Segitiga. Sebuah segitiga $ABC$ harus memenuhi ketiga sifat berikut
$$\begin{align*} a+b&>c \\ b+c&>a \\ c+a&>b\end{align*}$$

Bukti. Buktikan dengan kontradiksi, asumsikan $a+b\le c$ jika $a+b=c$ maka titik $A,B,$ dan $C$ segaris, jika $a+b < c$ maka kejadian ini tidak akan mungkin karena jarak terpendek atara 2 titik adalah dengan menarik garis lurus dari titik pertama ke titik kedua.

Latihan Soal Cauchy-Schwarz

• $a,b\in \mathbb{R}^{+}$ buktikan $8(a^4+b^4)\ge (a+b)^4$!
• $a,b,c\in \mathbb{R}^{+}$ dan $abc=1$ buktikan $\frac{1}{a^3(b+c)}+\frac{1}{b^3(c+a)}+\frac{1}{c^3(a+b)}\ge \frac{3}{2}$!
• $a,b,c,m,n\in \mathbb{R}^{+}$ buktikan $\frac{x}{ay+bz}+\frac{y}{az+bx}+\frac{z}{ax+by}\ge \frac{3}{a+b}$!
• $a,b,c\in \mathbb{R}^{+}$ buktikan $\frac{x}{x+2y+3z}+\frac{y}{y+2z+3x}+\frac{z}{z+2x+3y}\ge \frac{1}{2}$!
• $a,b,c\in \mathbb{R}^{+}$ dan $ab+bc+ca=\frac{1}{3}$ buktikan $\frac{a}{a^2-bc+1}+\frac{b}{b^2-ca+1}+\frac{c}{c^2-ab+1}\ge \frac{1}{a+b+c}$!
• $a,b,c\in \mathbb{R}^{+}$ dan $abc=1$ buktikan $\sum_{cyc}\frac{a+b+1}{a+b^2+c^3}\le \frac{(a+1)(b+1)(c+1)+1}{a+b+c}$!
• $a,b,c\in \mathbb{R}^{+}$ dan $ab+bc+ca\ge 3$ buktikan $\frac{a}{\sqrt{b+c}}+\frac{b}{\sqrt{c+a}}+\frac{c}{\sqrt{a+b}}\ge \frac{3}{\sqrt{2}}$!
• $a,b,c\in \mathbb{R}^{+}$ buktikan $\frac{a}{2a+b}+\frac{a}{2a+b}+\frac{a}{2a+b}\le 1$!
• $a,b,c\in \mathbb{R}^{+}$ dan $a+b+c=1$ buktikan $\frac{a}{\sqrt{a+2b}}+\frac{b}{\sqrt{b+2c}}+\frac{c}{\sqrt{c+2a}}<\sqrt{\frac{3}{2}}$!
• $a,b,c\in \mathbb{R}^{+}$ buktikan $\sqrt{\frac{2a}{b+c}}+\sqrt{\frac{2a}{b+c}}+\sqrt{\frac{2a}{b+c}}\le \sqrt{3\left(\frac{a}{b}+\frac{b}{c}+\frac{c}{a}\right)}$

Share if you like it:)

Ketaksamaan Cauchy-Schwarz

Pada kesempatan kali ini kita akan membahas tentak ketaksamaan Cauchy-Schwarz. Ketaksamaan ini juga tak kalah terkenal dengan ketaksamaan AM-GM. Ketaksamaan ini juga sering muncul pada soal-soal matematika.

Cauchy-Schwarz Inequality. Untuk sembarang bilangan real $a_1,a_2,\cdots,a_n$ dan $b_1,b_2,\cdots,b_n$ berlaku
$$(a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2)\ge(a_1b_1+a_2b_2+\cdots+a_nb_n)^2$$
ketaksamaan terjadi saat $\frac{a_1}{b_1}=\frac{a_2}{b_2}=\cdots=\frac{a_n}{b_n}$

Bukti. Pertama nyatakan $A=a_1^2+a_2^2+\cdots+a_n^2$ dan $B=b_1^2+b_2^2+\cdots+b_n^2$ kemudian gunakan ketaksamaan AM-GM
$$\frac{a_1^2}{A}+\frac{b_1^2}{B}\ge \frac{2a_1b_1}{\sqrt{AB}}$$
gunakan cara yang sama untuk $a_2,a_3,\cdots,a_n$ kemudian jumlahkan semuanya
$$\sum_{i=1}^n \frac{a_i^2}{A}+\sum_{i=1}^n\frac{b_i^2}{B}\ge \sum_{i=1}^n \frac{2a_ib_i}{\sqrt{AB}}$$
$$ 2\ge \sum_{i=1}^n \frac{2a_ib_i}{\sqrt{AB}}$$
dengan kata lain
$$\sqrt{AB}\ge (a_1b_1+a_2b_2+\cdots+a_nb_n)$$
$$(a_1^2+a_2^2+\cdots+a_n^2)(b_1^2+b_2^2+\cdots+b_n^2)\ge(a_1b_1+a_2b_2+\cdots+a_nb_n)^2$$

Cauchy-Schwarz Engel form. Untuk sembarang bilangan real $a_1,a_2,\cdots,a_n$ dan $b_1,b_2,\cdots,b_n$ berlaku
$$\frac{a_1^2}{b_1}+\frac{a_2^2}{b_2}+\cdots+\frac{a_n^2}{b_n}\ge \frac{(a_1+a_2+\cdots+a_n)^2}{b_1+b_2+\cdots+b_n}$$

Bukti. Kita akan buktikan dengan Ketaksamaan yang sudah kita bahas di awal. Berbeda dengan yang awal kita akan mengganti nilai $a_i$ menjadi $\frac{a_i^2}{b_1}$
$$\left(b_1+b_2+\cdots+b_n\right)\left(\frac{a_1^2}{b_1}+\frac{a_2^2}{b_2}+\cdots+\frac{a_n^2}{b_n}\right)\ge \left(a_1+a_2+\cdots+a_n\right)^2$$
dengan memindahkan ruas kita mendapat
$$\frac{a_1^2}{b_1}+\frac{a_2^2}{b_2}+\cdots+\frac{a_n^2}{b_n}\ge \frac{(a_1+a_2+\cdots+a_n)^2}{b_1+b_2+\cdots+b_n}$$

Latihan Soal Fermat Little Theorem

• Jika bilangan prima $p$ membagi $a^2+1$ untuk suatu bilangan bulat $a$. Buktikan $p$ berbentuk $4k+1$!
• Cari semua bilangan bulat $n$ sedemikian hingga $7|2^n-1$!
• Buktikan tidak ada bilangan bulat $n$ sedemikian hingga $7|2^n+1$!
• Buktikan tidak ada bilangan bulat $n>1$ sedemikian hingga $n^2|2^n+1$!
• Jika $3^n-2^n=p^k$ dengan $p$ prima dan $k\ge 1$, buktikan bahwa $n$ merupakan bilangan prima!
• Jika bilangan prima $p$ berbentuk $4k+3$ dan ada bilangan bulat $a$ dan $b$ sedemikian hingga $p|a^2+b^2$, buktikan $p|a$ dan $p|b$!
• Jika $p$ adalah bilangan prima buktikan $p|2^p-2$
• Apakah konvers dari soal nomor 7 juga benar?
• Buktikan untuk semua bilangan prima $p>2$ maka $n^p\equiv n \pmod {2p}$!
• Buktikan jika $p>2$ adalah bilangan prima dan $p|m^p+n^p$ untuk bilangan bulat $m$ dan $n$ maka $p^2|m^p+n^p$!

Share if you like it:)

Fermat Little Theorem

Fermat Little Theorem (FLT)

Pada kesempatan kali ini kita akan membahas tentang Fermat Little Theorem atau yang biasa dikenal dengan singkatan FLT. Teorema ini sendiri juga sering dijumpai pada soal-soal matematika khususnya pada bagian teori bilangan atau Number Theory

FLT. Diberikan bilangan bulat positif $a$ dan sebuah bilangan prima $p$ maka berlaku
$$a^p\equiv a \pmod p$$

Bukti. Kita akan membuktikan Fermat Little Theorem dengan induksi matematika. Untuk $a=1$ teorema benar, sekarang kita asumsikan untuk $a=k$ teorema benar. Maka kita harus membuktikan $(k+1)^p\equiv k+1 \pmod p$.
$$\begin{align*} (k+1)^p - (k+1)&\equiv (k^p-k) + \sum_{n=1}^{p-1} {p\choose n}k^n \pmod p \\ &\equiv k^p-k \pmod p \\ &\equiv 0 \pmod p\end{align*}$$
jadi teorema benar. Perlu diingat bahwa $p|{p\choose n}$ untuk setiap $1\le n $

Ada sebuah teorema yaitu Teorema Euler yang bisa dibilang mirip dengan Fermat Little Theorem tetapi berlaku untuk sebuah bilangan bulat $a$ dan $b$ dimana $b$ tidak harus prima namun $\gcd{(a,b)}=1$. Sebelum membahas tentang Teorema Euler kita harus mengetahui suatu fungsi yaitu euler phi function yang biasa dilambangkan dengan $\varphi(n)$. $\varphi(n)$ menyatakan banyaknya bilangan yang lebih kecil dari $n$ dan relatif prima dengan $n$, contohnya $\varphi(8)=4,\varphi(20)=8,$ dan lain lain.

Euler Theorem. Untuk sembarang bilangan bulat positif $a$ dan $n$ yang saling relatif prima, maka berlaku
$$a^{\varphi(n)}\equiv 1\pmod n$$

Bukti. Misalkan himpunan $S=\{s_1,s_2,\cdots,s_{\varphi(n)}\}$ dimana $s_i(i=1,2\cdots,\varphi(n))$ dan $a$ semuanya relatif prima dengan $n$. Perhatikan bilangan $s_1a,s_2a,\cdots,s_{\varphi(n)}a$ semuanya relatif prima dengan $n$. Misalkan $t_i$ adalah sisa dari $s_ia$ saat dibagi dengan $n$, hal ini berarti $t_i\in S$. Kita claim bahwa tidak ada bilangan bulat $i\not =j$ sedemikian hingga $t_i=t_j$, asumsikan ada maka $s_ia\equiv s_ja\pmod n\implies s_i\equiv s_j\pmod n$ dimana hal ini tidak mungkin. Jadi dapat disimpulkan bahwa $t_i$ merupakan permutasi dari $s_i$
$$\begin{align*} s_1a\cdot s_2a\cdot\cdots\cdot s_{\varphi(n)}a&\equiv s_1\cdot s_2\cdot\cdots\cdot s_{\varphi(n)} \pmod n \\ Ha^{\varphi(n)}&\equiv H\pmod n\\ a^{\varphi(n)}&\equiv 1 \pmod n\end{align*}$$
dimana $H=s_1\cdot s_2\cdot\cdots\cdot s_{\varphi(n)}$

Latihan Soal PHP

• Jika pada suatu pertemuan terdapat 13 siswa, buktikan terdapat minimal 2 siswa yang lahir pada bulan yang sama!
• John memiliki 5 kelereng berwarna merah, 8 kelereng berwarna hijau, dan 10 kelereng berwarna putih. Tentukan berapa kelereng minimal yang harus diambil John agar ia memiliki 3 kelereng dengan warna yang sama?
• Sebuah keranjang besar berisi buah pisang, apel, dan jeruk. Berapa buah yang harus diambil agar terdapat minimal 6 buah pisang atau minimal 8 buah apel atau 9 buah jeruk?
• Dari himpunan $S=\{1,2,3,\cdots 2016\}$ diambil $14$ buah bilangan. Buktikan dari ke-14 bilangan tersebut ada 2 bilangan yang selisihnya habis dibagi $13$!
• Dari bilangan $1,11,111,\cdots,111\cdots 111$ (ada 2017 digit angka 1) buktikan ada sebuah bilangan yang habis dibagi 2017!
• Ada $n$ bilangan bulat $a_1,a_2,\cdots,a_n$. Buktikan terdapat 2 bilangan bulat $0\le k < l\le n$ sedemikian hingga $a_{k+1}+a_{k+2}+\cdots +a_l$ habis dibagi $n$!
• Seorang pebulu tangkis memiliki waktu $11$ minggu untuk persiapan menghadapi Olimpiade. Dia berkomitmen untuk berlatih minimal sekali sehari, namun agar tidak kelelahan dia tidak akan berlatih lebih dari $12$ kali dalam periode $7$ hari ($1$ minggu). Buktikan ada periode tertentu dimana ia berlatih tepat $21$ kali!
• Dari bilangan $1,2,3,\cdots ,200$ berapa banyak bilangan minimal yang harus diambil agar dapat dipastikan ada $2$ bilangan bulat $a$ dan $b$ sedemikian hingga $a|b$!
• Pada suatu pesta terdapat $n$ orang. Buktikan terdapat 2 orang $p$ dan $q$ sedemikian hingga jumlah teman dari $p$ sama dengan jumlah teman dari $q$! (asumsikan jika $a$ berteman dengan $b$ maka $b$ juga berteman dengan $a$)
• Diberikan $n$ buah bilangan real positif $a_1,a_2,\cdots,a_n$ yang memenuhi
  $$\frac{a_1+a+2+\cdots +a_n}{n}=p$$
  buktikan terdapat bilangan $0< k \le n$ sedemikian hingga $a_k > p$!

Share if you like it:)

PHP

PHP (Pigeon Hole Principal)

Pada kesempatan kali ini kita akan membahas tentang salah satu teorema mendasar pada Kombinatorika yaitu prinsip sangkar merpati atau biasa dikenal dengan istilah Pigeon Hole Principal. Prinsip ini biasanya sering dipakai pada soal-soal lomba karena sudah dikenal oleh banyak orang.

PHP. Jika ada $n+1$ ekor burung merpati yang di masukkan kedalam $n$ buah sangkar, maka ada minimal sebuah sangkar yang berisi 2 ekor burung

Bukti. Kita akan membuktikan teorema ini dengan pembuktian kontradiksi. Asumsikan pernyataan salah: semua kotak berisi maksimal seekor burung. Dengan menggunakan ketaksamaan biasa kita mendapat banyak burung maksimal adalah banyak kotak dikali dengan banyak burung maksimal pada tiap kotak yaitu $n$, namun $n+1 < n$ bernilai salah jadi dapat disimpulkan asumsi salah dan pernyataan awal benar

Latihan Soal Ceva dan Menelaus

• Buktikan garis berat segitiga bertemu pada satu titik!
• Buktikan garis tinggi segitiga bertemu pada satu titik!
• Buktikan garis bagi ketiga sudut segitiga bertemu pada satu titik!
• $P$ titik di dalam segitiga $ABC$. Garis $PA,PB,$ dan $PC$ memotong sisi $BC,CA,$ dan $AB$ berturut-turut pada $D,E,$ dan $F$. Buktikan
  $$\frac{PD}{AD}+\frac{PE}{BE}+\frac{PF}{CF}=1$$
• Segiempat coveks $ABCD$. Garis $DA$ dan $BC$ bertemu di titik $K$. Garis $AB$ dan $CD$ bertemu di titik $L$. Garis $AC$ dan $KL$ bertemu di titik $G$. Garis $DB$ dan $KL$ bertemu di $F$ buktikan
  $$\frac{KF}{FL}=\frac{KG}{GL}$$
• Pada sebuah segienam beraturan $ABCDEF$, titik $M$ dan $N$ pada segmen $AC$ dan $CE$. Jika titik $B,M,$ dan $N$ segaris dan $\frac{AM}{AC}=\frac{CN}{CE}=r$ tentukan $r$!
• Pada segitiga $ABC$, lingkaran dalam segitiga $ABC$ menyinggung sisi $BC,CA,$ dan $AB$ berturut-turut pada $X,Y,$ dan $Z$. Buktikan $AX,BY,$ dan $CZ$ berpotongan di satu titik!
• Pada segitiga $ABC$, titik $D,E,$ dan $F$ pada $BC,CA,$ dan $AB$ sedemikian hingga $AD,BE,$ dan $CF$ berpotongan di satu titik $P$. Buktikan $\frac{AP}{PD}=\frac{AF}{BF}+\frac{AE}{EC}$
• Pada segitiga $ABC$ buat 3 buah persegi pada sisi-sisi segitiga tersebut dan menghadap keluar. Buktikan garis-garis yang ditarik dari titik $A,B,$ dan $C$ terhadap pusat persegi di hadapannya berpotongan di satu titik!
• Pada segitiga $ABC$, garis $AD,BE,$ dan $CF$ berpotongan di satu titik. Titik $P,Q,$ dan $R$ terletak pada $EF,FD,$ dan $DE$ sedemikian hingga $DP,EQ,$ dan $FR$ berpotongan di satu titik. Buktikan $AP,BQ,$ dan $CR$ juga berpotongan di satu titik!

Share if you like it:)

Teorema Ceva dan Menelaus

Pada kesempatan kali ini kita akan membahas salah satu teorama dalam geometri yaitu teorema Ceva dan Menelaus. Sebelum membahas tentang teorema Ceva dan Menelaus ada beberapa lemma yang harus kita ketahui dahulu:

Lemma 1. Pada segitiga $ABC$, titik $D$ pada $AB$ maka
$$\frac{[ABD]}{[ACD]}=\frac{BD}{CD}$$
dimana $[ABC]$ menyatakan luas segitiga $ABC$.

Bukti. Misalkan $t$ adalah tinggi dari segitiga $ABC$ yang ditarik dari titik $A$, segitiga $ABD$ dan $ACD$ juga memiliki tinggi yang sama yaitu $t$. Maka berlaku
$$\begin{align*} \frac{[ABD]}{[ACD]}&=\frac{\frac{1}{2}\cdot BD \cdot t}{\frac{1}{2}\cdot CD\cdot t}\\ &=\frac{BD}{CD} \end{align*}$$

Ceva. Pada segitiga $ABC$, titik $D,E,$ dan $F$ berturut-turut terletak pada $BC,CA,$ dan $AB$. Garis $AD,BE,$ dan $CF$ berpotongan pada satu titik $P$ jika dan hanya jika
$$\frac{AF}{FB}\cdot \frac{BD}{DC}\cdot \frac{CE}{EA}=1$$

Bukti. Dengan menggunakan Lemma 1 kita bisa membuktikan Teorema Ceva. Kita punya
$$\frac{[ABD]}{[ACD]}=\frac{BD}{CD}\text{ dan }\frac{[PBD]}{[PCD]}=\frac{BD}{CD}$$
akibatnya
$$\frac{[ABP]}{[ACP]}=\frac{BD}{CD}$$
dengan cara yang sama
$$\frac{[APC]}{[BPC]}=\frac{AF}{BF}\\\frac{[BPC]}{[APB]}=\frac{CE}{AE}$$
sehingga didapat
$$\frac{AF}{FB}\cdot \frac{BD}{DC}\cdot \frac{CE}{EA}=\frac{[APC]}{[BPC]}\cdot\frac{[APB]}{[APC]}\cdot \frac{[BPC]}{[APB]}=1$$

Menelaus. Pada segitiga $ABC$, titik $D,E,$ dan $F$ berturut-turut terletak pada $BC,CA,$ dan $AB$. Titik $D,E,$ dan $F$ segaris jika dan hanya jika
$$\frac{AF}{FB}\cdot \frac{BD}{DC}\cdot \frac{CE}{EA}=1$$

Latihan Soal AM-GM

• Untuk sembarang bilangan real $a,b > 0$ buktikan $\frac{a}{b}+\frac{b}{a}\ge 2$!
• Untuk sembarang bilangan real $a,b,c >0$ buktikan $3(a^2+b^2+c^2)\ge (a+b+c)^2\ge 3(ab+bc+ca)$!
• $a,b,c\in \mathbb{R}^{+}$ dan $abc=1$ buktikan $a^2+b^2+c^2\ge a+b+c$!
• $a,b,c\in \mathbb{R}^{+}$ buktikan $(a+b+c)\left( \frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right) \ge 9$!
• Untuk sembarang bilangan real $a,b,c >0$ buktikan $a^3+b^3+c^3+ab^2+bc^2+ca^2\ge 2(a^2b+b^2c+c^2a)$!
• $a,b,c\in \mathbb{R}^{+}$ buktikan $(a+b)(b+c)(c+a)\ge 8abc$!
• $a,b,c\in \mathbb{R}^{+}$ buktikan $abc\ge (a+b-c)(b+c-a)(c+a-b)$!
• $a,b,c\in \mathbb{R}^{+}$ dan $a+b+c=3$ buktikan $abc+\frac{12}{ab+bc+ca}\ge 5$!
• $a,b,c\in \mathbb{R}^{+}$ dan $abc=1$ buktikan $\left( a-1+\frac{1}{b}\right)\left( b-1+\frac{1}{c}\right)\left( c-1+\frac{1}{a}\right)\le 1$!
• $a,b,c\in \mathbb{R}^{+}$ dan $a+b+c=3$ buktikan $a^bb^cc^a\le 1$!

Share if you like it:)

Ketaksamaan AM-GM

Pada kesempatan kali ini kita akan membahas suatu ketaksamaan yang paling mendasar yaitu ketaksamaan AM-GM. Kata AM dan GM sendiri berarti Arithmetic Mean dan Geometric Mean. Rataan Aritmatika untuk dua bilangan diartikan sebagai $\frac{a+b}{2}$ sedangkan rataan geometrinya $\sqrt{ab}$.

AM-GM. Untuk sembarang bilangan real positif $a$ dan $b$ berlaku
$$\frac{a+b}{2}\ge \sqrt{ab}$$

Bukti. Untuk sembarang bilangan real $x$ berlaku $x^2\ge 0$. Sekarang kita substitusikan $x=\sqrt{a}-\sqrt{b}$ dimana $a$ dan $b$ bernilai positif.
$$(\sqrt{a}-\sqrt{b})^2\ge 2\\a-2\sqrt{ab}+b\ge 0\\ \frac{a+b}{2}\ge \sqrt{ab}$$

AM-GM (Generalisasi). Untuk sembarang bilangan real positif $a_1,a_2,a_3,\cdots,a_n$ berlaku
$$\frac{a_1+a_2+a_3+\cdots +a_n}{n}\ge \sqrt[n]{a_1a_2a_3\cdots a_n}$$

Latihan Soal keterbagian

• Untuk sembarang bilangan bulat positif $m$ dan $n$. Buktikan $\gcd{(m,n)}{lcm}{(m,n)}=mn$! ($\text{gcd}$ adalah greatest common divisor atau $\text{FPB}$ dan $\text{lcm}$ adalah least common multiple atau $\text{KPK}$)
• Untuk setiap bilangan bulat positif $n$, buktikan $120|n^5-5n^3+4n$!
• Untuk setiap bilangan bulat positif $n$, buktikan $121\nmid n^2+3n+5$!
• Buktikan $13|2^{70}+3^{70}$!
• Tentukan semua bilangan bulat $n$ yang memenuhi $5|2^n+3^n$!
• Cari semua bilangan bulat $x$ yang memenuhi $2x+1|x^3 − 3x + 2$!
• Cari semua bilangan bulat $n$ sedemikian hingga jika kita menghapus digit terakhir dari $n$ maka kita mendapat sebuah bilangan yang membagi $n$!
• Cari semua pasangan bilangat bulat positif $(a,b)$ sedemikian hingga $ab^2+b+7|a^2b+a+b$!
• Buktikan bahwa ada tak hingga banyaknya bilangan prima! (Teorema Euclid)
• Cari semua bilangan prima $p$ dan $q$ yang memenuhi $𝑝 + 𝑞 = (𝑝 − 𝑞)^3$!

Share if you like it:)

Keterbagian

Pada kesempatan kali ini, kita akan membahas suatu bagian yang paling dasar dalam teori bilangan yaitu Keterbagian. Keterbagian merupakan sifat dasar yang dimiliki semua bilangan bulat. Jika ada 2 bilangan bulat $a$ dan $b$ dimana $a\not =0$. Bilangan bulat $a$ dikatakan membagi $b$ jika dan hanya jika ada bilangan bulat $c$ sedemikian hingga $a=bc$. Kita bisa menyatakan hal ini dengan $a|b$ yang berarti $a$ habis membagi $b$ atau $b$ adalah kelipatan dari $a$.

Kita tahu bahwa $0=a\cdot 0$, jadi $a|0$ untuk semua bilangan bulat $a\not=0$

Beberapa sifat lain dari keterbagian antara lain:

• Jika $a|b$ dan $b\not=0$ maka $|a|\le|b|$
• jika $a|b$ dan $a|c$ maka ada bilangan bulat $\alpha$ dan $\beta$ sedemikian hingga $a|\alpha b+\beta c$
• jika $a|b$ dan $a|b\pm c$ maka $a|c$
• $a|a$
• jika $a|b$ dan $b|c$ maka $a|c$
• jika $a|b$ dan $b|a$ maka $|a|=|b|$

Selain sifat-sifat diatas ada beberapa teorema tentang keterbagian, salah satunya adalah Division Algorithm. Division Algorithm sendiri memiliki peran yang cukup penting dalam mengerjakan soal-soal matematika. Sejarang kita akan membahas tentang Division Algorithm

Teorema 1. Untuk setiap bilangan bulat positif $a$ dan $b$, terdapat bilangan bulat non-negatif $q$ dan $r$ yang unik (unik berarti hanya ada 1 kemungkinan, tidak ada kemungkinan lain) yang memenuhi
$$b=aq+r,r < a$$

Bukti.Untuk memnbuktikan teorema ini kita perlu tinjau 3 kemungkinan yaitu: $a > b, a=b,$ dan $a < b $. Jika $a > b$ maka kita dapatkan $q=0$ dan $r=b < a$. Jika $a=b$ kita ambil $q=1$ dan $r=0 < a$. Jika$a < b$ maka ada bilangan bulat $n$ sedemikian hingga $na > b$, misalkan $q$ adalah bilangan bulat terkecil sedemikian hingga $(q+1)a > b$. Hal ini berarti $qa\le b$, selanjutnya kita ambil $r=b-qa$. Untuk membuktikan keunikannya, kita asumsikan ada bilangan bulat non-negatif $q'$ dan $r'$ sedemikian hingga $b=aq' + r$. Kita punya $aq+r=aq'+r'$ atau $a(q-q')=(r'-r)$. Dengan sifat diatas kita dapati $a|r'-r$ dan $a\le |r'-r|$. Karena $0\le r,r' < a$ kita punya $|r'-r| < a$. Dengan ini kita dapat simpulkan bahwa $r'=r$ dan otomatis $q'=q$. Dari teorema diatas, saat $a$ dibagi $b$, bilangan $q$ kita sebut quotient dan bilangan $r$ kita sebut reminder.

Contoh Soal. Buktikan untuk semia bilangan bulat positif $n$, bilangan
$$\frac{21n+4}{14n+3}$$
tidak dapat disederhanakan lagi. (IMO pertama)

Solusi. Misalkan ada bilangan bulat positif $d$ sedemikian hingga $d|21n+4$ dan $d|14n+3$.Dengan sifat nomor 2, $d|2(21n+4)-3(14n+3)=-1$. Jadi kita dapat simpulkan bahwa $d=1$ yang berarti pecahan tersebut tidak dapat disederhanakan lagi.

Notasi

Saat mengerjakan soal matematika, kita selalu dipertemukan dengan notasi-notasi matematika. Sebagian notasi-notasi tersebut mungkin asing bagi kita. Notasi-notasi tersebut sebenarnya digunakan agar setiap orang tidak memiliki persepsi yang berbeda tentang suatu hal pada matematika. Notasi-notasi yang biasanya ditemukan pada soal matematika antara lain:

Diatas ada beberapa notasi yang pasti sering kita jumpai pada soal-soal matematika. Notasi-notasi diatas belum mencakup semua notasi yang ada. Notasi-notasi yang belum ada di daftar akan kita bahas pada kesempatan lainnya.