Penerapan Metode Menghitung dengan Dua Cara

• Contoh 1. Untuk himpunan berhingga $A=\{a_1,a_2,…,a_m\}$ dan $B=\{b_1,b_2,…,b_n\}$ definisikan produk Kartesius $A\times B$ sebagai himpunan pasangan terurut yang diberikan oleh $$A\times B=\{(a_i,b_j)\}|1\le i\le m,1\le j\le n\}.$$ Buktikan bahwa $|A\times B|=\sum_{i=1}^{m}|C_i|=\sum_{j=1}^{n}|D_j|$, dimana $$C_i=\{(a_i,b)|b\in B\},\text{ }\text{ }\text{ }D_j=\{(a,b_j)|a\in A\},\text{ }\text{ }\text{ }1\le i\le m,1\le j\le n.$$
  Solusi: Kita hitung $|A\times B|$ dengan mempartisi $A\times B$ dalam dua cara: (i) menurut komponen pertama dari pasangan $(a_i,b_j)$ untuk mengklasifikasikan $A\times B$ dan (ii) menurut komponen kedua dari pasangan $(a_i,b_j)$ untuk mengklasifikasikan $A\times B$.
  Oleh karena itu contoh ini merupakan contoh tipikal penghitungan dalam dua cara.
• Contoh 2. Misalkan $n$ adalah bilangan bulat ganjil yang lebih besar dari $1$, dan misalkan $k_1,k_2,…,k_n$ diberikan bilangan bulat. Untuk setiap $n!$ permutasi $a =(a_1,a_2,…,a_n)$ dari $1,2,…,n$, misalkan $$S(a)=\sum_{i=1}^{n}k_ia_i.$$ Buktikan bahwa ada dua permutasi $b$ dan $c$, $b\neq c$, sehingga $n!$ adalah pembagi dari $S(b)-S(c)$.
  Solusi: Misalkan $\sum S(a)$ adalah jumlah $S(a)$ atas semua $n!$ permutasi $a=(a_1,a_2,…,a_n)$. Kita menghitung $\sum S(a)$ mod $n!$ dengan dua cara, salah satunya bergantung pada kesimpulan yang diinginkan yang salah, dan mencapai kontradiksi ketika $n$ ganjil.
  Cara pertama. Pada $\sum S(a)$, $k_1$ dikalikan dengan masing-masing $i\in\{1,2,…,n\}$ sebanyak $(n-1)!$ kali, sekali untuk setiap permutasi $\{1,2,…,n\}$ dimana $a_1=i$. Dengan demikian, koefisien $k_1$ pada $\sum S(a)$ adalah $$(n-1)!(1+2+…+n)=\frac{(n+1)!}{2}.$$ Jumlahnya benar untuk semua $k_i$, jadi $$\sum S(a)=\frac{(n+1)!}{2}\sum_{i=1}^{n}k_i.\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.1)$$ Cara kedua. Jika $n!$ bukan pembagi $S(b)-S(c)$ untuk setiap $b\neq c$, maka setiap $S(a)$ harus memiliki sisa yang berbeda mod $n!$. Karena terdapat $n!$ permutasi, sisa-sisa ini harus berupa angka $1, 2,…,n!-1$. Jadi, $$\sum S(a)\equiv \frac{(n!-1)(n!)}{2}\text{ }\text{ }\text{ }(\text{mod }n!)\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.2)$$ Kombinasi (29.1) dan (29.2), kita memperoleh $$\frac{(n+1)!}{2}\sum_{i=1}^{n}k_i\equiv \frac{(n!-1)(n!)}{2}\text{ }\text{ }\text{ }(\text{mod }n!)\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.3)$$ Sekarang, untuk $n$ ganjil, ruas kiri persamaan (29.3) kongruen dengan 0 mod $n!$, sedangkan untuk ganjil $n>1$, ruas kanan persamaan (29.3) tidak kongruen dengan $0$ mod $n!$ ($n!-1$ ganjil). Kita memiliki kontradiksi.
