Arsip 2021:

Agustus

Pembahasan Soal 2 Prinsip Sarang Merpati

Tutorial Minggu, 22 Agustus 2021

Soal: Diberikan himpunan A yang terdiri atas 20 bilangan yang diambil dari himpunan S=\{1,4,7,\ldots,100\}. Buktikkan bahwa setidaknya ada 2 bilangan yang dipilih dari A berjumlah 104.

Pembahasan:

Dengan melihat pola dari himpunan S, jelas bahwa S membentuk barisan a_{n}=3n-2,\forall n \in \{1,2,3,\ldots,34\}. Jika a_{i} dan a_{j} adalah dua buah bilangan yang dipilih dari S yang memiliki jumlah 104, maka diperoleh

    \[3i-2+3j-2=140 \iff i+j=36 .\]

Artinya, pernyataan pada soal akan ekuivalen dengan menunjukkan terdapat 20 bilangan yang dipilih dari \{1,2,3,\ldots,34\} maka ada 2 bilangan yang jumlahnya 36. read more

Pembahasan Soal 1 Prinsip Sarang Merpati

Tutorial Minggu, 22 Agustus 2021

Soal: Terdapat 51 bilangan yang dipilih dari bilangan bulat antara 1 dan 100 secara inklusif. Buktikkan bahwa terdapat 2 bilangan yang dipilih adalah berurutan.

Pembahasan:

Dari 100 bilangan tersebut, akan dibagi menjadi 50 partisi, yaitu \{1, 2\}, \{3, 4\},\ldots,\{99, 100\} sebagai sarang merpati. Selanjutnya, dipilih 51 bilangan sebagai merpati. Dengan menggunakan prinsip sangkar burung, maka terdapat \lceil \frac{51}{50} \rceil =2 bilangan yang berurutan.

Terbukti bahwa jika 51 bilangan yang dipilih dari bilangan bulat antara 1 dan 100 secara inklusif, maka terdapat 2 bilangan dari bilangan bulat yang dipilih adalah berurutan. read more

Pembahasan Soal 4 Prinsip Inklusi-Eksklusi

Tutorial Minggu, 22 Agustus 2021

File Tayangan

Soal: 

Tentukan banyaknya permutasi dari himpunan \{1, 2,\ldots, 9\} dimana paling tidak terdapat satu bilangan ganjil yang berada pada urutan aslinya.

Contoh : angka 1 diletakan pada urutan pertama, angka 2 diletakan pada urutan kedua.

Pembahasan:

Petama-tama, dipilih satu bilangan ganjil dan diletakan kedalam urutan aslinya, diperoleh banyaknya cara yaitu \binom{5}{1} = 5 cara dan permutasikan terhadap 8 bilangan lainnya, diperoleh 8! cara, dengan prinsip permutasi perkalian didapat total caranya yaitu 5\times 8!. Dipilih dua bilangan ganjil dan diletakan kedalam urutan aslinya, diperoleh banyaknya cara yaitu \binom{5}{2} = 10 cara dan permutasikan terhadap 7 bilangan lainnya, diperoleh 7! cara, dengan prinsip permutasi perkalian didapat total caranya yaitu 10\times7!.
Selanjutnya, dipilih tiga bilangan ganjil dan diletakan kedalam urutan aslinya, diperoleh banyaknya cara yaitu \binom{5}{3} = 10 cara dan permutasikan terhadap 6 bilangan lainnya, diperoleh 7! cara, dengan prinsip permutasi perkalian didapat total caranya yaitu 10\times 6!. Dipilih empat bilangan ganjil dan diletakan kedalam urutan aslinya, diperoleh banyaknya cara yaitu \binom{5}{4} = 5 cara dan permutasikan terhadap 5 bilangan lainnya, diperoleh 5! cara, dengan prinsip permutasi perkalian didapat total caranya yaitu 5\times 5!. Dipilih lima bilangan ganjil dan diletakan kedalam urutan aslinya, diperoleh banyaknya cara yaitu \binom{5}{5} = 1 cara dan permutasikan terhadap 4 bilangan lainnya, diperoleh 4! cara, dengan prinsip permutasi perkalian didapat total caranya yaitu 1\times4!. read more

Pembahasan Soal 3 Prinsip Inklusi-Eksklusi

Tutorial Minggu, 22 Agustus 2021

File Tayangan

Soal: A bakery sells chocolate, cinnamon, and plain doughnuts and at a particular time has 6 chocolate, 6 cinnamon, and 3 plain. If a box contains 12 doughnuts, how many different option are there for a box of doughnuts?

