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