• Contoh 3. Misalkan $2\le r\le \frac{n}{2},Z_n=\{1,2,…,n\},\mathcal{A}$ merupakan keluarga himpunan yang terdiri dari himpunan bagian-bagian berelemen $r$ dari $Z_n$. Jika dua elemen di $\mathcal{A}$ memiliki irisan tak kosong, buktikan bahwa $\mathcal{A}\le \binom{n-1}{r-1}$, dengan persamaan berlaku jika $$\mathcal{A}=\{A|A \text{ adalah himpunan berelemen $r$ dari $Z_n$ dan berisi elemen tetap $x$ dari $Z_n$}.$$
  Solusi: Ada $(n-1)!$ cara untuk menyusun elemen-elemen di $Z_n$ dalam sebuah lingkaran. Untuk setiap permutasi $\pi_j(j=1,2,…,(n-1)!)$, jika semua elemen $A_i\in\mathcal{A}$ muncul berurutan di $\pi_j$, maka buatlah pasangan $(A_i,\pi_j)$. Dengan $S$, kita menyatakan himpunan semua pasangan tersebut.
  Karena dua elemen di $\mathcal{A}$ mempunyai irisan yang tidak kosong, dan angka $2\le r\le \frac{n}{2},\pi_j$ muncul paling banyak $r$ kali di $S$, maka $$|S|\le r\cdot[(n-1)!].\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.4)$$ Di sisi lain, untuk setiap $A_i\in\mathcal{A}$, ada $(r!)[(n-r)!]$ permutasi $\pi_j$, sehingga semua elemen $A_i\in\mathcal{A}$ muncul secara berurutan di $\pi_j$, oleh karena itu $$|S|=|\mathcal{A}|\cdot(r!)\cdot[(n-r)!].\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.5)$$ Kombinasi (29.4) dan (29.5), kita peroleh $$|\mathcal{A}|\cdot(r!)\cdot[(n-r)!]\le r\cdot[(n-1)!],$$ $$∴|\mathcal{A}|\le \frac{(n-1)!}{[(r-1)!][(n-r)!]}=\binom{n-1}{r-1}.$$ Selanjutnya, kita memiliki $|\mathcal{A}|=\binom{n-1}{r-1}$ jika $$\mathcal{A}=\{A|A\text{ adalah himpunan bagian berelemen $r$ dari $Z$ dan berisi elemen tetap $Z$}\},$$ maka persamaan berlaku.
• Contoh 4. Misalkan $P$ adalah titik sembarang di dalam poligon beraturan $n$ sisi $A_1A_2…A_n$, dan misalkan garis $A_iP$ berpotongan dengan batas $A_1A_2…A_n$ di $B_i,i=1,2,…,n$. Buktikan bahwa $\sum_{i=1}^{n}PA_i\ge \sum_{i=1}^{n}PB_i.$
  Solusi: Misalkan $t=\left\lfloor \frac{n}{2} \right\rfloor$ dan $A_{n+j}=A_j,j=1,2,…,n$. Misalkan $d$ adalah panjang diagonal terpanjang dari $A_1A_2…A_n$, maka $$A_iP+PB_i=A_iB_i\le d,\text{ }\text{ }\text{ }\text{ }\text{ }i=1,2,…,n.\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.6)$$ Di sisi lain, dari pertidaksamaan segitiga, $$A_iP+PA_{i+t}\ge A_iA_{i+t}=d,\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }i=1,2,…,n.\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(29.7)$$ Untuk masing-masing (29.6) dan (29.7), dengan mengambil penjumlahan pada $i$ dari $1$ sampai $n$, maka dapat disimpulkan bahwa $$\sum_{i=1}^{n}(A_iP+PA_{i+1})\ge nd\ge \sum_{i=1}^{n}(A_iP+PB_i)$$ $$\Rightarrow 2\sum_{i=1}^{n}PA_i\ge\sum_{i=1}^{n}PA_i+\sum_{i=1}^{n}PB_i\Rightarrow \sum_{i=1}^{n}PA_i\ge\sum_{i=1}^{n}PB_i.$$ 

Aplikasi Metode Rekursif dalam Penghitungan

• Contoh 5. Tiga orang $A, B,$ dan $C$ bermain mengoper bola basket dari satu orang ke orang lain. Temukan banyaknya cara mengoper bola dimulai dengan $A$ dan mencapai $A$ lagi pada operan ke-$11$. Misalnya, salah satu kemungkinan urutan operan adalah $$A\to B\to A\to B\to C\to A\to B\to C\to B\to C\to B\to A.$$
  Solusi: Untuk setiap bilangan bulat positif $n\ge 1$, misalkan $s_n$ adalah banyaknya cara bola basket mencapai $A$ pada operan ke-$n$. Maka $s_1 = 0$. Karena ada total $2^n$ cara berbeda untuk menyelesaikan $n$ operan tanpa batasan, maka $$s_{n+1}=2^n-s_n.$$ Karena $s_1=0,s_2=2$, kita memiliki 
  
  
  Maka jawabannya adalah $682$.
