Pembahasan Soal 3 Prinsip Inklusi-Eksklusi

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

        \[|A^{c}\cap B^{c} \cap C^{c}| .\]

    Dengan Prinsip Inklusi-Eksklusi, akan ditentukan banyak solusinya dari |A^{c}\cap B^{c} \cap C^{c}|.
    Diperoleh,

        \[|A^{c} \cap B^{c} \cap C^{c}| = |S| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C | - | A \cap B \cap C|.\]

  • Selanjutnya, akan dicari solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x \geq 7 \\ (x-5) \geq 0 \\ x_1 \geq 0, \text{untuk} \ x_1 = x-7 \end{array}.\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 7) + y + z &= 12 - 7 \\ x_1 + y + z &= 5 \\ \end{align*}

    Untuk x_1,y,z \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|A| = \binom{5+3-1}{5} = \binom{7}{5} = 21.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} y \geq 7 \\ (y-7) \geq 0 \\ y_1 \geq 0, \text{untuk} \ y_1 = y-7 \end{array}.\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ x + (y - 7) + z &= 12 - 7 \\ x + y_1 + z &= 5 \\ \end{align*}

    Untuk x,y_1,z \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|B| = \binom{5+3-1}{5} = \binom{7}{5} = 21.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} z \geq 4 \\ (z-4) \geq 0 \\ z_1 \geq 0, \text{untuk} \ z_1 = z-4 \end{array}.\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ x + y + (z - 4) &= 12 - 4 \\ x + y + z_1 &= 8 \\ \end{align*}

    Untuk x,y,z_1 \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|C| = \binom{8+3-1}{8} = \binom{10}{8} = 45.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x \geq 7, y \geq 7 \\ (x-5) \geq 0, (y-7) \geq 0 \\ x_1 \geq 0,y_1 \geq 0, \text{untuk} \ x_1 = x-7 , y_1 = y-7 \end{array}.\]

    Maka,

        \begin{align*} \(x + y + z &= 12 \\ (x - 7) + (y - 7) + z &= 12 - 7 -7 \\ x_1 + y_1 + z &= -2 \\ \end{align*}

    Diperhatikan bahwa, \forall x,y_1,z_1 \geq 0, berlaku x + y_1 + z_1 \geq 0. Sedangkan, pernyataan awal akan ditentukan banyaknya solusi x + y_1 + z_1 = -1, dengan x , y_1 , z_1 \geq 0. Akibatnya, diperoleh -1 \geq 0 , kontradiksi dengan pernyataan awal dimana \forall x,y_1,z_1 \geq 0, berlaku x + y_1 + z_1 \geq 0. Dengan demikian, banyaknya solusi
    x + y + z = 12 dengan kendala y \geq 6 , z \geq 7 yaitu

        \[|A \cap B |=0.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x \geq 7, z \geq 4 \\ (x-7) \geq 0, (z-4) \geq 0 \\ x_1 \geq 0,z_1 \geq 0, \text{untuk} \ x_1 = x-7 , z_1 = z-4 \end{array}.\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 7) + y + (z - 4) &= 12 - 7 - 4 \\ x_1 + y + z_1 &= 1 \\ \end{align*}

    Untuk x_1,y,z_1 \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|A \cap C| = \binom{3+1-1}{1} = \binom{3}{1} = 3.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} y \geq 7, z \geq 4 \\ (y-7) \geq 0, (z-4) \geq 0 \\ y_1 \geq 0,z_1 \geq 0, \text{untuk} \ y_1 = y-7 , z_1 = z-4 \end{array}.\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ x + (y - 7) + (z - 4) &= 12 - 7 - 4 \\ x + y_1 + z_1 &= 1 \\ \end{align*}

    Untuk x,y_1,z_1 \geq 0, menurut Stars and Bars Theorem, diperoleh banyaknya solusi yaitu

        \[|B \cap C| = \binom{3+1-1}{1} = \binom{3}{1} = 3.\]

  • Solusi x + y +z = 12, dengan kendala

        \[\begin{array}{cc} x\geq 7, y \geq 7, z \geq 4 \\ (x-7)\geq 0, (y-7) \geq 0, (z-4) \geq 0 \\ x_1\geq 0, y_1 \geq 0,z_1 \geq 0, \text{ untuk } \ x_1 = x - 7, y_1 = y-7 , z_1 = z-4 \end{array}.\]

    Maka,

        \begin{align*} x + y + z &= 12 \\ (x - 7) + (y - 7) + (z - 4) &= 12 - 7 - 7 - 4 \\ x_1 + y_1 + z_1 &= -6 \\ \end{align*}

    Diperhatikan bahwa, \forall x,y_1,z_1 \geq 0 berlaku x_1 + y_1 + z_1 \geq 0. Sedangkan, pernyataan awal akan ditentukan banyaknya solusi x_1 + y_1 + z_1 = -6, \ \text{dengan} \ x_1 , y_1 , z_1 \geq 0
    Akibatnya, diperoleh -6 \geq 0 , kontradiksi dengan pernyataan awal dimana \forall x_1,y_1,z_1 \geq 0, berlaku x_1 + y_1 + z_1 \geq 0.
    Dengan demikian, banyaknya penyelesaian
    x + y + z = 12 dengan kendala x\geq 5, y \geq 6 , z \geq 7, yaitu

        \[|A \cap B \cap C|=0.\]

Dengan menggunakan Prinsip Inklusi-Eksklusi, diperoleh

    \begin{align*} |A^{c} \cap B^{c} \cap C^{c}| &= |S| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C | - | A \cap B \cap C| \\ &= 91 - (21+21+45)+(0+3+3)-0 \\ &= 10. \end{align*}

Jadi banyaknya solusi dari x + y + z = 12 dengan kendala x \leq 6, y\leq 6, z \leq 4, yaitu sebanyak 10 solusi unik.

 

Credit: Fadhlan Zhaahiran

Leave A Comment

Alamat email Anda tidak akan dipublikasikan.

*