Pembahasan:

Dari informasi pada soal, didapat multiset T=\{6\cdot x,\cdot y,3\cdot z \}, dengan x adalah coklat, y adalah cinnamon, z plain. Akan dicari banyaknya solusi dari

    \[x+y+z=12\]

dengan x\leq6,y\leq6,z\leq3 .
Dinotasikan

    \begin{align*} \begin{cases} A = \{x\in\mathbb{Z}|x+y+z=12,x\geq 7\} \\ B = \{ y\in\mathbb{Z}|x+y+z=12, y\geq 7\} \\ C = \{z\in\mathbb{Z}|x+y+z=12,z\geq 4\} \\ \end{cases} \end{align*}

Untuk x,y,z \geq 0, menurut Stars and Bars theorem, diperoleh banyaknya solusi, yaitu

    \[|S| =\binom{3+12-1}{12} = \binom{14}{12} = 91 .\]

Untuk memperoleh himpunan x \leq 6, y \leq 6, z \leq 3, yaitu irisan dari negasi ketiga himpunan tersebut. Dinotasikan read more

Pembahasan Soal 2 Prinsip Inklusi-Eksklusi

Tutorial Minggu, 22 Agustus 2021

File Tayangan

Soal: Tentukan banyaknya bilangan dari 1 sampai 70 yang relatif prima terhadap 70.

Pembahasan:

Diketahui bahwa pembagi prima dari 70 yaitu 2,5, dan 7. Selanjutnya, di defenisikan A adalah himpunan bilangan bulat yang habis dibagi 2, B adalah himpunan bilangan bulat yang habis dibagi 5, A adalah himpunan bilangan bulat yang habis dibagi 7. Akan dicari banyaknya bilangan dari 1 sampai 70 yang relatif prima terhadap 70 yaitu |A^{c}\cup B^{c} C^{c}|.

Diperoleh, read more

Pembahasan Soal 1 Prinsip Inklusi-Eksklusi

Tutorial Minggu, 22 Agustus 2021

File Tayangan

Soal: Tentukan banyaknya bilangan bulat dari 1 hingga 2021 yang tidak habis dibagi 4,6, dan 9.

Pembahasan:

Dinotasikan himpunan :

    \begin{align*} \begin{cases} A &= \{x\in\mathbb{Z}\mid 1 \leq x \leq 2021, \textit{x} \ \text{habis dibagi} \ 4 \} \\ B &= \{x\in\mathbb{Z}\mid 1 \leq x \leq 2021, \textit{x} \ \text{habis dibagi} \ 6\} \\ C &= \{x\in\mathbb{Z}\mid 1 \leq x \leq 2021, \textit{x} \ \text{habis dibagi} \ 9\} \end{cases} \end{align*}

Akan ditentukan banyaknya bilangan bulat antara 1 dan 2021 yang tidak habis dibagi 4,6, dan 9, yaitu |A^{c} \cup B^{c} \cup C^{c}|.
Diperoleh,

    \begin{align*} |A| &= \lfloor\frac{2021}{4}\rfloor =505 & |B| &= \lfloor\frac{2021}{6}\rfloor = 336\\ |C| &= \lfloor\frac{2021}{9}\rfloor = 224 & |A\cap B| &= \lfloor\frac{2021}{12}\rfloor = 168 \\ |B\cap C| &= \lfloor\frac{2021}{18}\rfloor = 224 & |A\cap C| &= \lfloor\frac{2021}{36}\rfloor = 56 \\ |A\cap B \cap C| &= \lfloor\frac{2021}{36}\rfloor = 56 & |S| = 2019 \end{align*}

Dengan menggunakan Prinsip Inklusi-Eksklusi, diperoleh

    \begin{align*} |A^{c} \cup B^{c} \cup C^{c}| &= |S| - \Bigg(|A|+|B|+|C|-\Big(|A\cap B|+|A\cap C|+|B \cap C|\Big)+|A\cap B \cap C|\Bigg) \\ &= 1234. \end{align*}

Credit: Fadhlan Zhaahiran

Pembahasan Soal 5 Teorema Binomial

Tutorial Minggu, 22 Agustus 2021

File Tayangan

Soal: Berikan bukti kombinatorika untuk membuktikkan persamaan

    \[n^{3} = 6 \binom{n}{3} + 6 \binom{n}{2} + \binom{n}{1} .\]

Pembahasan:

Ruas kiri:

Diberikan himpunan S yang terdiri dari 3 elemen, yang dipilih dari himpunan \{1,2,\ldots,n\} maka banyaknya cara memilih tiap elemen nya adalah

    \[n\times n\times n = n^3 .\]