• Contoh 6. Misalkan $a_1,a_2,…,a_n$ adalah permutasi dari $1,2,…,n$ yang memenuhi 
  (1) $a_1=1,$          (2) $|a_i-a_{i-1}|\le 2,i=2,3,…,n.$
  Jika kita misalkan $f(n)$ menyatakan banyaknya permutasi, tentukan sisa $f(2010)$ jika dibagi $3$.
  Solusi: Dapat diverifikasi bahwa $f(1)=f(2)=1,f(3)=2$. Untuk $n\ge 4, a_1=1\Rightarrow a_2=2$ atau $3$.
  Ketika $a_2=2$, jumlah permutasi yang diizinkan adalah $f(n-1)$, karena kita dapat memperoleh permutasi yang diizinkan dengan menghilangkan $a_1$ dan menggunakan $a_i-1$ untuk mengganti $a_i$ dengan $2\le i\le n$, dan korespondensi ini adalah satu-satu.
  Ketika $a_2=3$, maka $a_3=2$ atau $s_3\neq 2$. Jika $a_3=2$, maka jumlah permutasi yang diizinkan adalah $f(n-3)$. Jika $a_3\neq 2$, maka angka $2$ harus disusun di belakang angka $4$, dan setelah susunan bilangan ganjil yang meningkat, susunan bilangan genap yang menurun diikuti, yaitu terdapat tepat satu permutasi tersebut. Dengan demikian, $$f(n)=f(n-1)+f(n-3)+1.$$ Misalkan $r(n)$ adalah sisa $f(n)$ modulo $3$ untuk $n=1,2,…$. Maka $r(1)=r(2)=1,r(3)=2$, dan untuk $n\ge 4,$ $$r(n)\equiv r(n-1)+r(n-3)+1\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(\text{mod }3).$$ Untuk $n=1,2,3,…,11,$ maka urutannya adalah $1,1,2,1,0,0,2,0,1,1,2,$ sehingga deret $\{r(n)\}$ bersifat periodik dan $8$ adalah periode minimumnya. Dengan demikian, sejak tahun $2010\equiv 2$ (mod $8$), $$r(2010)=r(2)=1,\text{ }\text{ }\text{ yaitu sisa dari $f(2010)$ mod $3$ adalah $1$}.$$
• Contoh 7. Bila kita menaruh $n$ bola yang diberi tanda $1$ sampai $n$ ke dalam $n$ kotak yang diberi tanda $1$ sampai $n$, sehingga setiap kotak berisi satu bola, berapa banyak cara agar pada setiap kotak, tanda bola tidak sama dengan tanda kotaknya?
  Solusi: Misalkan kotak-kotak tersebut disusun dalam urutan menaik, perhatikan hanya susunan $n$ bola di bawah ini. Jika jumlah bola dan kotaknya sama-sama $n$, misalkan $A_n$ adalah himpunan semua susunan $n$ bola yang memenuhi persyaratan, dan $|A_n| = a_n$.
  Sekarang perhatikan relasi rekursif antara $a_{n-1},a_n$ dan $a_{n+1}$ sebagai berikut. Untuk setiap susunan dalam $A_n$, kita dapat menempatkan bola berlabel $n+1$ ke dalam kotak $k$ dan bola di kotak $k$ ke dalam kotak $n+1$ untuk $1\le k\le n$, maka susunan $na_n$ ini adalah $A_{n+1}$.
  Di antara semua susunan $n$ bola, jika hanya bola $k$ yang berada di kotak $k$ dan $n-1$ bola lainnya tidak berada di kotak berlabel sama dengan bola, jumlah susunan tersebut adalah $a_{n-1}$. Dengan memasukkan bola $n+1$ ke dalam kotak $k$ dan memasukkan bola $k$ ke dalam kotak $n+1$, diperoleh total $na_{n-1}$ susunan lain di $A_{n+1}$. Dengan demikian, $$a_{n+1}=na_n+na_{n-1},n=2,3,….$$ Jelas bahwa $a_1=0,a_2=1$. Misalkan $a_n(n!)b_n,n\ge 1$, maka $b_1=0,b_1=\frac{1}{2}$ dan $$(n+1)b_{n+1}=nb_n+b_{n-1}\Rightarrow b_{n+1}-b_n=-\frac{1}{n+1}(b_n-b_{n-1}),$$ maka $$\prod_{k=2}^{n-1}(b_{k+1}-b_k)=\prod_{k=2}^{n-1}\left[-\frac{1}{k+1}(b_k-b_{k-1})\right]$$ $$\Rightarrow b_n=\sum_{i=2}^{n}(b_i-b_{i-1})=\sum_{i=2}^{n}(-1)^i\cdot\frac{1}{i!}=\sum_{i=0}^{n}(-1)^i\frac{1}{i!}.$$
  Maka, $a_n=n!\sum_{i=0}^{n}(-1)^i\frac{1}{i!}.$
• Contoh 8. Kumpulan $2011$ lingkaran membagi bidang menjadi $N$ bagian sedemikian rupa sehingga setiap pasangan lingkaran berpotongan di dua titik dan tidak ada titik yang terletak pada tiga lingkaran. Temukan empat digit terakhir dari $N$.
  Solusi: Misalkan $a_n$ adalah jumlah daerah yang diperoleh dari $n$ lingkaran yang dibagi sedemikian rupa sehingga setiap pasangan lingkaran berpotongan di dua titik dan tidak ada titik yang terletak pada tiga lingkaran. Ketika jumlah lingkaran dari $n$ bertambah menjadi $n+1$, karena terdapat $2n$ titik potong pada lingkaran ke-$n+1$, ​​lingkaran tersebut terbagi menjadi $2n$ busur, dan setiap busur membagi satu daerah menjadi dua, sehingga $a_1=2$ dan $$a_{n+1}=a_n+2n\Rightarrow a_n=\sum_{k=1}^{n-1}(a_{k+1}-a_k)=2\sum_{k=1}^{n-1}k\Rightarrow a_n =2+(n-1)n.$$ Maka, $$N=a_{2011}=2+2010\cdot 2011=4042112\Rightarrow \text{ empat digit terakhirnya adalah }2011.$$