Ruas kanan:

Jika 3 elemen dari S yang dipilih dari himpunan \{1,2,\ldots,n\}, di mana

  • Jika semua elemen berbeda
    Banyak cara memilihnya yaitu n\times (n-1)\times(n-2).
  • Jika semua elemen adalah sama
    Banyak cara memilihnya yaitu n\times(1)\times(1) = n.
  • Jika dua dari 3 element adalah sama
    Banyak cara memilihnya yaitu \binom{3}{1} \times n\times(n-1)\times 1= 3n(n-1).
    • read more

    Pembahasan Soal 4 Teorema Binomial

    Tutorial Minggu, 22 Agustus 2021

    File Tayangan

    Soal: Diberikan bilangan bulat positif n, buktikkan bahwa

        \[ \binom{2n}{2} = 2 \binom{n}{2} + n^2\]

    a). dengan manipulasi aljabar,
    b). dengan argumentasi kombinatorial.

    Pembahasan:

    a. Diperoleh,

        \begin{align*} \binom{2n}{2} &= \frac{(2n)!}{2! (2n-2)!} \\ &= 2n^2 - n \\ &= n(n-1) + n^2 \\ &= 2 \frac{n(n-1)(n-2)!}{2!(n-2)!} + n^2 \\ &= 2\binom{n}{2} + n^2 \end{align*}

    b. Misalkan pada suatu kelas terdiri atas 2n mahasiswa di mana terdapat n anak laki-laki dan n anak perempuan. Ingin memilih ketua kelas dan wakil ketua kelas secara acak. Maka banyak cara memilih ketua kelas dan wakil ketua kelas yaitu

        \[\displaystyle\binom{2n}{n} .\]

    Diperhatikan bahwa, terdapat cara lain untuk memilih nya, yaitu: read more

    Pembahasan Soal 3 Teorema Binomial

    Tutorial Minggu, 22 Agustus 2021

    File Tayangan

    Soal: Diberikan n \in \mathbb{N,} buktikkan bahwa

        \[\sum_{k=1}^{n} k(n+1-k) = \binom{n+2}{3} .\]

    Pembahasan:

    Dengan manipulasi aljabar, diperoleh

        \begin{align*} \sum_{k=1}^{n} k(n+1-k) &=(n+1) \sum_{k=1}^{n} k - \sum_{k=1}^{n} k^2 \\ &= (n+1) \frac{n(n+1)}{2} - \frac{n(n+1)(2n+1)}{6} \\ &= \frac{n(n+1)(n+2)}{6} \\ &= \binom{n+2}{3} \end{align*}

    Persamaan tersebut juga dapat dibuktikan dengan argumentasi kombinatorial.
    Misalkan terdapat n+2 orang yang akan ditempatkan pada sebuah bangku yang sejajar. Banyak cara untuk memilih kombinasi 3 orang dari n+2 kapasitas bangku yaitu sebanyak \displaystyle\binom{n+2}{3}.
    Diperhatikan bahwa, terdapat cara lain untuk memilihnya. Akan dibagi menjadi beberapa kasus berdasarkan elemen tengah dari tiga buah subset. Misalkan \{a,b,c\} yang telah diurutkan sedemikian sehingga b selalu di antara a dan c. Karena b selalu di antara a dan c artinya b hanya boleh ditempatkan pada urutan ke-2 sampai urutan ke-n+1. read more

    Pembahasan Soal 2 Teorema Binomial

    Tutorial Minggu, 22 Agustus 2021

    File Tayangan

    Soal: Tentukan koefisien x^{12} pada ekspansi \displaystyle\left( x + y + \frac{1}{y}\right)^{20}.

    Pembahasan:

    Misalkan n merupakan bilangan asli, Maka untuk semua x_{1},x_{2},\ldots,x_{k} berlaku

        \[(x_{1}+x_{2} + \ldots + x_{m})^{n} = \sum \frac{n!}{k_{1}! k_{2}! \cdots k_{m}!} x_{1}^{k_{1}} x_{2}^{k_{2}} \cdots x_{m}^{k_{m}}.\]

    Menurut teorema multinomial di atas, diperoleh koefisien x^{12} pada ekspansi \left(x + y + \frac{1}{y}\right)^{12} adalah

        \[ \displaystyle\binom{20}{12,8,4} =\binom{20}{12} \binom{12}{8} \binom{4}{4} = 125970 \times 70 \times 1 = 8817900 .\]

    Credit: Fadhlan Zhaahiran