Lewati ke konten utama
Gambar logo

Matematika Diskret Sebuah Pengantar Terbuka, Edisi Keempat

Oscar Levin

Lampiran B Penyelesaian Terpilih

1 Logika dan Pembuktian
1.1 Pernyataan Matematis
Soal Latihan

7.

Penyelesaian.
\(P(11)\) adalah pernyataan “\(16\cdot 11 + 1\) genap”, yang bernilai salah. Dengan demikian, pernyataan \(\forall x P(x)\) salah (misalnya, 11 merupakan contoh penyangkal). Namun, kita tidak dapat menyimpulkan apa pun tentang \(\exists x P(x)\) karena kita tidak mengetahui nilai kebenaran \(P(x)\) untuk unsur semesta pembicaraan lainnya. Dalam kasus ini, \(\exists x P(x)\) ternyata benar (misalnya, karena \(P(1)\) benar).

8.

Penyelesaian.
\(P(13)\) adalah pernyataan “\(9\cdot 13 + 1\) genap”, yang bernilai benar. Dengan demikian, pernyataan \(\exists x P(x)\) benar (misalnya, 13 merupakan salah satu \(x\) tersebut). Namun, kita tidak dapat menyimpulkan apa pun tentang \(\forall x P(x)\) karena kita tidak mengetahui nilai kebenaran \(P(x)\) untuk semua unsur semesta pembicaraan. Dalam kasus ini, \(\forall x P(x)\) ternyata salah (misalnya, karena \(P(4)\) salah).

Latihan Tambahan

1.

Penyelesaian.
  1. \(P \wedge Q\text{.}\)
  2. \(P \imp \neg Q\text{.}\)
  3. Jack lulus matematika atau Jill lulus matematika (atau keduanya).
  4. Jika Jack dan Jill tidak keduanya lulus matematika, maka Jill lulus.
    1. Tidak ada kesimpulan tambahan.
    2. Jack juga tidak lulus matematika.

2.

Penyelesaian.
  1. \(\neg \exists x (E(x) \wedge O(x))\text{.}\)
  2. \(\forall x (E(x) \imp O(x+1))\text{.}\)
  3. \(\exists x(P(x) \wedge E(x))\) (dengan \(P(x)\) berarti “\(x\) prima”).
  4. \(\forall x \forall y \exists z(x \lt z \lt y \vee y \lt z \lt x)\text{.}\)
  5. \(\forall x \neg \exists y (x \lt y \lt x+1)\text{.}\)

1.2 Implikasi
Soal Latihan

1.

Penyelesaian.
Hal utama yang perlu disadari adalah bahwa kita tidak mengetahui warna kedua bangun tersebut, tetapi kita mengetahui bahwa salah satu dari tiga kasus berikut terjadi: bangun belah ketupat berwarna ungu dan bangun lingkaran berwarna biru; bangun belah ketupat tidak berwarna ungu, tetapi bangun lingkaran berwarna biru; atau bangun belah ketupat tidak berwarna ungu dan bangun lingkaran tidak berwarna biru. Kasus ketika bangun belah ketupat berwarna ungu tetapi bangun lingkaran tidak berwarna biru tidak mungkin terjadi karena kasus itu akan membuat pernyataan tersebut salah.

2.

Penyelesaian.
Satu-satunya cara agar implikasi \(P\rightarrow Q\) benar sedangkan konversnya salah adalah ketika \(Q\) benar dan \(P\) salah. Dengan demikian, kita mengetahui bahwa bangun persegi berwarna ungu dan bangun lingkaran tidak berwarna jingga.

3.

Penyelesaian.
Konversnya adalah "Jika saya memberi Anda seekor sapi, maka Anda akan memberi saya kacang ajaib." Kontraposisinya adalah "Jika saya tidak memberi Anda seekor sapi, maka Anda tidak akan memberi saya kacang ajaib." Semua pernyataan lainnya bukan konvers maupun kontraposisi.

Latihan Tambahan

1.

Penyelesaian.
  1. Setiap bilangan genap yang ditambah 2 merupakan bilangan genap.
  2. Untuk setiap \(x\text{,}\) terdapat \(y\) sedemikian sehingga \(\sin(x) = y\text{.}\) Dengan kata lain, setiap bilangan \(x\) berada dalam domain sinus.
  3. Untuk setiap \(y\text{,}\) terdapat \(x\) sedemikian sehingga \(\sin(x) = y\text{.}\) Dengan kata lain, setiap bilangan \(y\) berada dalam daerah hasil sinus (pernyataan ini salah).
  4. Untuk sembarang dua bilangan, jika pangkat tiga kedua bilangan itu sama, maka kedua bilangan tersebut sama.

3.

Penyelesaian.
  1. Jika berat badan Anda telah turun, maka Anda berolahraga.
  2. Jika Anda berolahraga, maka berat badan Anda akan turun.
  3. Jika Anda orang Amerika, maka Anda bersifat patriotik.
  4. Jika Anda bersifat patriotik, maka Anda orang Amerika.
  5. Jika suatu bilangan rasional, maka bilangan tersebut real.
  6. Jika suatu bilangan tidak genap, maka bilangan tersebut prima. (Atau kontraposisinya: Jika suatu bilangan tidak prima, maka bilangan tersebut genap.)
  7. Jika Broncos tidak memenangi Super Bowl, maka mereka tidak bermain dalam Super Bowl. Sebagai bentuk alternatif, jika Broncos bermain dalam Super Bowl, maka mereka akan memenangi Super Bowl.

5.

Penyelesaian.
Agar suatu fungsi terdiferensialkan di titik \(c\text{,}\) fungsi tersebut perlu kontinu di \(c\text{.}\) Namun, agar suatu fungsi kontinu di \(c\text{,}\) fungsi tersebut tidak perlu terdiferensialkan di \(c\text{.}\)
Agar suatu fungsi kontinu di titik \(c\text{,}\) cukup jika fungsi tersebut terdiferensialkan di \(c\text{.}\) Namun, kontinuitas di \(c\) tidak cukup untuk menjamin bahwa suatu fungsi terdiferensialkan di \(c\text{.}\)

1.3 Aturan Logika
Soal Latihan

1.

Penyelesaian.
Jika Anda mempertimbangkan makna pernyataan ini, wajar bahwa pernyataan tersebut merupakan tautologi (benar dalam setiap kasus). Tabel kebenaran lengkapnya adalah sebagai berikut.
\(P\) \(Q\) \(P \wedge Q\) \(P \vee Q\) \((P \wedge Q) \rightarrow (P \vee Q))\)
B B B B B
B S S B B
S B S B B
S S S S B

2.

Penyelesaian.
Tabel kebenaran lengkapnya adalah sebagai berikut.
\(P\) \(Q\) \(\neg Q\) \(Q \rightarrow P\) \(\neg Q \vee (Q \rightarrow P)\)
B B S B B
B S B B B
S B S S S
S S B B B
Jika pernyataan ini salah, kita harus berada pada baris ketiga sehingga \(P\) salah dan \(Q\) benar.

3.

Penyelesaian.
Tabel kebenaran lengkapnya adalah sebagai berikut.
\(P\) \(Q\) \(R\) \(\neg P\) \(Q \rightarrow R\) \(\neg P \wedge (Q \rightarrow R)\)
B B B S B S
B B S S S S
B S B S B S
B S S S B S
S B B B B B
S B S B S S
S S B B B B
S S S B B B

4.

Penyelesaian.
Tabel kebenaran lengkapnya adalah:
\(P\) \(Q\) \(R\) \(P \rightarrow (Q \vee R)\) \((P \rightarrow Q) \vee (P\rightarrow R)\)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T T
F T F T T
F F T T T
F F F T T
Karena kedua kolom tersebut identik, kedua pernyataan itu ekuivalen secara logis.

5.

Penyelesaian.
Tabel kebenaran lengkapnya adalah:
\(P\) \(Q\) \(P \rightarrow Q\) \(\neg Q\) \(\neg P\)
T T T F F
T F F T F
F T T F T
F F T T T
Hanya ada satu baris yang kedua premisnya benar (baris 4). Pada baris ini, kesimpulannya juga benar. Jadi, aturan deduksi tersebut sahih.

6.

Penyelesaian.
Tabel kebenaran lengkapnya adalah:
\(P\) \(Q\) \(R\) \(P \rightarrow (Q \vee R)\) \(\neg(P \rightarrow Q)\)
T T T T F
T T F T F
T F T T T
T F F F T
F T T T F
F T F T F
F F T T F
F F F T F
Hanya ada satu baris yang kedua premisnya benar (baris 3). Pada baris ini, kesimpulannya juga benar, sehingga aturan deduksi tersebut sahih.

7.

Penyelesaian.
Tabel kebenaran lengkapnya adalah:
\(P\) \(Q\) \(R\) \((P \wedge Q) \rightarrow R\) \(\neg P \vee \neg Q\) \(\neg R\)
T T T T F F
T T F F F T
T F T T T F
T F F T T T
F T T T T F
F T F T T T
F F T T T F
F F F T T T
Pada baris 3, 5, dan 7, kedua premisnya benar, tetapi kesimpulannya salah. Jadi, aturan deduksi tersebut tidak sahih.

8.

Penyelesaian.
Tabel kebenaran lengkapnya adalah:
\(P\) \(Q\) \(R\) \(P \rightarrow Q\) \(P \wedge \neg Q\)
T T T T F
T T F T F
T F T F T
T F F F T
F T T T F
F T F T F
F F T T F
F F F T F
Tidak ada baris yang kedua premisnya benar (kedua premis ini memang saling berkontradiksi; premis kedua merupakan negasi dari premis pertama). Jadi, pada setiap baris yang kedua premisnya benar (yakni tidak ada baris), kesimpulannya juga benar. Oleh karena itu, aturan deduksi tersebut sahih. (Ini merupakan contoh bahwa apa pun dapat disimpulkan dari sebuah kontradiksi.)

Latihan Tambahan

3.

Penyelesaian.
  1. \(P\text{:}\) Hari ini ulang tahun Anda; \(Q\text{:}\) Akan ada kue. \((P \vee Q) \imp Q\)
  2. Petunjuk: Anda seharusnya memperoleh tiga nilai B dan satu nilai S.
  3. Hanya bahwa akan ada kue.
  4. Hari ini BUKAN ulang tahun Anda!
  5. Hari ini ulang tahun Anda, tetapi tidak akan ada kue.

5.

Penyelesaian.
Buatlah tabel kebenaran untuk masing-masing pernyataan, lalu bandingkan keduanya. Kedua pernyataan tersebut ekuivalen secara logis.

6.

Penyelesaian.
  1. \(P \wedge Q\text{.}\)
  2. \((\neg P \vee \neg Q) \imp (Q \vee \neg R)\) atau, dengan terlebih dahulu mengganti implikasi dengan disjungsi: \((P \wedge Q) \vee (Q \vee \neg R)\text{.}\)
  3. \((P \wedge Q) \wedge (R \wedge \neg R)\text{.}\) Pernyataan ini selalu salah, sehingga juga ekuivalen dengan \(P \wedge \neg P\text{.}\)
  4. Sam adalah perempuan dan Chris adalah laki-laki, atau Chris adalah perempuan.

16.

Penyelesaian.
  1. \(\forall x \exists y (O(x) \wedge \neg E(y))\text{.}\)
  2. \(\exists x \forall y (x \ge y \vee \forall z (x \ge z \wedge y \ge z))\text{.}\)
  3. Ada suatu bilangan \(n\) sehingga setiap bilangan lain lebih besar secara ketat daripada \(n\text{.}\)
  4. Ada suatu bilangan \(n\) yang tidak terletak di antara dua bilangan lain mana pun.

1.4 Pembuktian
Latihan Tambahan

1.

Penyelesaian.
  1. Klaim \(\forall x P(x)\) berarti bahwa \(P(n)\) benar untuk setiap \(n\) dalam semesta pembicaraan. Jadi, satu-satunya cara untuk membuktikan bahwa \(\forall x P(x)\) benar adalah memeriksa atau menunjukkan dengan cara lain bahwa \(P(n)\) benar untuk semua \(n\) dalam semesta tersebut.
  2. Untuk membuktikan bahwa \(\forall x P(x)\) salah, Anda hanya memerlukan satu contoh elemen dalam semesta yang membuat \(P(n)\) salah. Contoh semacam ini sering disebut contoh penyangkal.
  3. Kita hanya mengklaim bahwa terdapat suatu elemen \(n\) dalam semesta pembicaraan yang membuat \(P(n)\) benar. Jika Anda dapat menemukan satu elemen seperti itu, klaim tersebut telah terbukti.
  4. Di sini kita mengklaim bahwa tidak ada elemen yang membuat \(P(n)\) benar. Satu-satunya cara untuk memastikan hal ini adalah membuktikan bahwa setiap elemen dalam semesta membuat \(P(n)\) salah. Perhatikan bahwa tingkat pembuktian yang diperlukan untuk pernyataan ini sama dengan yang diperlukan untuk membuktikan bahwa \(\forall x P(x)\) benar.

2.

Penyelesaian.
  1. Untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a\) atau \(b\) tidak genap, maka \(a+b\) tidak genap.
  2. Untuk semua bilangan bulat \(a\) dan \(b\text{,}\) jika \(a\) dan \(b\) genap, maka \(a+b\) genap.
  3. Terdapat bilangan bulat \(a\) dan \(b\) sedemikian sehingga \(a+b\) genap, tetapi \(a\) dan \(b\) tidak keduanya genap.
  4. Salah. Sebagai contoh, ambil \(a = 3\) dan \(b = 5\text{.}\) Nilai \(a+b = 8\text{,}\) tetapi baik \(a\) maupun \(b\) tidak genap.
  5. Salah, karena kontraposisi ekuivalen dengan pernyataan semula.
  6. Benar. Misalkan \(a\) dan \(b\) bilangan bulat. Asumsikan keduanya genap. Dengan demikian, \(a = 2k\) dan \(b = 2j\) untuk suatu bilangan bulat \(k\) dan \(j\text{.}\) Maka \(a+b = 2k + 2j = 2(k+j)\text{,}\) sehingga bernilai genap.
  7. Benar, karena pernyataan semula salah.

3.

Penyelesaian.
  1. Pembuktian dengan kontradiksi. Awal pembuktian: Andaikan, demi memperoleh kontradiksi, bahwa terdapat bilangan bulat \(x\) dan \(y\) sedemikian sehingga \(x\) merupakan bilangan prima yang lebih besar dari 5 dan \(x = 6y + 3\text{.}\) Akhir pembuktian: … hal ini merupakan suatu kontradiksi, sehingga tidak ada bilangan bulat semacam itu.
  2. Pembuktian langsung. Awal pembuktian: Misalkan \(n\) suatu bilangan bulat. Asumsikan \(n\) merupakan kelipatan 3. Akhir pembuktian: Oleh karena itu, \(n\) dapat ditulis sebagai jumlah bilangan bulat berurutan.
  3. Pembuktian melalui kontraposisi. Awal pembuktian: Misalkan \(a\) dan \(b\) bilangan bulat. Asumsikan \(a\) dan \(b\) genap. Akhir pembuktian: Oleh karena itu, \(a^2 + b^2\) genap.

4.

Penyelesaian.
  1. Pembuktian langsung.
    Bukti.
    Misalkan \(n\) suatu bilangan bulat. Asumsikan \(n\) genap. Dengan demikian, \(n = 2k\) untuk suatu bilangan bulat \(k\text{.}\) Jadi, \(8n = 16k = 2(8k)\text{.}\) Oleh karena itu, \(8n\) genap.
  2. Konversnya salah. Artinya, terdapat bilangan bulat \(n\) sedemikian sehingga \(8n\) genap, tetapi \(n\) ganjil. Sebagai contoh, ambil \(n = 3\text{.}\) Maka \(8n = 24\) genap, tetapi \(n = 3\) ganjil.

5.

Penyelesaian.
  1. Ini merupakan contoh penerapan prinsip sarang merpati. Kita dapat membuktikannya melalui kontraposisi.
    Bukti.
    Misalkan setiap angka muncul paling banyak 6 kali. Jadi, terdapat paling banyak enam angka 1, enam angka 2, dan seterusnya. Jumlah keseluruhannya paling banyak 36 dadu, sehingga tidak mungkin Anda telah melempar ke-40 dadu.
  2. Kita dapat melempar 9 dadu tanpa memperoleh empat angka yang sama maupun empat angka yang semuanya berbeda: tiga angka 1, tiga angka 2, dan tiga angka 3. Kita akan membuktikan bahwa setiap kali 10 dadu dilempar, selalu diperoleh empat angka yang sama atau empat angka yang semuanya berbeda.
    Bukti.
    Misalkan Anda melempar 10 dadu, tetapi TIDAK ada empat hasil lemparan yang sama. Artinya, setiap angka muncul paling banyak tiga kali. Jika hanya ada tiga angka berbeda, jumlah dadunya paling banyak 9, sehingga pasti ada 4 angka berbeda, yang memberikan 4 dadu dengan hasil yang semuanya berbeda.

1.6 Ringkasan Bab

Tinjauan Bab

1.6.1.
Penyelesaian.
\(P\) \(Q\) \(R\) \(\neg P \imp (Q \wedge R)\)
B B B B
B B S B
B S B B
B S S B
S B B B
S B S S
S S B S
S S S S
1.6.2.
Penyelesaian.
Peter tidak tinggi, dan Robert tidak kurus. Keadaan ini harus bersesuaian dengan baris ke-6 pada tabel kebenaran di atas.
1.6.3.
Penyelesaian.
Ya. Untuk melihatnya, buatlah tabel kebenaran bagi setiap pernyataan lalu bandingkan keduanya.
1.6.4.
Penyelesaian.
Buatlah tabel kebenaran yang memuat ketiga pernyataan dalam argumen tersebut:
\(P\) \(Q\) \(R\) \(P \imp Q\) \(P \imp R\) \(P \imp (Q \wedge R)\)
B B B B B B
B B S B S S
B S B S B S
B S S S S S
S B B B B B
S B S B B B
S S B B B B
S S S B B B
Perhatikan bahwa pada setiap baris yang membuat \(P \imp Q\) dan \(P \imp R\) keduanya benar, \(P \imp (Q \wedge R)\) juga benar. Oleh karena itu, setiap kali premis-premis argumen tersebut benar, kesimpulannya juga benar. Dengan kata lain, aturan deduksi tersebut sahih.
1.6.5.
Penyelesaian.
  1. Negasi: Listrik padam, dan makanan tidak rusak.
    Konvers: Jika makanan rusak, maka listrik telah padam.
    Kontraposisi: Jika makanan tidak rusak, maka listrik tidak padam.
  2. Negasi: Pintu tertutup, dan lampu menyala.
    Konvers: Jika lampu padam, maka pintu tertutup.
    Kontraposisi: Jika lampu menyala, maka pintu terbuka.
  3. Negasi: \(\exists x (x \lt 1 \wedge x^2 \ge 1)\)
    Konvers: \(\forall x( x^2 \lt 1 \imp x \lt 1)\)
    Kontraposisi: \(\forall x (x^2 \ge 1 \imp x \ge 1)\text{.}\)
  4. Negasi: Terdapat bilangan asli \(n\) yang prima tetapi tidak soliter.
    Konvers: Untuk setiap bilangan asli \(n\text{,}\) jika \(n\) soliter, maka \(n\) prima.
    Kontraposisi: Untuk setiap bilangan asli \(n\text{,}\) jika \(n\) tidak soliter, maka \(n\) tidak prima.
  5. Negasi: Terdapat fungsi yang dapat didiferensialkan dan tidak kontinu.
    Konvers: Untuk setiap fungsi \(f\text{,}\) jika \(f\) kontinu, maka \(f\) dapat didiferensialkan.
    Kontraposisi: Untuk setiap fungsi \(f\text{,}\) jika \(f\) tidak kontinu, maka \(f\) tidak dapat didiferensialkan.
  6. Negasi: Terdapat bilangan bulat \(a\) dan \(b\) sedemikian sehingga \(a\cdot b\) genap tetapi \(a\) atau \(b\) ganjil.
    Konvers: Untuk setiap bilangan bulat \(a\) dan \(b\text{,}\) jika \(a\) dan \(b\) keduanya genap, maka \(ab\) genap.
    Kontraposisi: Untuk setiap bilangan bulat \(a\) dan \(b\text{,}\) jika \(a\) atau \(b\) ganjil, maka \(ab\) ganjil.
  7. Negasi: Terdapat bilangan bulat \(x\) dan \(y\) sedemikian sehingga untuk setiap bilangan bulat \(n\text{,}\) \(x \gt 0\) dan \(nx \le y\text{.}\)
    Konvers: Untuk setiap bilangan bulat \(x\) dan setiap bilangan bulat \(y\text{,}\) terdapat bilangan bulat \(n\) sedemikian sehingga jika \(nx > y\text{,}\) maka \(x > 0\text{.}\)
    Kontraposisi: Untuk setiap bilangan bulat \(x\) dan setiap bilangan bulat \(y\text{,}\) terdapat bilangan bulat \(n\) sedemikian sehingga jika \(nx \le y\text{,}\) maka \(x \le 0\text{.}\)
  8. Negasi: Terdapat bilangan real \(x\) dan \(y\) sedemikian sehingga \(xy = 0\text{,}\) tetapi \(x \ne 0\) dan \(y \ne 0\text{.}\)
    Konvers: Untuk setiap bilangan real \(x\) dan \(y\text{,}\) jika \(x = 0\) atau \(y = 0\text{,}\) maka \(xy = 0\)
    Kontraposisi: Untuk setiap bilangan real \(x\) dan \(y\text{,}\) jika \(x \ne 0\) dan \(y \ne 0\text{,}\) maka \(xy \ne 0\text{.}\)
  9. Negasi: Terdapat setidaknya seorang mahasiswa dalam Matematika 228 yang tidak memahami implikasi tetapi tetap akan lulus ujian.
    Konvers: Untuk setiap mahasiswa dalam Matematika 228, jika mahasiswa tersebut gagal dalam ujian, maka ia tidak memahami implikasi.
    Kontraposisi: Untuk setiap mahasiswa dalam Matematika 228, jika mahasiswa tersebut lulus ujian, maka ia memahami implikasi.
1.6.6.
Penyelesaian.
  1. Pernyataan tersebut benar. Jika \(n\) merupakan bilangan bulat genap yang kurang dari atau sama dengan 7, maka satu-satunya kemungkinan agar bilangan tersebut tidak negatif adalah \(n\) sama dengan 0, 2, 4, atau 6.
  2. Terdapat bilangan bulat \(n\) sedemikian sehingga \(n\) genap dan \(n \le 7\text{,}\) tetapi \(n\) tidak negatif dan \(n \not\in \{0,2,4,6\}\text{.}\) Pernyataan ini salah karena pernyataan asal benar.
  3. Untuk setiap bilangan bulat \(n\text{,}\) jika \(n\) tidak negatif dan \(n \not\in\{0,2,4,6\}\text{,}\) maka \(n\) ganjil atau \(n > 7\text{.}\) Pernyataan ini benar karena kontraposisi ekuivalen dengan pernyataan asal (yang benar).
  4. Untuk setiap bilangan bulat \(n\text{,}\) jika \(n\) negatif atau \(n \in \{0,2,4,6\}\text{,}\) maka \(n\) genap dan \(n \le 7\text{.}\) Pernyataan ini salah. \(n = -3\) merupakan contoh penyangkal.
1.6.7.
Penyelesaian.
  1. Untuk setiap bilangan \(x\text{,}\) jika penambahan sembarang bilangan pada \(x\) menghasilkan kembali bilangan tersebut, maka perkalian sembarang bilangan dengan \(x\) menghasilkan 0. Pernyataan ini benar (baik pada bilangan bulat maupun bilangan real). Bagian “jika” hanya berlaku apabila \(x = 0\text{,}\) dan dalam hal itu, hasil kali bilangan apa pun dengan \(x\) adalah 0.
  2. Konversnya, dalam kata-kata, adalah: Untuk setiap bilangan \(x\text{,}\) jika hasil kali setiap bilangan dengan \(x\) adalah nol, maka penambahan setiap bilangan pada \(x\) menghasilkan bilangan itu sendiri. Dalam simbol: \(\forall x (\forall z (x \cdot z = 0) \imp \forall y (x + y = y))\text{.}\) Konvers tersebut benar: Satu-satunya bilangan yang menghasilkan 0 ketika dikalikan dengan sembarang bilangan lain adalah \(x = 0\text{.}\) Jika \(x = 0\text{,}\) maka \(x + y = y\text{.}\)
  3. Kontraposisinya, dalam kata-kata, adalah: Untuk setiap bilangan \(x\text{,}\) jika terdapat suatu bilangan yang tidak menghasilkan nol ketika dikalikan dengan \(x\text{,}\) maka terdapat suatu bilangan yang tidak menghasilkan bilangan itu sendiri ketika ditambahkan pada \(x\text{.}\) Dalam simbol: \(\forall x (\exists z (x\cdot z \ne 0) \imp \exists y (x + y \ne y))\text{.}\) Kita mengetahui bahwa kontraposisi tersebut harus benar karena implikasi asal benar.
  4. Negasinya adalah: Terdapat bilangan \(x\) sedemikian sehingga penambahan sembarang bilangan pada \(x\) menghasilkan kembali bilangan tersebut, tetapi terdapat bilangan yang dapat dikalikan dengan \(x\) tanpa menghasilkan 0. Dalam simbol: \(\exists x (\forall y (x + y = y) \wedge \exists z (x \cdot z \ne 0))\text{.}\) Tentu saja, karena implikasi asal benar, negasinya salah.
1.6.8.
Penyelesaian.
  1. \((\neg P \vee Q) \wedge (\neg R \vee (P \wedge \neg R))\text{.}\)
  2. \(\forall x \forall y \forall z (z = x+y \wedge \forall w (x-y \ne w))\text{.}\)
1.6.9.
Penyelesaian.
  1. Pembuktian langsung.
    Bukti.
    Misalkan \(n\) suatu bilangan bulat. Asumsikan \(n\) ganjil. Jadi, \(n = 2k+1\) untuk suatu bilangan bulat \(k\text{.}\) Maka
    \begin{equation*} 7n = 7(2k+1) = 14k + 7 = 2(7k +3) + 1\text{.} \end{equation*}
    Karena \(7k + 3\) merupakan bilangan bulat, kita melihat bahwa \(7n\) ganjil.
  2. Konversnya adalah: Untuk setiap bilangan bulat \(n\text{,}\) jika \(7n\) ganjil, maka \(n\) ganjil. Kita akan membuktikannya melalui kontraposisi.
    Bukti.
    Misalkan \(n\) suatu bilangan bulat. Asumsikan \(n\) tidak ganjil. Maka \(n = 2k\) untuk suatu bilangan bulat \(k\text{.}\) Jadi \(7n = 14k = 2(7k)\text{,}\) yang berarti bahwa \(7n\) genap. Oleh karena itu, \(7n\) tidak ganjil.
1.6.10.
Penyelesaian.
  1. Misalkan Anda hanya memiliki 5 keping untuk setiap denominasi. Artinya, Anda memiliki 5 keping 1 sen, 5 keping 5 sen, 5 keping 10 sen, dan 5 keping 25 sen. Jumlahnya 20 keping. Namun, Anda memiliki lebih dari 20 keping, sehingga sedikitnya satu jenis pasti berjumlah lebih dari 5 keping.
  2. Misalkan Anda memiliki 22 keping, yang mencakup \(2k\) keping 5 sen, \(2j\) keping 10 sen, dan \(2l\) keping 25 sen (jadi, setiap jenis dari ketiga uang logam ini berjumlah genap). Banyaknya keping 1 sen yang Anda miliki adalah
    \begin{equation*} 22 - 2k - 2j - 2l = 2(11-k-j-l)\text{.} \end{equation*}
    Namun, persamaan ini menyatakan bahwa banyaknya keping 1 sen juga genap (karena sama dengan 2 kali suatu bilangan bulat). Dengan demikian, kita telah membuktikan kontraposisi pernyataan tersebut, “Jika Anda memiliki keping 1 sen dalam jumlah ganjil, maka sedikitnya satu jenis uang logam lain juga berjumlah ganjil.”
  3. Anda memerlukan 10 keping. Anda dapat memiliki 3 keping 1 sen, 3 keping 5 sen, dan 3 keping 10 sen. Keping ke-10 pasti merupakan keping 25 sen, sehingga Anda memiliki empat keping yang semuanya berbeda, atau merupakan keping keempat dari denominasi 1 sen, 5 sen, atau 10 sen. Untuk membuktikannya, asumsikan bahwa Anda tidak memiliki empat keping yang semuanya sama ataupun semuanya berbeda. Secara khusus, ini berarti bahwa Anda hanya memiliki tiga jenis uang logam, dan setiap jenis hanya dapat berisi tiga keping, sehingga jumlah keseluruhannya 9 keping, kurang dari 10.

2 Teori Graf
2.1 Masalah dan Definisi
Soal Latihan

4.

Penyelesaian.
Menurut lema jabat tangan, banyaknya sisi adalah setengah dari jumlah derajat simpul-simpul pada graf tersebut. Jumlah derajatnya adalah \(8+8+8+8+8+7+7+7+7 = {68}\text{,}\) sehingga terdapat \({34}\) sisi.

Latihan Tambahan

1.

Penyelesaian.
Pertanyaan ini menanyakan banyaknya sisi pada \(K_{10}\text{.}\) Setiap simpul (orang) berderajat 9 (berjabat tangan dengan 9 orang). Jadi, jumlah derajatnya adalah \(90\text{.}\) Namun, jumlah derajat menghitung setiap sisi (jabat tangan) dua kali, sehingga terdapat 45 sisi pada graf tersebut. Jadi, terjadi 45 jabat tangan.

2.

Penyelesaian.
Setiap orang mungkin saja berteman dengan tepat 2 orang. Anda dapat mengatur kelima orang dalam lingkaran dan menetapkan bahwa setiap orang berteman dengan dua orang di kedua sisinya (sehingga diperoleh graf \(C_5\)). Namun, tidak mungkin setiap orang berteman dengan tepat 3 orang. Hal itu akan menghasilkan graf dengan simpul berderajat ganjil dalam jumlah ganjil, padahal ini mustahil karena jumlah derajat harus genap.

4.

Penyelesaian.
Kedua graf tersebut tidak sama. Sebagai contoh, graf 1 memiliki sisi \(\{a,b\}\text{,}\) sedangkan graf 2 tidak memiliki sisi tersebut. Keduanya isomorfik. Salah satu isomorfisme yang mungkin adalah \(f:G_1 \to G_2\) yang didefinisikan oleh \(f(a) = d\text{,}\) \(f(b) = c\text{,}\) \(f(c) = e\text{,}\) \(f(d) = b\text{,}\) \(f(e) = a\text{.}\)

9.

Penyelesaian.
  1. Sebagai contoh:
    Graf yang terdiri atas satu simpul dengan tiga sisi yang menghubungkannya ke tiga simpul yang berjajar di atasnya.
    Graf yang terdiri atas empat simpul yang tersusun membentuk huruf V. Titik kiri huruf V terhubung ke sudut bawah huruf V. Simpul tersebut terhubung ke simpul yang berada di pertengahan sisi kanan huruf V, yang kemudian terhubung ke simpul pada titik kanan huruf V.
  2. Hal ini tidak mungkin jika graf-graf tersebut disyaratkan terhubung. Jika tidak disyaratkan, kita dapat mengambil \(C_8\) sebagai salah satu graf dan dua salinan \(C_4\) sebagai graf lainnya.
  3. Tidak mungkin. Jika suatu graf memiliki 5 simpul yang semuanya berderajat 4, setiap simpul harus bertetangga dengan setiap simpul lainnya. Graf tersebut adalah \(K_5\text{.}\)
  4. Hal ini tidak mungkin. Bahkan, tidak ada satu pun graf dengan sifat ini (graf semacam itu akan memiliki \(5\cdot 3/2 = 7.5\) sisi).

10.

Penyelesaian.
  1. Salah.
  2. Benar.
  3. Benar.
  4. Salah.

2.2 Pohon
Soal Latihan

3.

Penyelesaian.
Setiap pohon merentang tetap harus memuat 12 simpul. Karena merupakan pohon, pohon merentang tersebut memiliki \(12-1 = 11\) sisi. Jadi, kita harus menghapus 6 sisi untuk memperoleh pohon merentang.

5.

Penyelesaian.
Misalkan \(x\) adalah banyaknya daun. Jumlah derajatnya adalah \(x + 10 +7 + 4 + 2 = x + 23\text{.}\) Nilai ini sama dengan dua kali banyaknya sisi. Karena banyaknya sisi satu lebih sedikit daripada banyaknya simpul, yaitu \(x + 4\text{,}\) kita juga mengetahui bahwa banyaknya sisi adalah \(x+3\text{.}\)
Dengan demikian, kita memperoleh \(2(x+3) = x+23\text{.}\) Menyelesaikan persamaan ini untuk \(x\) menghasilkan \(x = 17\text{.}\)

Latihan Tambahan

1.

Penyelesaian.
  1. Graf ini bukan pohon karena memuat siklus. Perhatikan pula bahwa graf ini memiliki terlalu banyak sisi untuk menjadi pohon, sebab kita mengetahui bahwa setiap pohon dengan \(v\) simpul memiliki \(v-1\) sisi.
  2. Graf ini merupakan pohon karena terhubung dan tidak memuat siklus (yang dapat Anda lihat dengan menggambar graf tersebut). Setiap lintasan merupakan pohon.
  3. Graf ini merupakan pohon karena terhubung dan tidak memuat siklus (gambarlah graf tersebut). Setiap graf bintang merupakan pohon.
  4. Graf ini bukan pohon karena tidak terhubung. Perhatikan bahwa graf ini tidak memiliki cukup sisi untuk menjadi pohon.

2.

Penyelesaian.
  1. Barisan ini pasti merupakan barisan derajat suatu pohon. Alasannya, simpul berderajat 4 harus bertetangga dengan keempat simpul berderajat 1 (tidak ada simpul lain yang dapat menjadi tetangganya), sehingga kita memperoleh graf bintang.
  2. Barisan ini tidak mungkin merupakan barisan derajat suatu pohon. Setiap simpul berderajat 3 bertetangga dengan semua simpul dalam graf kecuali satu. Dengan demikian, masing-masing harus bertetangga dengan salah satu simpul berderajat 1 (dan bukan dengan simpul berderajat 1 yang lain). Artinya, kedua simpul berderajat 3 bertetangga dengan simpul berderajat 2 dan juga saling bertetangga, sehingga terdapat siklus.
    Sebagai alternatif, hitunglah banyaknya sisi!
  3. Barisan ini mungkin merupakan barisan derajat pohon, tetapi mungkin juga bukan. Lintasan dengan panjang 4 memiliki barisan derajat ini (dan merupakan pohon), tetapi gabungan suatu siklus-3 dan lintasan dengan panjang 1 juga memilikinya (graf ini tidak terhubung, sehingga bukan pohon).
  4. Barisan ini tidak mungkin merupakan barisan derajat suatu pohon. Jumlah derajatnya adalah 28, sehingga terdapat 14 sisi. Akan tetapi, terdapat pula 14 simpul, sehingga tidak berlaku \(v = e+1\text{;}\) jadi, graf ini tidak mungkin merupakan pohon.

6.

Penyelesaian.
Ya. Kita akan membuktikan kontraposisinya. Andaikan \(G\) tidak memuat siklus. Maka, \(G\) merupakan pohon sehingga harus memenuhi \(v = e+1\text{,}\) bertentangan dengan ketentuan.

12.

Penyelesaian.
  1. Tidak, meskipun terdapat graf-graf yang memenuhi sifat tersebut. Sebagai contoh, \(K_4\) memiliki pohon merentang berupa lintasan (dengan tiga sisi) dan juga pohon merentang berupa graf bintang (dengan simpul pusat berderajat 3).
  2. Ya. Untuk suatu graf tertentu, banyaknya simpul \(v\) bersifat tetap. Setiap pohon merentang dari graf tersebut juga memiliki \(v\) simpul, dan karena merupakan pohon, pohon merentang itu harus memiliki \(v-1\) sisi.
  3. Tidak, meskipun terdapat graf-graf yang memenuhi sifat tersebut (perhatikan bahwa jika semua pohon merentang saling isomorfik, maka semuanya memiliki jumlah daun yang sama). Sekali lagi, \(K_4\) merupakan contoh penyangkal. Salah satu pohon merentangnya berupa lintasan yang hanya memiliki dua daun, sedangkan pohon merentang lainnya berupa graf bintang dengan 3 daun.

2.3 Graf Planar
Latihan Tambahan

1.

Penyelesaian.
Tidak. Graf planar (terhubung) harus memenuhi rumus Euler: \(v - e + f = 2\text{.}\) Dalam kasus ini, \(v - e + f = 6 - 10 + 5 = 1\text{.}\)

2.

Penyelesaian.
\(G\) memiliki 10 sisi karena \(10 = \frac{2+2+3+4+4+5}{2}\text{.}\) Graf tersebut mungkin planar, dan jika demikian, menurut rumus Euler graf itu akan memiliki 6 muka: \(6-10+f = 2\) berarti \(f = 6\text{.}\) Namun, untuk memastikan bahwa graf tersebut benar-benar planar, kita perlu menggambar graf dengan derajat simpul tersebut tanpa sisi yang berpotongan. Hal ini dapat dilakukan dengan mencoba berbagai kemungkinan (dan memang mungkin).

6.

Penyelesaian.
Misalkan muka terakhir memiliki \(n\) sisi dan juga \(n\) simpul. Dengan demikian, jumlah sisi polihedron tersebut adalah \((7 \cdot 3 + 4 \cdot 4 + n)/2 = (37 + n)/2\text{.}\) Secara khusus, kita mengetahui bahwa muka terakhir harus memiliki jumlah sisi ganjil. Kita juga mengetahui bahwa \(v = 11 \text{.}\) Berdasarkan rumus Euler, berlaku \(11 - (37+n)/2 + 12 = 2\text{,}\) dan dengan menyelesaikannya untuk \(n\text{,}\) kita memperoleh \(n = 5\text{,}\) sehingga muka terakhir berbentuk segilima.

8.

Penyelesaian.
Bukti.
Andaikan terdapat graf \(G\) dengan jumlah sisi paling sedikit yang tidak memenuhi rumus Euler.
Perhatikan bahwa \(G\) tidak mungkin berupa pohon karena untuk setiap pohon berlaku \(v = e+1\) dan \(f = 1\text{,}\) sehingga \(v - e + f = 2\text{.}\) Oleh karena itu, \(G\) harus memuat suatu siklus. Pilih sembarang sisi \(e_0\) yang merupakan bagian dari suatu siklus dalam \(G\text{,}\) lalu tinjau graf \(G' = G-e_0\) yang diperoleh dengan menghapus hanya sisi \(e_0\) dari \(G\text{.}\)
Karena \(G'\) memiliki lebih sedikit sisi daripada \(G\text{,}\) graf tersebut harus memenuhi rumus Euler. Artinya, \(v' - e' + f' = 2\text{,}\) dengan \(v'\text{,}\) \(e'\text{,}\) dan \(f'\) masing-masing menyatakan banyaknya simpul, sisi, dan muka pada \(G'\text{.}\) Karena \(G'\) diperoleh dengan menghapus satu sisi dari suatu siklus dalam \(G\text{,}\) berlaku \(v' = v\text{,}\) \(e'=e-1\text{,}\) dan \(f' = f-1\text{.}\) Oleh karena itu, \(v - (e-1) + (f-1) = 2\text{,}\) sehingga \(v - e + f = 2\) juga berlaku. Ini merupakan kontradiksi, sehingga graf \(G\) semacam itu tidak mungkin ada.

12.

Penyelesaian.
Bukti.
Kita mengetahui bahwa dalam setiap graf planar, banyaknya muka \(f\) memenuhi \(3f \le 2e\) karena setiap muka dibatasi oleh sedikitnya tiga sisi, sedangkan setiap sisi membatasi dua muka. Gabungkan hal ini dengan rumus Euler:
\begin{equation*} v - e + f = 2 \end{equation*}
\begin{equation*} v - e + \frac{2e}{3} \ge 2 \end{equation*}
\begin{equation*} 3v - e \ge 6 \end{equation*}
\begin{equation*} 3v - 6 \ge e\text{.} \end{equation*}

2.4 Jejak dan Sirkuit Euler
Latihan Tambahan

1.

Penyelesaian.
Pertanyaan ini berkaitan dengan pencarian jejak Euler. Gambarlah sebuah graf dengan satu simpul untuk setiap negara bagian, lalu hubungkan dua simpul jika negara bagian yang diwakilinya memiliki perbatasan bersama. Tepat dua simpul akan berderajat ganjil, yaitu simpul untuk Nevada dan Utah. Jadi, perjalanan darat tersebut harus dimulai di salah satu dari kedua negara bagian itu dan berakhir di negara bagian yang lain.

2.

Penyelesaian.
  1. \(K_4\) tidak memiliki jejak maupun sirkuit Euler.
  2. \(K_5\) memiliki sirkuit Euler (dan dengan demikian juga memiliki jejak Euler).
  3. \(K_{5,7}\) tidak memiliki jejak maupun sirkuit Euler.
  4. \(K_{2,7}\) memiliki jejak Euler, tetapi tidak memiliki sirkuit Euler.
  5. \(C_7\) memiliki sirkuit Euler (graf tersebut memang graf sirkuit!).
  6. \(P_7\) memiliki jejak Euler, tetapi tidak memiliki sirkuit Euler.

8.

Penyelesaian.
Jika kita membangun satu jembatan, kita dapat memperoleh jejak Euler. Untuk memperoleh sirkuit Euler, dua jembatan harus dibangun.
Tiga titik tersusun dalam kolom vertikal di sebelah kiri satu titik lain yang berada di kanan. Garis-garis menghubungkan titik kanan dengan setiap titik kiri. Di antara titik-titik kiri, dua garis lengkung menghubungkan titik bawah dengan titik tengah, dan dua garis lengkung lain menghubungkan titik tengah dengan titik atas. Sebuah sisi putus-putus tambahan menghubungkan titik kanan dengan titik atas, dan sisi putus-putus lainnya menghubungkan titik bawah dengan titik tengah pada kolom vertikal.

2.5 Pewarnaan
Latihan Tambahan

1.

Penyelesaian.
2, karena graf tersebut bipartit. Gunakan satu warna untuk himpunan simpul bagian atas dan satu warna lain untuk himpunan simpul bagian bawah.

2.

Penyelesaian.
Sebagai contoh, \(K_6\text{.}\) Jika bilangan kromatiknya 6, graf tersebut tidak planar; teorema empat warna menyatakan bahwa semua graf planar dapat diwarnai dengan 4 warna atau kurang.

3.

Penyelesaian.
Bilangan kromatiknya, berturut-turut dari kiri ke kanan, adalah 2, 3, 4, 5, dan 3.

5.

Penyelesaian.
Kubus dapat direpresentasikan sebagai graf planar dan diwarnai dengan dua warna sebagai berikut:
Delapan simpul membentuk persegi dalam dan persegi luar, dengan sisi-sisi yang membentuk setiap persegi serta sisi yang menghubungkan setiap simpul dalam ke simpul luar terdekat. Dimulai dari kiri atas dan bergerak searah jarum jam, simpul-simpul luar berlabel R, B, R, B. Dengan urutan yang sama, simpul-simpul dalam berlabel B, R, B, R. Label R menyatakan merah dan B menyatakan biru.
Karena simpul-simpulnya tidak mungkin diwarnai hanya dengan satu warna, kita menyimpulkan bahwa kubus memiliki bilangan kromatik 2 (grafnya bipartit).

9.

Penyelesaian.
Graf roda berikut memiliki sifat tersebut. Bagian luar roda membentuk siklus ganjil sehingga memerlukan 3 warna; pusat roda harus memiliki warna yang berbeda dari semua simpul luar.
Lima simpul membentuk segilima dengan simpul keenam di tengah. Sisi-sisi membentuk keliling segilima, dan simpul tengah bertetangga dengan setiap simpul luar.

12.

Penyelesaian.
Jika kita menggambar graf dengan setiap huruf merepresentasikan sebuah simpul dan setiap sisi menghubungkan dua huruf yang berurutan dalam alfabet, kita memperoleh graf yang memiliki dua simpul berderajat 1 (A dan Z), sedangkan 24 simpul lainnya semuanya berderajat 2 (sebagai contoh, \(D\) bertetangga dengan \(C\) dan \(E\)). Menurut teorema Brooks, graf ini memiliki bilangan kromatik paling banyak 2 karena itulah derajat maksimum graf tersebut, dan graf itu bukan graf lengkap maupun siklus ganjil. Jadi, hanya diperlukan dua kotak.

13.

Penyelesaian.

2.7 Pencocokan pada Graf Bipartit

Latihan

2.7.1.
Penyelesaian.
Graf pertama dan ketiga memiliki pencocokan yang ditunjukkan dengan garis tebal (terdapat pula pencocokan lainnya). Graf tengah tidak memiliki pencocokan. Jika Anda memperhatikan ketiga simpul yang dilingkari, ketiganya hanya memiliki dua tetangga, sehingga melanggar kondisi pencocokan \(\card{N(S)} \ge \card{S}\) (ketiga simpul yang dilingkari tersebut membentuk himpunan \(S\)).
Sebuah graf bipartit dengan enam simpul yang terbagi ke dalam dua himpunan beranggotakan tiga simpul. Jika simpul-simpul atas dinamai a, b, c dan simpul-simpul bawah dinamai 1, 2, 3 (dari kiri ke kanan), graf tersebut memiliki sisi-sisi berikut: (a,1), (a,2), (b,1), (b,3), (c,1), (c,3). Sisi (a,2), (b,3), dan (c,1) ditampilkan dengan garis tebal.
Sebuah graf bipartit dengan delapan simpul yang terbagi ke dalam dua himpunan beranggotakan empat simpul. Jika simpul-simpul atas dinamai a, b, c, d dan simpul-simpul bawah dinamai 1, 2, 3, 4 (dari kiri ke kanan), graf tersebut memiliki sisi-sisi berikut: (a,1), (a,3), (a,4), (b,2), (c,1), (c,2), (c,3), (c,4), (d,2). Simpul 1, 3, dan 4 dilingkari.
Sebuah graf bipartit dengan sepuluh simpul yang terbagi ke dalam dua himpunan beranggotakan lima simpul. Jika simpul-simpul atas dinamai a, b, c, d, e dan simpul-simpul bawah dinamai 1, 2, 3, 4, 5 (dari kiri ke kanan), graf tersebut memiliki sisi-sisi berikut: (a,1), (a,2), (a,3), (b,1), (b,3), (c,2), (c,4), (d,3), (d,5), (e,3), (e,4), (e,5). Di antaranya, sisi-sisi berikut ditampilkan dengan garis tebal: (a,1), (b,3), (c,2), (d,5), (e,4).

2.8 Ringkasan Bab

Tinjauan Bab

2.8.1.
Penyelesaian.
Graf pertama dan ketiga sama (cobalah menggeser simpul-simpulnya agar kedua gambar berimpit), tetapi graf di tengah berbeda (hal ini dapat Anda lihat, misalnya, dengan memperhatikan bahwa graf di tengah hanya memiliki satu simpul berderajat 2, sedangkan dua graf lainnya memiliki dua simpul semacam itu).
2.8.2.
Penyelesaian.
Graf pertama (dan ketiga) memiliki jejak Euler. Semua graf tersebut planar.
2.8.3.
Penyelesaian.
Sebagai contoh, \(K_5\text{.}\)
2.8.4.
Penyelesaian.
Sebagai contoh, \(K_{3,3}\text{.}\)
2.8.5.
Penyelesaian.
  1. Ya, kedua graf tersebut isomorfik, sebagaimana dapat dilihat dengan menggambarnya. Salah satu isomorfismenya adalah:
    \begin{equation*} f = \begin{pmatrix} a \amp b \amp c \amp d \amp e \amp f \amp g \\ u \amp z \amp v \amp x \amp w \amp y \amp t \end{pmatrix}\text{.} \end{equation*}
  2. Hal ini mudah dilakukan jika Anda menggambar grafnya. Berikut adalah salah satu graf semacam itu:
    Pohon dengan satu simpul bawah yang bertetangga dengan masing-masing dari tiga simpul pada baris di atasnya. Setiap simpul pada baris tersebut bertetangga dengan satu simpul lain yang berada tepat di atasnya.
    Pelabelan apa pun pada graf ini akan menghasilkan graf yang tidak isomorfik dengan \(G\text{.}\) Sebagai contoh, kita dapat mengambil \(V'' = \{a,b,c,d,e,f,g\}\) dan \(E'' = \{ab, ac, ad, be, cf, dg\} \text{.}\)
  3. Barisan derajat \(G\) adalah \((3, 3, 2, 1, 1, 1, 1)\text{.}\)
  4. Secara umum, hal ini seharusnya mungkin: barisan derajat tidak menentukan kelas isomorfisme graf. Namun, dalam kasus ini, semula saya hampir yakin bahwa hal tersebut tidak mungkin. Keyakinan itu berubah ketika saya menemukan graf berikut:
    Pohon dengan satu simpul tengah bawah yang bertetangga dengan dua simpul di atasnya. Masing-masing dari kedua simpul tersebut bertetangga dengan dua simpul di atasnya.
  5. \(G\) adalah pohon (tidak terdapat siklus) sehingga juga merupakan graf bipartit.
  6. Ya, semua pohon bersifat planar. Anda dapat menggambarnya pada bidang tanpa sisi yang berpotongan.
  7. Bilangan kromatik \(G\) adalah 2. Tidak sulit untuk memberikan pewarnaan dengan 2 warna (sebagai contoh, warnai \(a, d, e, g\) dengan merah dan \(b, c, f\) dengan biru), tetapi kita juga mengetahui bahwa semua graf bipartit yang memiliki sisi mempunyai bilangan kromatik 2.
  8. Dari gambar terlihat jelas bahwa tidak terdapat jejak Euler, apalagi sirkuit Euler. Selain itu, karena terdapat lebih dari 2 simpul berderajat ganjil, kita mengetahui dengan pasti bahwa tidak ada jejak Euler.
2.8.6.
Penyelesaian.
Ya. Menurut rumus Euler, graf tersebut akan memiliki 2 muka. Graf itu memang memiliki 2 muka. Satu-satunya graf semacam itu adalah \(C_{10}\text{.}\)
2.8.7.
Penyelesaian.
  1. Hanya jika \(n \ge 6\) dan nilainya genap.
  2. Tidak ada.
  3. 12. Graf semacam itu akan memiliki \(\frac{5n}{2}\) sisi. Jika graf tersebut planar, maka \(n - \frac{5n}{2} + f = 2\text{,}\) sehingga terdapat \(\frac{4+3n}{2}\) muka. Selain itu, harus berlaku \(3f \le 2e\) karena graf tersebut sederhana. Jadi, harus berlaku \(3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}\) Penyelesaian terhadap \(n\) menghasilkan \(n \ge 12\text{.}\)
2.8.8.
Penyelesaian.
  1. Terdapat 24 pasangan: 6 pilihan siswi dan 4 pilihan siswa.
  2. Terdapat 45 pasangan: \({10 \choose 2}\) karena kita harus memilih dua dari 10 orang untuk berdansa bersama.
  3. Untuk bagian (a), kita menghitung banyaknya sisi dalam \(K_{4,6}\text{.}\) Pada bagian (b), kita menghitung sisi-sisi \(K_{10}\text{.}\)
2.8.9.
Penyelesaian.
Ya, selama \(n\) genap. Jika \(n\) ganjil, graf yang bersesuaian akan memiliki jumlah simpul berderajat ganjil yang ganjil, dan hal ini tidak mungkin.
2.8.10.
Penyelesaian.
  1. Tidak. Kesembilan segitiga masing-masing menyumbangkan 3 sisi, dan keenam segilima masing-masing menyumbangkan 5 sisi. Jumlahnya adalah 57, yang harus sama dengan dua kali jumlah sisi karena setiap sisi membatasi tepat 2 muka. Namun, 57 ganjil, sehingga hal ini tidak mungkin.
  2. Sekarang, penjumlahan seluruh sisi dari keenam belas poligon menghasilkan 64, yang berarti polihedron tersebut memiliki 32 sisi. Selanjutnya, kita dapat menggunakan rumus Euler \(v - e + f = 2\) untuk menyimpulkan bahwa harus terdapat 18 simpul.
  3. Jika kita menjumlahkan semua simpul dari setiap poligon secara terpisah, jumlahnya adalah 64. Bilangan ini tidak habis dibagi 3, sehingga tidak mungkin setiap simpul menjadi bagian dari tepat 3 muka. Mungkinkah semuanya menjadi bagian dari 4 muka? Hal itu berarti terdapat \(64/4 = 16\) simpul, tetapi berdasarkan rumus Euler kita mengetahui bahwa harus terdapat 18 simpul. Kita dapat menuliskan \(64 = 3x + 4y\) dan menyelesaikannya untuk \(x\) dan \(y\) (sebagai bilangan bulat). Kita memperoleh bahwa harus terdapat 10 simpul berderajat 4 dan 8 simpul berderajat 3. (Perhatikan bahwa jumlah muka yang bertemu pada suatu simpul sama dengan derajatnya dalam istilah teori graf.)
2.8.11.
Penyelesaian.
Tidak. Setiap polihedron dapat direpresentasikan sebagai graf planar, dan Teorema Empat Warna menyatakan bahwa setiap graf planar memiliki bilangan kromatik paling besar 4.
2.8.12.
Penyelesaian.
\(K_{n,n}\) memiliki \(n^2\) sisi. Graf tersebut memiliki sirkuit Euler ketika \(n\) genap. Graf tersebut planar hanya ketika \(n \lt 3\text{.}\)
2.8.13.
Penyelesaian.
\(G\) memiliki 8 sisi (karena jumlah derajatnya adalah 16). Jika \(G\) planar, graf tersebut akan memiliki 4 muka (karena \(6 - 8 + 4 = 2\)). \(G\) tidak memiliki jejak Euler karena terdapat lebih dari 2 simpul berderajat ganjil.
2.8.14.
Penyelesaian.
\(7\) warna. Jadi, \(K_7\) tidak planar (berdasarkan kontraposisi Teorema Empat Warna).
2.8.15.
Penyelesaian.
Bilangan kromatik \(K_{3,4}\) adalah 2 karena graf tersebut bipartit. Anda tidak dapat menentukan apakah graf tersebut planar berdasarkan pewarnaan ini (konvers Teorema Empat Warna tidak benar). Sebenarnya, graf tersebut tidak planar karena memuat \(K_{3,3}\) sebagai subgraf.
2.8.16.
Penyelesaian.
Kita mengetahui bahwa \(K_{3,4}\) memiliki 7 simpul dan 12 sisi (setiap simpul dalam kelompok beranggota 3 memiliki derajat 4). Berdasarkan rumus Euler, berlaku \(7 - 12 + f = 2\text{,}\) sehingga jika graf tersebut planar, graf itu akan memiliki \(f = 7\) muka. Namun, karena panjang siklus terpendek (girth) graf tersebut adalah 4 (tidak terdapat siklus dengan panjang 3), kita memperoleh \(4f \le 2e\text{.}\) Akan tetapi, hal ini berarti \(28 \le 24\text{,}\) suatu kontradiksi.
2.8.17.
Penyelesaian.
Dalam semua pertanyaan ini, sebenarnya kita mewarnai simpul-simpul suatu graf. Graf tersebut diperoleh dengan terlebih dahulu menggambar representasi planar polihedron, lalu mengambil dual planarnya: tempatkan sebuah simpul di tengah setiap muka (termasuk muka luar), dan hubungkan dua simpul apabila muka yang bersesuaian berbagi sisi.
  1. Karena dual planar dodekahedron memuat roda-5, bilangan kromatiknya sedikitnya 4. Sebagai alternatif, andaikan Anda dapat mewarnai muka-mukanya dengan 3 warna tanpa ada dua muka bertetangga yang diberi warna sama. Ambil sembarang muka dan warnai biru. Kelima segilima yang berbatasan dengan segilima biru tersebut tidak dapat diwarnai biru. Warnai segilima pertama dengan merah. Kedua tetangganya (yang bertetangga dengan segilima biru) harus diwarnai hijau. Dua segilima yang tersisa tidak dapat diwarnai biru atau hijau, tetapi juga tidak dapat keduanya diwarnai merah karena keduanya saling bertetangga. Jadi, diperlukan warna keempat.
  2. Dual planar dodekahedron itu sendiri merupakan graf planar. Jadi, berdasarkan Teorema Empat Warna, graf tersebut dapat diwarnai hanya dengan 4 warna tanpa ada dua simpul bertetangga (yang bersesuaian dengan muka polihedron) diberi warna sama.
  3. Muka-muka kubus dapat diwarnai secara tepat dengan 3 warna. Warnai muka “atas” dan “bawah” dengan merah, muka “depan” dan “belakang” dengan biru, serta muka “kiri” dan “kanan” dengan hijau.
2.8.18.
Penyelesaian.
  1. Salah. Untuk membuktikannya, kita dapat memberikan contoh sepasang graf yang memiliki bilangan kromatik sama tetapi tidak isomorfik. Sebagai contoh, \(K_{3,3}\) dan \(K_{3,4}\) sama-sama memiliki bilangan kromatik 2 tetapi tidak isomorfik.
  2. Salah. Contoh sebelumnya tidak dapat digunakan, tetapi Anda dapat dengan mudah menggambar dua pohon yang memiliki jumlah simpul dan sisi sama tetapi tidak isomorfik. Karena semua pohon yang memiliki sisi mempunyai bilangan kromatik 2, pasangan ini merupakan contoh penyangkal.
  3. Benar. Jika terdapat isomorfisme dari \(G_1\) ke \(G_2\text{,}\) kita memiliki bijeksi yang menunjukkan pasangan simpul di antara kedua graf. Setiap pewarnaan simpul yang tepat pada \(G_1\) menunjukkan cara mewarnai \(G_2\) secara tepat, cukup dengan memberi \(f(v_i)\) warna yang sama dengan \(v_i\) untuk setiap simpul \(v_i \in V\text{.}\) Artinya, warnai simpul-simpul dalam \(G_2\) persis seperti simpul-simpul yang bersesuaian dalam \(G_1\text{.}\) Demikian pula, setiap pewarnaan simpul yang tepat pada \(G_2\) bersesuaian dengan pewarnaan simpul yang tepat pada \(G_1\text{.}\) Jadi, jumlah warna minimum yang diperlukan untuk mewarnai \(G_1\) secara tepat tidak mungkin lebih kecil daripada jumlah warna minimum yang diperlukan untuk mewarnai \(G_2\) secara tepat, dan sebaliknya, sehingga bilangan kromatik keduanya harus sama.
2.8.19.
Penyelesaian.
\(G\) memiliki \(13\) sisi karena harus berlaku \(7 - e + 8 = 2\text{.}\)
2.8.20.
Penyelesaian.
  1. Graf tersebut memiliki jejak Euler, tetapi tidak memiliki sirkuit Euler. Terdapat tepat dua simpul berderajat ganjil. Jejak itu bermula pada salah satunya dan berakhir pada simpul lainnya.
  2. Graf tersebut planar. Meskipun gambar yang diberikan memiliki sisi-sisi yang berpotongan, graf tersebut mudah digambar ulang tanpa sisi yang berpotongan.
  3. Graf tersebut tidak bipartit (terdapat siklus ganjil) dan juga tidak lengkap.
  4. Bilangan kromatik graf tersebut adalah 3.
2.8.21.
Penyelesaian.
  1. Salah. Sebagai contoh, \(K_{3,3}\) tidak planar.
  2. Benar. Graf tersebut bipartit, sehingga simpul-simpulnya dapat dibagi menjadi dua kelompok tanpa sisi di antara simpul-simpul dalam kelompok yang sama. Jadi, kita dapat mewarnai semua simpul dalam satu kelompok dengan merah dan kelompok lainnya dengan biru.
  3. Salah. \(K_{3,3}\) memiliki 6 simpul berderajat 3 sehingga tidak memiliki jejak Euler.
  4. Salah. Sekali lagi, \(K_{3,3}\) merupakan contoh penyangkal.
  5. Salah. Jumlah derajat semua simpul bernilai genap untuk setiap graf, sehingga sifat ini tidak mengakibatkan graf tersebut bipartit.
2.8.22.
Penyelesaian.
  1. Jika suatu graf memiliki jejak Euler, graf tersebut planar.
  2. Jika suatu graf tidak memiliki jejak Euler, graf tersebut tidak planar.
  3. Terdapat graf planar yang tidak memiliki jejak Euler.
  4. Ya. Dalam kasus ini, hal tersebut terjadi karena pernyataan semula salah.
  5. Salah. \(K_4\) planar tetapi tidak memiliki jejak Euler.
  6. Salah. \(K_5\) memiliki jejak Euler tetapi tidak planar.

3 Pencacahan
3.1 Segitiga Aritmetika Pascal
Soal Latihan

7.

Penyelesaian.
  1. \({12 \choose 5} = {792}\) pilihan, karena Anda harus memilih himpunan bagian 5-elemen dari himpunan 12 isian.
  2. \({11 \choose 5} = {462}\) pilihan, karena Anda harus memilih 5 dari 11 isian selain paprika hijau.
  3. \({11 \choose 4} = {330}\) pilihan, karena Anda harus memilih 4 dari 11 isian selain paprika hijau yang tersisa untuk digunakan bersama paprika hijau.
Perhatikan bahwa \({792} = {462} + {330}\) pilihan. Hal ini masuk akal karena setiap calzone dengan 5 isian memuat paprika hijau atau tidak memuat paprika hijau.

9.

Penyelesaian.
Untuk memperoleh \(x^{9}\text{,}\) kita harus memilih 9 dari 17 faktor agar masing-masing menyumbangkan \(x\text{,}\) sehingga 8 faktor lainnya menyumbangkan 3. Terdapat \({17 \choose 9}\) cara untuk memilih 9 faktor tersebut. Jadi, suku yang memuat \(x^{9}\) adalah \({17 \choose 9}x^{9}3^{8}\text{.}\) Dengan kata lain, koefisien \(x^{9}\) adalah \({17\choose 9}3^8 = {1.59498\times 10^{8}}\text{.}\)

10.

Penyelesaian.
Untuk memperoleh \(x^{8}\) dari suku pertama, kita harus memilih 8 dari 17 faktor agar masing-masing menyumbangkan \(x\text{,}\) sehingga 9 faktor lainnya menyumbangkan 2. Terdapat \({17 \choose 8}\) cara untuk memilih 8 faktor tersebut, sehingga koefisiennya adalah \({17 \choose 8} *2^{9}\text{.}\) Selanjutnya, kita harus memilih 4 faktor pada suku kedua agar masing-masing menyumbangkan \(x\text{,}\) sehingga 14 faktor lainnya menyumbangkan 3. Hal ini menghasilkan koefisien \({18 \choose 4}*3^{14}\) dari suku tersebut. Secara keseluruhan, koefisien \(x^{8}\) adalah \({17 \choose 8} *2^{9} + {18 \choose 4}*3^{14}= {1.46483\times 10^{10}}\text{.}\)

3.2 Menggabungkan Hasil
Soal Latihan

1.

Penyelesaian.
Terdapat \(2 \cdot 4 \cdot 18 = {144}\) setelan pakaian. Gunakan prinsip perkalian.

2.

Penyelesaian.
  1. \(2 + 6 = {8}\) pilihan dasi. Gunakan prinsip penjumlahan.
  2. \(2 \cdot 6 = {12}\) pasangan dasi. Gunakan prinsip perkalian.
  3. \(6 \cdot (5+7) + 8 = {80}\) pilihan pakaian.

3.

Penyelesaian.
  1. Terdapat 4096 bilangan heksadesimal 4 digit yang digit pertamanya E, satu untuk setiap pilihan digit sisanya. Demikian pula, terdapat 4096 bilangan heksadesimal yang digit pertamanya F. Kita mencari gabungan dua himpunan yang saling lepas ini, sehingga terdapat \(4096 + 4096 = 2\cdot4096=8192\) bilangan heksadesimal 4 digit yang digit pertamanya E atau F.
  2. Digit pertama dapat dipilih dengan 6 cara, masing-masing digit ke-2 sampai ke-5 dengan 16 cara, dan digit terakhir dengan 10 cara. Jadi, terdapat \(6\cdot 16^{4} \cdot 10 = 3932160\) bilangan heksadesimal yang memenuhi syarat tersebut.
  3. Banyaknya bilangan heksadesimal 5 digit yang diawali huruf adalah \(6 \cdot 16^4 = 393216\text{.}\) Banyaknya bilangan heksadesimal 5 digit yang diakhiri angka adalah \(16^{4} \cdot 10 = 655360\text{.}\) Kita menginginkan semua anggota dari kedua himpunan ini. Akan tetapi, keduanya sama-sama memuat bilangan heksadesimal 5 digit yang sekaligus diawali huruf dan diakhiri angka, sebanyak \(6\cdot16^{3}\cdot 10=245760\text{,}\) sehingga banyaknya harus dikurangi satu kali. Jadi, banyaknya bilangan heksadesimal 5 digit yang diawali huruf atau diakhiri angka adalah:
    \(\displaystyle{ 393216 + 655360 - 245760 = 802816 }\)

4.

Penyelesaian.
  1. \(2^{11} = 2048\) himpunan bagian. Untuk masing-masing dari 11 anggota, kita memilih apakah anggota tersebut disertakan atau tidak.
  2. \(2^{8} = 256\) himpunan bagian. Untuk masing-masing dari 8 anggota yang tersisa, kita memilih apakah anggota tersebut disertakan atau tidak.
  3. \(2^{11} - 2^{5} = 2016\) himpunan bagian. Dari banyaknya semua himpunan bagian, kurangi banyaknya himpunan bagian yang tidak memuat bilangan ganjil. Banyaknya himpunan semacam itu adalah \(2^{5}\text{,}\) karena untuk setiap anggota genap kita memilih apakah anggota tersebut disertakan atau tidak.
  4. \({5 \choose 1}\cdot 2^{6} ={320}\) himpunan bagian. Pertama pilih satu bilangan genap. Kemudian, untuk setiap bilangan ganjil, pilih apakah bilangan tersebut disertakan atau tidak.

5.

Penyelesaian.
  1. \(\binom{8}{5} = 56\) subhimpunan
  2. \(\binom{5}{2} = 10\) subhimpunan. Kita perlu memilih 2 dari 5 elemen \(S\) yang tersisa untuk dimasukkan ke dalam subhimpunan.
  3. \(\binom{8}{5} = 56\) subhimpunan. Setiap subhimpunan dengan kardinalitas \(5\) harus memuat setidaknya satu bilangan ganjil.
  4. \(\binom{4}{1} = 4\) subhimpunan. Pilih 1 dari 4 bilangan genap. Semua 4 bilangan ganjil dalam \(S\) yang tersisa harus berada dalam subhimpunan.

7.

Penyelesaian.
  1. Setiap barisan dapat dipandang sebagai string 12 bit berbobot 6, karena 6 dari 12 koin harus berupa koin satu sen. Jadi, terdapat \({12 \choose 6} = {924}\) barisan yang mungkin. Setiap barisan memerlukan 12 koin, sehingga untuk menyusun semua barisan sekaligus diperlukan 11088 koin, separuh koin lima sen dan separuh koin satu sen.
  2. Sekarang terdapat \(2^{12} = 4096\) barisan yang mungkin. Jika barisan dikelompokkan menurut banyaknya koin satu sen—0, 1, 2, dan seterusnya—jumlah ini juga sama dengan \({12 \choose 0} + {12\choose 1} + {12 \choose 2} +\dots + {12 \choose 12}\text{.}\) Karena setiap barisan memuat 12 koin, seluruhnya diperlukan \(12 \cdot 4096 = {49152}\) koin.

8.

Penyelesaian.
Hitung secara terpisah banyaknya string untuk setiap jumlah angka 1 yang diperbolehkan, lalu jumlahkan semuanya. Dengan demikian, terdapat \({13 \choose 4} + {13 \choose 5} + \cdots {13 \choose 13} = {7814}\) string.

9.

Penyelesaian.
Pertanyaan ini setara dengan pertanyaan tentang string 10 bit, karena setiap himpunan bagian dapat direpresentasikan oleh string 10 bit dengan angka 1 yang menandakan bahwa anggota terkait disertakan. Jadi, terdapat \({10 \choose 8} + {10\choose 9} + \cdots + {10\choose 10} = {56}\) himpunan bagian.

10.

Penyelesaian.
  1. \({ 22\choose 11} = {705432}\) lintasan. Semua lintasan memiliki panjang 22, yaitu 11 langkah ke atas dan 11 langkah ke kanan. Kita cukup memilih 11 dari 22 langkah tersebut yang akan diarahkan ke kanan.
  2. \({11 \choose 5}{11\choose 6} = {213444}\) lintasan. Pertama bergeraklah menuju \((6,7)\text{,}\) lalu lanjutkan ke \((12,12)\text{.}\)
  3. \({ 22\choose 11} - {11 \choose 5}{11\choose 6} = {491988}\) lintasan. Kurangi semua lintasan yang dihitung pada bagian (b).

Latihan Tambahan

1.

Penyelesaian.
  1. Sebagai contoh, 16 adalah banyaknya pilihan jika Anda ingin menonton satu film, berupa film komedi atau film horor.
  2. Sebagai contoh, 63 adalah banyaknya pilihan jika Anda akan menonton dua film, pertama film komedi lalu film horor.

3.3 Hasil yang Tidak Saling Lepas
Soal Latihan

3.

Penyelesaian.
48 mahasiswa. Gunakan diagram Venn atau prinsip inklusi–eksklusi (PIE): \(29 + 24 + 27 - (10 + 13+17) + 8= {48}\text{.}\)

4.

Penyelesaian.
Dengan menggunakan prinsip inklusi–eksklusi, banyak mahasiswa yang menyukai sedikitnya satu olahan kentang yang disebutkan adalah
\(\displaystyle{ 53 + 51 + 70 -(22 + 33 + 36) +16 = {99}. }\)
Jadi, ada \(115 - {99} = {16}\) mahasiswa yang tidak menyukai kentang. Soal ini juga dapat diselesaikan dengan diagram Venn.

5.

Penyelesaian.
  1. \(2^{11} = {2048}\text{.}\) Terdapat 2 pilihan untuk setiap bit pada 11 posisi yang tersisa.
  2. \({11 \choose 6} = 462\text{.}\) Kita perlu memilih 6 dari 11 bit yang tersisa untuk bernilai 1.
  3. 5632. Ada \(2^{11}\) string yang diawali 011 dan \(2^{12}\) string yang diakhiri 01 (untuk 12 bit, kita memilih 1 atau 0). Namun, string yang diawali 011 sekaligus diakhiri 01 terhitung dua kali; ada \(2^{9}\) string semacam itu. Dengan prinsip inklusi–eksklusi (PIE), diperoleh \(2^{11} + 2^{12} - 2^{9} = {5632}\text{.}\)
  4. 1128. Ada \({11 \choose 6} = 462\) string berbobot 8 yang diawali 011 dan \({12 \choose 7} ={792}\) string yang diakhiri 01. Sekali lagi terjadi penghitungan ganda: ada string berbobot 8 yang diawali 011 sekaligus diakhiri 01, tepatnya sebanyak \({9 \choose 5} ={126}\text{.}\) Jadi, seluruhnya ada \(462+{792}-{126} = {1128}\) string.

6.

Penyelesaian.
Ada 299 nilai \(n\text{.}\) Gunakan prinsip inklusi–eksklusi (PIE), yaitu \(98 + 158+ 87 - (19 + 10 + 17) + 2\text{,}\) atau gunakan diagram Venn. Untuk menentukan banyak bilangan yang habis dibagi 5 dan 9, misalnya, hitung \(790/(5\cdot9)\) lalu bulatkan ke bawah.

7.

Penyelesaian.
Untuk menentukan banyak bilangan yang benar-benar kurang dari 850 dan merupakan kelipatan 9, kita dapat membagi \(850-1\) dengan 9 lalu membulatkan hasilnya ke bawah. Ada 94 bilangan semacam itu. Demikian pula, terdapat 169 kelipatan 5 dan 424 kelipatan 2 yang kurang dari 850.
Kita juga perlu memperhitungkan irisannya. Bilangan yang merupakan kelipatan 9 dan 5 harus merupakan kelipatan 45; terdapat 18 bilangan semacam itu. Terdapat 47 bilangan yang merupakan kelipatan 9 dan 2, serta 84 bilangan yang merupakan kelipatan 5 dan 2. Terakhir, terdapat 9 bilangan yang merupakan kelipatan ketiganya.
Dengan menggunakan prinsip inklusi–eksklusi (PIE), diperoleh
\(\displaystyle{ 94 +169+ 424 - (18 + 47 + 84) + 9 = {547} }\)
bilangan yang kurang dari 850 dan merupakan kelipatan 9, 5, atau 2.

8.

Penyelesaian.
  1. Ada \(7^{12} = {1.38413\times 10^{10}}\) kata, karena untuk masing-masing dari 12 posisi kita memilih satu dari 7 huruf.
  2. Ada \((7)\cdot (6)\cdot (5) \dots (7-12+1) = {0}\) kata. Setelah satu huruf dipilih, jumlah huruf yang tersedia untuk posisi berikutnya berkurang.
  3. Ada \(7 ^ {9} ={4.03536\times 10^{7}}\) kata: kita hanya perlu memilih huruf-huruf yang mengikuti “ade”.
  4. Ada \(7^{9} + 7^{10} - 7^{7}={3.22005\times 10^{8}}\) kata. Terdapat \(7^{9}\) kata yang diawali “ade” dan \(7^{10}\) kata lain yang diakhiri “be”. Selanjutnya, kita kurangi kata-kata yang memenuhi keduanya karena sebelumnya terhitung dua kali.
  5. Ada \((7 \cdot (7-1) \cdot (7-2) \dots (7-12+1)) - (10\cdot (4)\cdot (4-1) \cdot (4-2) \dots 4-9+1) = {0}\) kata. Kita mengambil semua kata tanpa pengulangan, lalu mengurangi kata-kata yang memuat subkata terlarang “bed”. Subkata “bed” dapat dimulai pada salah satu dari 10 posisi; untuk setiap posisi tersebut, kita harus memilih 9 huruf sisanya dari 4 huruf yang tersisa dalam alfabet.

3.4 Kombinasi dan Permutasi
Soal Latihan

1.

Penyelesaian.
  1. Ada \({8 \choose 4} = {70}\) piza. Kita harus memilih 4 dari 8 jenis topping tanpa memperhatikan urutan.
  2. Ada \(2^{8} = {256}\) piza. Untuk setiap jenis topping, pilih ya atau tidak.
  3. Ada \(P(8,4) = {1680}\) cara. Isilah masing-masing dari 4 posisi pada kolom kiri dengan satu jenis topping piza yang berbeda.

2.

Penyelesaian.
Meskipun namanya kunci kombinasi, yang kita hitung di sini bukanlah kombinasi dalam arti matematis. Urutan kemunculan ketiga angka penting. Ada \(P(45,3) = 45\cdot 44 \cdot 43\) kemungkinan berbeda untuk “kombinasi” kunci tersebut. Perhitungan ini menganggap tidak ada angka yang boleh diulang (jika pengulangan diperbolehkan, jawabannya adalah \(45^3\)).

3.

Penyelesaian.
  1. Ini merupakan penerapan langsung prinsip perkalian. Untuk setiap satu dari 3 posisi, tersedia 8 digit yang dapat dipilih, sehingga terdapat \(8^3 = {512}\) bilangan.
  2. Sekarang tersedia 8 pilihan untuk digit pertama, 7 untuk digit kedua, dan seterusnya. Jadi, terdapat \(8 \cdot 7 \cdot \dots \cdot (9-3) = P(8,3) = {336}\) bilangan.
  3. Untuk membentuk bilangan semacam itu, kita cukup memilih 3 digit berbeda. Setelah dipilih, hanya ada satu cara untuk menyusunnya dalam urutan menaik. Jadi, terdapat \({8 \choose 3} = {56}\) bilangan.

4.

Penyelesaian.
  1. Jawabannya dapat ditulis sebagai \(P(18,14) = 18 \cdot 17 \cdot 16 \cdot \dots \cdot 5\text{,}\) yang sama dengan \(\frac{18!}{4!}\text{.}\) Jika kita memandang prosesnya sebagai memilih 14 buku lalu menyusun 14 buku tersebut, jawabannya juga dapat ditulis sebagai \(\binom{18}{14}\cdot 14!\text{.}\) Karena urutan apa pun diperbolehkan dan susunan yang berbeda dihitung sebagai hasil yang berbeda, permutasi tepat digunakan di sini.
  2. Di sini kita hanya perlu memilih buku; setelah itu tidak ada pilihan dalam penyusunannya. Jadi, jawabannya adalah \(\binom{18}{14}\text{.}\)

5.

Penyelesaian.
Karena terdapat 14 huruf berbeda dalam “troublemakings”, tersedia 14 pilihan untuk huruf pertama, 13 untuk huruf berikutnya, 12 untuk huruf setelahnya, dan seterusnya. Jadi, terdapat \(14!\) anagram.

6.

Penyelesaian.
Setelah huruf pertama (yaitu v), kita harus menyusun ulang 5 huruf yang tersisa. Kini hanya ada dua jenis huruf, sehingga persoalan ini sebenarnya setara dengan persoalan untaian bit: satu jenis huruf berperan sebagai 0 dan jenis lainnya sebagai 1. Jadi, terdapat \({5 \choose 1} = {5}\) anagram yang diawali “v”.

7.

Penyelesaian.
Pertama, tentukan posisi untuk menempatkan ketiga huruf “a”. Terdapat 8 posisi dan kita harus memilih 3 di antaranya untuk diisi dengan “a”. Hal ini dapat dilakukan dengan \(\binom{8}{3}\) cara. Masing-masing dari 5 posisi yang tersisa diisi dengan huruf yang berbeda, sehingga ada \(5!\) cara untuk menyelesaikan anagram. Jadi, seluruhnya terdapat \(\binom{8}{3}\cdot 5!\) anagram. Menariknya, hasilnya adalah 6720, yang juga sama dengan \(P(8,5)\text{.}\) Untuk memperoleh jawaban dengan cara ini, mulailah dengan memilih satu dari 8 posisi untuk diisi huruf pertama yang bukan “a”, lalu pilih salah satu posisi yang masih tersisa untuk huruf berikutnya, dan seterusnya. Setelah itu, tempatkan “a” pada 3 posisi yang tersisa.

8.

Penyelesaian.
  1. \({24 \choose 4}\cdot {20 \choose 4} \cdot {16 \choose 4} \cdot \dots \cdot{4 \choose 4}\) cara. Pilih 4 dari 24 orang untuk kelompok berempat pertama, lalu 4 dari 20 orang yang tersisa untuk kelompok kedua, dan seterusnya (gunakan prinsip perkalian untuk menggabungkannya).
  2. \(6!{18 \choose 3}\cdot {15 \choose 3}\cdot {12 \choose 3} \cdot \dots \cdot {3 \choose 3}\) cara. Pertama tentukan jadwal tee bagi 6 anggota dewan, lalu pilih 3 dari 18 orang yang bukan anggota dewan untuk bermain dengan anggota dewan pertama, kemudian 3 dari 15 orang yang tersisa untuk bermain dengan anggota dewan kedua, dan seterusnya.

9.

Penyelesaian.
\(16!\text{.}\) Ada 17 orang yang duduk mengelilingi meja, tetapi posisi Raja Arthur tidak penting. Yang penting hanyalah siapa yang duduk di sebelah kirinya, dua kursi di sebelah kirinya, dan seterusnya.

10.

Penyelesaian.
  1. Ada \(21^{14}\) fungsi. Untuk bayangan setiap elemen domain, tersedia 21 pilihan.
  2. Ada \(P(21, 14)=21\cdot20\cdot19\cdot \dots \cdot 7\) fungsi injektif. Tersedia 21 pilihan untuk bayangan elemen pertama domain, lalu hanya 20 pilihan untuk elemen kedua, 19 untuk elemen ketiga, dan seterusnya.

11.

Penyelesaian.
  1. Ada \(7^{6} = {117649}\) fungsi, karena tersedia 7 pilihan bayangan untuk masing-masing dari 6 elemen domain.
  2. Ada \(P(7, 6) = 7\cdot 6 \cdot \cdots \cdot 2 = {5040}\) fungsi, karena nilai keluaran tidak boleh berulang.
  3. Ada \({7 \choose 6} = {7}\) fungsi. Karena fungsi harus injektif dan naik, kita cukup memilih 6 elemen berbeda yang akan menjadi nilai fungsi dari 7 elemen kodomain. Setelah elemen-elemen itu dipilih, elemen terkecil harus menjadi bayangan 1, elemen terkecil berikutnya menjadi bayangan 2, dan seterusnya. Langkah ini tidak menambah banyak fungsi karena hanya ada satu cara untuk memasangkan elemen-elemen terpilih tersebut agar fungsi naik.

Latihan Tambahan

1.

Penyelesaian.
120.

3.5 Menghitung Multihimpunan
Soal Latihan

1.

Penyelesaian.
  1. \({10\choose 5}\) himpunan. Kita harus memilih 5 dari 10 digit untuk dimasukkan ke dalam himpunan.
  2. Gunakan batang dan batu: Setiap batu merepresentasikan salah satu dari 5 elemen multihimpunan; setiap batang merepresentasikan perpindahan antar-digit. Jadi terdapat 5 batu dan 9 batang, yang menghasilkan \({14 \choose 5}\) multihimpunan.

2.

Penyelesaian.
  1. Terdapat \({6 \choose 5}\) bilangan. Kita cukup memilih 5 dari 6 digit dan, setelah pilihan dibuat, menempatkannya dalam urutan menaik.
  2. Gunakan batang dan batu. Gunakan satu batu untuk merepresentasikan masing-masing dari 5 digit dalam bilangan tersebut, dan gunakan posisinya relatif terhadap batang untuk menunjukkan angka mana yang mengisi posisi itu. Jadi kita memiliki 5 batu dan 5 batang, yang menghasilkan \({10 \choose 5}\) bilangan.

3.

Penyelesaian.
  1. \({30 \choose 21}\) cara. Setiap hasil dapat direpresentasikan oleh barisan yang terdiri atas 9 batang dan 21 batu.
  2. \({20 \choose 11}\) cara. Pertama, masukkan satu bola ke dalam setiap wadah. Setelah itu tersisa 9 batang dan 11 batu.

4.

Penyelesaian.
  1. \({10 \choose 8}\) solusi. Setelah setiap variabel terlebih dahulu memperoleh 1 batu, tersisa 8 batu dan 2 batang.
  2. \({13 \choose 11}\) solusi. Kita memiliki 11 batu dan 2 batang.
  3. \({22 \choose 2}\) solusi. Masalah ini ekuivalen dengan menentukan banyaknya solusi untuk \(x' + y' + z' = 20\) dengan \(x'\text{,}\) \(y'\text{,}\) dan \(z'\) taknegatif. (Sesungguhnya kita hanya melakukan substitusi. Ambil \(x = x'- 3\text{,}\) \(y = y' - 3\) dan \(z = z' - 3\)).

5.

Penyelesaian.
Dalam Yahtzee biasa, terdapat \({10 \choose 5}\) hasil yang mungkin. Setiap dadu direpresentasikan oleh satu batu; nilainya ditentukan oleh letak batu itu relatif terhadap batang.
Untuk Super-Yahtzee, terdapat \({10 \choose 4}\) hasil. Kita memiliki 6 batu (untuk 6 dadu) dan 4 batang (untuk 4 perpindahan di antara bilangan 1 sampai 5).

6.

Penyelesaian.
Kita harus menentukan banyaknya kombinasi berbeda dari 11 keping uang logam yang mungkin. Misalkan setiap batu merepresentasikan satu keping uang logam dan setiap batang merepresentasikan perpindahan dari satu jenis uang logam ke jenis berikutnya. Sebagai contoh, jika kita memiliki 7 keping uang logam, \(**|*||****\) merepresentasikan 2 penny, satu nickel, tanpa dime, dan 4 quarter. Banyaknya diagram batang dan batu dengan total 14 simbol (11 batu dan 3 batang) adalah \({14 \choose 11}\text{.}\) Jadi peluang Anda menebak dengan benar adalah \({0.00274725}\text{.}\)

7.

Penyelesaian.
Terdapat \({31 \choose 28}\) solusi. Pertama, kita memenuhi kendala pada variabel-variabel tersebut dengan membagikan 10 satuan kepada mereka. Kemudian kita menentukan semua solusi untuk \(x_1' + x_2' + x_3' + x_4' = 28\) dalam bilangan bulat taknegatif.

8.

Penyelesaian.
  1. \({11\choose 7}= {330}\text{.}\) Perhatikan bahwa fungsi yang menaik secara ketat pasti injektif. Jadi, semua 7 keluaran harus berbeda. Pertama-tama, pilih 7 keluaran yang akan kita gunakan: terdapat \({11 \choose 7}\) cara untuk melakukannya. Sekarang, ada berapa cara untuk menetapkan keluaran-keluaran itu kepada masukan \(1\) sampai 7? Hanya satu cara, karena hanya ada satu cara untuk menyusun bilangan dalam urutan menaik.
  2. \({17 \choose 7}\text{.}\) Ini sebenarnya merupakan masalah batang dan batu. Batu-batunya adalah 7 masukan, dan batang-batangnya adalah 10 celah di antara 11 keluaran yang mungkin. Pandanglah demikian: Kita akan menetapkan \(f(1)\text{,}\) lalu \(f(2)\text{,}\) lalu \(f(3)\text{,}\) dan seterusnya dalam urutan itu. Mulailah dengan kemungkinan keluaran 0. Kita dapat menggunakannya sebagai keluaran \(f(1)\text{,}\) atau beralih ke 1 sebagai keluaran yang mungkin. Misalkan kita menetapkan \(f(1) = 1\text{.}\) Sekarang kita berada pada 1 (tidak dapat kembali ke 0). Apakah \(f(2) = 1\text{?}\) Jika ya, letakkan satu batu lagi. Jika tidak, letakkan satu batang dan beralih ke 2. Anda mungkin beralih ke 3, lalu menetapkan \(f(2) = 3\) dan \(f(3) = 3\) (dua batu lagi) sebelum beralih ke 4 sebagai keluaran yang mungkin. Demikian seterusnya.

9.

Penyelesaian.
  1. \({17 \choose 7}\) racikan soda (urutan tidak penting dan pengulangan tidak diperbolehkan).
  2. \(P(17, 7) = (17)\cdot (17-1)\cdot \dots \cdot 11\) racikan soda (urutan penting dan pengulangan tidak diperbolehkan).
  3. \({23 \choose 7}\) racikan soda (urutan tidak penting dan pengulangan diperbolehkan; 7 batu dan 16 batang).
  4. \(17^{7}\) racikan soda (urutan penting dan pengulangan diperbolehkan; 17 pilihan dilakukan 7 kali).

Latihan Tambahan

1.

Penyelesaian.
  1. Anda mengambil 3 rasa stroberi, 1 limau, 0 akar manis, 2 bluberi, dan 0 permen karet.
  2. Ini terbalik. Kita tidak ingin batu merepresentasikan anak-anak karena anak-anak tersebut tidak identik, sedangkan batu-batunya identik. Sebaliknya, kita harus menggunakan 5 batu (untuk lolipop) dan 5 batang untuk berpindah di antara 6 anak. Sebagai contoh,
    \begin{equation*} \o\o||\o\o\o||| \end{equation*}
    merepresentasikan hasil ketika anak pertama memperoleh 2 lolipop, anak ketiga memperoleh 3, dan anak-anak lainnya tidak memperoleh satu pun.
  3. Ini adalah kata AAAEOO.
  4. Ini tidak merepresentasikan suatu solusi. Setiap batu seharusnya merepresentasikan satu dari 6 satuan yang jumlahnya 6, dan batang-batang seharusnya menandai perpindahan di antara variabel-variabel yang berbeda. Kita memiliki satu batang terlalu banyak. Salah satu contoh diagram yang benar adalah
    \begin{equation*} \o|\o\o||\o\o\o\text{,} \end{equation*}
    yang merepresentasikan bahwa \(x_1 = 1\text{,}\) \(x_2 = 2\text{,}\) \(x_3 = 0\text{,}\) dan \(x_4 = 3\text{.}\)

3.6 Pembuktian Kombinatorial
Latihan Tambahan

1.

Penyelesaian.
Bukti.
Pertanyaan: Ada berapa kata 2 huruf yang diawali dengan a, b, atau c dan diakhiri dengan y atau z?
Jawaban 1: Terdapat dua kata yang diawali dengan a, dua yang diawali dengan b, dan dua yang diawali dengan c, sehingga jumlahnya \(2+2+2\text{.}\)
Jawaban 2: Terdapat tiga pilihan untuk huruf pertama dan dua pilihan untuk huruf kedua, sehingga jumlahnya \(3 \cdot 2\text{.}\)
Karena kedua jawaban tersebut menjawab pertanyaan yang sama, keduanya sama. Jadi, \(2 + 2 + 2 = 3\cdot 2\text{.}\)

5.

Penyelesaian.
  1. Ia memiliki \({15 \choose 6}\) cara untuk memilih 6 pengiring pengantin, lalu untuk setiap cara tersebut terdapat 6 pilihan untuk pengiring pengantin utama. Jadi, ia memiliki \({15 \choose 6}6\) pilihan.
  2. Ia memiliki 15 pilihan untuk menentukan pengiring pengantin utama. Kemudian ia perlu memilih 5 dari 14 sahabat yang tersisa sebagai pengiring pengantin, yang dapat dilakukan dalam \({14 \choose 5}\) cara. Jadi, ia memiliki \(15 {14 \choose 5}\) pilihan.
  3. Kita telah menjawab pertanyaan (ada berapa rombongan pengantin yang dapat dipilih mempelai perempuan) dengan dua cara. Cara pertama menghasilkan ruas kiri identitas, sedangkan cara kedua menghasilkan ruas kanannya. Oleh karena itu, identitas tersebut berlaku.

7.

Penyelesaian.
Bukti.
Pertanyaan: Anda memiliki wadah besar berisi bola pingpong, yang masing-masing diberi nomor berbeda. Anda harus memilih \(k\) bola, menempatkan dua di antaranya ke dalam stoples dan yang lainnya ke dalam kotak. Ada berapa cara untuk melakukannya?
Jawaban 1: Pertama, pilih 2 dari \(n\) bola untuk ditempatkan dalam stoples. Kemudian pilih \(k-2\) dari \(n-2\) bola yang tersisa untuk ditempatkan dalam kotak. Tugas pertama dapat dilakukan dalam \({n \choose 2}\) cara berbeda dan tugas kedua dalam \({n-2 \choose k-2}\) cara. Jadi, terdapat \({n \choose 2}{n-2 \choose k-2}\) cara untuk memilih bola-bola tersebut.
Jawaban 2: Pertama, pilih \(k\) bola dari \(n\) bola di dalam wadah. Kemudian pilih 2 dari \(k\) bola yang telah dipilih untuk ditempatkan dalam stoples, dan tempatkan \(k-2\) bola yang tersisa dalam kotak. Tugas pertama dapat dilakukan dalam \({n \choose k}\) cara dan tugas kedua dalam \({k \choose 2}\) cara. Jadi, terdapat \({n \choose k}{k \choose 2}\) cara untuk memilih bola-bola tersebut.
Karena kedua jawaban mencacah hal yang sama, keduanya harus sama, sehingga identitas tersebut terbukti.

3.8 Pencacahan Lanjut dengan Prinsip Inklusi–Eksklusi
Soal Latihan

1.

Penyelesaian.
  1. \({17 \choose 6}\) kombinasi makanan. Pertama, belanjakan $7 untuk membeli satu dari setiap hidangan, lalu gunakan 11 batu untuk memilih hidangan di antara 6 batang.
  2. \({24 \choose 6}\) kombinasi makanan. Di sini Anda memiliki 18 batu dan 6 batang (yang memisahkan 7 hidangan). c. \({24 \choose 6} - \left[{7 \choose 1}{21 \choose 6} - {7 \choose 2}{18 \choose 6} + {7 \choose 3}{15 \choose 6}\cdots\right]\) kombinasi makanan. Gunakan prinsip inklusi–eksklusi untuk mengurangkan semua kombinasi yang memuat 3 porsi atau lebih dari suatu hidangan.

2.

Penyelesaian.
  1. \({29 \choose 9} = {1.0015\times 10^{7}}\) — terdapat 20 batu dan 9 batang.
  2. \({19 \choose 9}= {92378}\) — beli satu dari setiap hidangan dengan menggunakan $10. Setelah itu tersisa $10 untuk dibagikan di antara 10 hidangan, sehingga terdapat 10 batu dan 9 batang.
  3. \({29 \choose 9} - \left[{10 \choose 1}{24 \choose 9} - {10 \choose 2}{19 \choose 9} + \cdots\right]\) pesanan. Gunakan prinsip inklusi–eksklusi untuk mengurangkan semua pesanan yang memuat 5 porsi atau lebih dari suatu hidangan.

3.

Penyelesaian.
\({18 \choose 4} - \left[ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right]\text{.}\)

4.

Penyelesaian.
Cara termudah untuk menyelesaikan masalah ini adalah terlebih dahulu memberikan nilai minimum (1) kepada setiap variabel, lalu mencacah solusi untuk \(y_1 + y_2 + y_3 + y_4 = 14\) dengan \(0 \le y_i \le 5\text{.}\) Dengan mengambil \(x_i = y_i+1\text{,}\) setiap solusi persamaan baru ini berkorespondensi dengan tepat satu solusi persamaan semula.
Sekarang, semua cara membagikan 14 satuan kepada empat variabel \(y_i\) dapat ditentukan dengan batang dan batu, tepatnya 14 batu dan 3 batang, sehingga terdapat \({17 \choose 14}\) cara. Namun, hitungan ini mencakup cara-cara ketika satu atau lebih variabel \(y_i\) diberi lebih dari 5 satuan. Karena itu, kurangkan dengan prinsip inklusi–eksklusi untuk memperoleh \(\displaystyle{ {17 \choose 3} -\left( {4\choose 1} {11 \choose 3}-{4\choose 2} {5 \choose 3} + \dots \right) }\)
Koefisien \({4 \choose 1}\) mencacah banyaknya cara memilih satu variabel yang diberi terlalu banyak satuan; koefisien \({11 \choose 3}\) mencacah banyaknya cara membagikan satuan yang tersisa kepada 4 variabel, dan seterusnya.

5.

Penyelesaian.
  1. \({15 \choose 13} = 105\text{.}\) Karena setiap siswa dapat menerima paling banyak satu bintang, kita harus memilih 13 dari 15 siswa yang akan menerimanya.
  2. Tanpa pembatasan tersebut, terdapat \({27\choose 14}\) cara untuk membagikan bintang. Sekarang kita menggunakan prinsip inklusi–eksklusi (PIE) untuk menyingkirkan semua pembagian yang membuat sedikitnya satu siswa menerima lebih dari satu bintang:
\(\displaystyle{ {27 \choose 14} - \left[{15 \choose 1}{25 \choose 14} - {15\choose 2}{23 \choose 14} + {15\choose 3}{21 \choose 14} - \cdots \right] = 105. }\)

6.

Penyelesaian.
Pertama, pilih satu dari 6 anggota untuk ditetapkan. Untuk setiap pilihan tersebut, susun 5 anggota yang tersisa tanpa titik tetap menggunakan rumus lanjutan prinsip inklusi–eksklusi. Diperoleh \({6 \choose 1}\left( 5! - \left[{5 \choose 1}4! - {5 \choose 2}3! + \cdots + (-1)^{5+1}{5 \choose 5}0! \right] \right)\) permutasi.

7.

Penyelesaian.
Terdapat \({11 \choose 6}\left(5! - \left[{5 \choose 1} 4! - {5 \choose 2}3! + \cdots + (-1)^{5+1}{5 \choose 5}0! \right]\right)={20328}\) cara. Kita memilih 6 dari 11 perempuan untuk menerima topinya sendiri, lalu mengalikannya dengan banyak cara untuk membagikan topi yang tersisa tanpa seorang pun menerima topinya sendiri.

8.

Penyelesaian.
  1.  
    \(\displaystyle{ 9! - \left[{9 \choose 1}8! - {9 \choose 2}7! + \cdots + (-1)^{9+1}{9 \choose 9}0! \right] = {133496} }\)
  2.  
    \(\displaystyle{ {9 \choose 4}\left(5! - \left[{5\choose 1}4! - {5 \choose 2}3! + \cdots + (-1)^{5+1}{5 \choose 5}0!\right]\right) = {5544} }\)
  3. 0. Jika 8 hadiah sudah mendapatkan label aslinya, hanya tersisa satu hadiah dan satu label. Karena itu, hadiah ke-9 juga harus mendapatkan labelnya sendiri.

9.

Penyelesaian.
Ada \(5 \cdot 6^{8}\) fungsi yang memenuhi \(f(1) \ne c\) dan \(5 \cdot 6^{8}\) fungsi lainnya yang memenuhi \(f(2) \ne f\text{.}\) Ada \(5^2 \cdot 6^{7}\) fungsi yang memenuhi \(f(1) \ne c\) sekaligus \(f(2) \ne f\text{.}\) Jadi, banyaknya fungsi yang memenuhi \(f(1) \ne c\) atau \(f(2) \ne f\) atau keduanya adalah
\(\displaystyle{ 5 \cdot 6^{8}+ 5 \cdot 6^{8} - 5^2 \cdot 6^{7} = {9.79776\times 10^{6}}. }\)

10.

Penyelesaian.
Terdapat \(4^{11} - \left[{4 \choose 1}3^{11} - {4 \choose 2}2^{11} + {4 \choose 3}1^{11} + \cdots +(-1)^{4}{4 \choose 3}1^{11}\right]\) fungsi. Suku \(4^{11}\) menghitung semua fungsi dari \(A\) ke \(B\text{.}\) Kita mengurangi fungsi-fungsi yang tidak surjektif. Pilih satu anggota \(B\) yang tidak termasuk dalam daerah hasil (dengan \({4 \choose 1}\) cara), lalu hitung semua fungsi semacam itu (\(3^{11}\)). Namun, cara ini menghitung terlalu banyak fungsi yang mengecualikan dua anggota \(B\) dari daerah hasil, sehingga fungsi-fungsi tersebut harus dikurangi. Lanjutkan dengan cara yang sama menggunakan prinsip inklusi–eksklusi (PIE).

11.

Penyelesaian.
Ada 14833 fungsi. Pertanyaan ini sebenarnya meminta banyaknya permutasi tanpa titik tetap pada 8 anggota.

Latihan Tambahan

2.

Penyelesaian.
Kesembilan permutasi tanpa titik tetap tersebut adalah 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, dan 4321.

3.9 Ringkasan Bab

Tinjauan Bab

3.9.1.
Penyelesaian.
  1. \({7 \choose 4}\) cara. Setelah memberikan satu hadiah kepada setiap anak, tersisa 4 hadiah (bintang) yang harus dibagi di antara 4 anak (menggunakan 3 sekat).
  2. \({11 \choose 8}={165}\) cara. Terdapat 8 bintang dan 3 sekat.
  3. \(4^{8}\text{.}\) Untuk setiap hadiah terdapat 4 pilihan penerima. Ini setara dengan membentuk fungsi dari himpunan hadiah ke himpunan anak.
  4. \(4^{8}- \left[{4 \choose 1}(4-1)^{8} - {4\choose 2}(4-2)^{8} + {4 \choose 3}(4-3)^{8} \dots \right]\) cara. Sekarang fungsi dari himpunan hadiah ke himpunan anak harus surjektif.
3.9.2.
Penyelesaian.
  1. Bukan keduanya. Terdapat \({14 \choose 4}\) lintasan.
  2. \({10\choose 4}\) pilihan dasi kupu-kupu.
  3. \(P(10,4)\text{,}\) karena urutan penting.
  4. Bukan keduanya. Dengan mengasumsikan Anda hanya akan mengenakan keempat dasi itu pada 4 dari 7 hari, tanpa pengulangan: \({10\choose 4}P(7,4)\text{.}\)
  5. \(P(10,4)\text{.}\)
  6. \({10\choose 4}\text{.}\)
  7. Bukan keduanya. Karena huruf boleh diulang: \(10^4\text{.}\) Jika pengulangan tidak diperbolehkan, jawabannya adalah \(P(10,4)\text{.}\)
  8. Bukan keduanya. Sebenarnya, “k” adalah huruf ke-11 dalam alfabet, sehingga jawabannya adalah 0. Jika “k” termasuk di antara 10 huruf pertama, hanya akan ada 1 cara – yakni menuliskannya.
  9. Bukan keduanya. Jawabannya adalah \({9\choose 3}\) (jika setiap anak memperoleh sebuah apel) atau \({13 \choose 3}\) (jika ada anak yang boleh tidak memperoleh apel).
  10. Bukan keduanya. Perhatikan bahwa jawabannya tidak mungkin \({10 \choose 4}\) karena 10 objek dan 4 objek tersebut berasal dari kelompok yang berbeda. Jawabannya adalah \(4^{10}\text{,}\) dengan mengasumsikan setiap anak menyantap satu jenis sereal.
  11. \({10 \choose 4}\text{.}\) Jangan terkecoh oleh kata “menyusun” dalam pertanyaan tersebut. Anda memilih 4 dari 10 posisi untuk menempatkan angka 1.
  12. \({10 \choose 4}\) (dengan mengasumsikan urutan tidak relevan).
  13. Bukan keduanya. Jawabannya adalah \(16^{10}\) (setiap anak memilih ya atau tidak untuk masing-masing dari 4 jenis).
  14. Bukan keduanya. Jawabannya 0.
  15. Bukan keduanya. Jawabannya adalah \(4^{10} - [{4\choose 1}3^{10} - {4\choose 2}2^{10} + {4 \choose 3}1^{10}]\text{.}\)
  16. Bukan keduanya. Jawabannya adalah \(10\cdot 4\text{.}\)
  17. Bukan keduanya. Jawabannya adalah \(4^{10}\text{.}\)
  18. \({10 \choose 4}\) (yang sama dengan \({10 \choose 6}\)).
  19. Bukan keduanya. Jika semua anak dianggap identik dan Anda tidak menginginkan tim kosong, jawabannya adalah \({10 \choose 4}\text{.}\) Namun, persoalan ini sama dengan menentukan banyaknya fungsi surjektif dari himpunan berukuran 11 ke himpunan berukuran 5.
  20. \({10 \choose 4}\text{.}\)
  21. \({10 \choose 4}\text{.}\)
  22. Bukan keduanya. Jawabannya adalah \(4!\text{.}\)
  23. Bukan keduanya. Jawabannya adalah \({10 \choose 4}\) jika tidak ada pilihan yang diulang. Jika pengulangan diperbolehkan, persoalannya menjadi \(x_1 + x_2 + \cdots +x_{10} = 4\text{,}\) yang memiliki \({13 \choose 9}\) solusi dalam bilangan bulat taknegatif.
  24. Bukan keduanya. Karena pengulangan jenis kue kering diperbolehkan, jawabannya adalah \(10^4\text{.}\) Tanpa pengulangan, jawabannya adalah \(P(10,4)\text{.}\)
  25. \({10 \choose 4}\) karena nilai ini sama dengan \({9 \choose 4} + {9 \choose 3}\text{.}\)
  26. Bukan keduanya. Persoalan ini akan menjadi persoalan pencacahan yang rumit (mungkin menggunakan prinsip inklusi–eksklusi).
3.9.3.
Penyelesaian.
  1. \(2^{12} = {4096}\) pilihan. Untuk setiap dasi ada dua pilihan: dikenakan atau tidak.
  2. Terdapat 15 pilihan dasi panjang (dari \(2^{4}\) pilihan dikurangi pilihan “tanpa dasi panjang”) dan 255 pilihan dasi kupu-kupu (dari \(2^{8}\) pilihan dikurangi pilihan “tanpa dasi kupu-kupu”). Jadi, seluruhnya terdapat \({15} \cdot {255} = {3825}\) pilihan.
  3. \({4\choose 3}{8\choose 2} = {112}\) pilihan.
  4. Pilih satu dari 2 dasi kupu-kupu untuk dikenakan paling luar. Setelah itu, terdapat 4 pilihan untuk dasi berikutnya, 4-1 pilihan untuk dasi sesudahnya, dan seterusnya. Jadi, terdapat \(2\cdot 4! = {48}\) pilihan.
3.9.4.
Penyelesaian.
Anda memiliki 8 dasi kupu-kupu ungu, 3 dasi kupu-kupu merah, 3 dasi kupu-kupu biru, dan 5 dasi kupu-kupu hijau. Ada berapa cara memilih satu dasi kupu-kupu dari setiap warna untuk dibawa dalam perjalanan? Terdapat \(8 \cdot 3 \cdot 3 \cdot 5\) cara. Ada berapa pilihan jika Anda hendak mengenakan satu dasi kupu-kupu besok? Terdapat \(8 + 3 + 3 + 5\) pilihan.
3.9.5.
Penyelesaian.
  1. \(8^{11}\) bilangan.
  2. \(8^{10} \cdot 4\) bilangan (pilih sembarang digit untuk 10 digit pertama, lalu pilih digit terakhir yang genap atau ganjil sesuai paritas jumlah digit pertama agar jumlah seluruh digit genap).
  3. Kita memerlukan sedikitnya 6 digit genap. Untuk tepat 6 digit genap terdapat \({11 \choose 6}4^6 4^{11-6}\text{.}\) Untuk 6+1 digit genap terdapat \({11 \choose (6+1)}4^{6+1} *4^{11-6-1}\text{,}\) dan seterusnya. Dengan menjumlahkan semuanya, diperoleh banyak bilangan yang memiliki sedikitnya 6 digit genap.
3.9.6.
Penyelesaian.
Ada 47 penumpang. Kita mencari kardinalitas gabungan tiga himpunan yang tidak saling lepas. Dengan prinsip inklusi–eksklusi (PIE), diperoleh \(27+22+30-(13 +11 + 12) + 4 = {47}\text{.}\)
3.9.7.
Penyelesaian.
  1. \(2^11\) string.
  2. \({11 \choose 4}\) string.
  3. \({11 \choose 4}\) himpunan bagian.
3.9.8.
Penyelesaian.
\(3^{5}\cdot{16 \choose 11} + 5^{12}\cdot{20 \choose 8}\text{.}\)
3.9.9.
Penyelesaian.
Jika pengulangan huruf diperbolehkan, kita memilih 3 dari 11 posisi yang akan ditempati huruf vokal, kemudian memilih satu dari 5 huruf vokal untuk setiap posisi tersebut, dan akhirnya memilih satu dari 21 huruf lainnya untuk masing-masing dari 8 posisi yang tersisa. Jadi, terdapat \({11 \choose 3}5^3 21^{8}\) kata.
Tanpa pengulangan, kita tetap memilih posisi huruf-huruf vokal, tetapi setiap kali sebuah huruf vokal ditempatkan, pilihan untuk huruf vokal berikutnya berkurang satu. Demikian pula, huruf konsonan tidak boleh berulang. Dengan demikian, terdapat \({11 \choose 3}P(5,3) P(21, 8)\) kata.
3.9.10.
Penyelesaian.
  1. \({3 \choose 2}{7 \choose 3}={105}\) lintasan.
  2. \({10 \choose 5} - {8 \choose 4}{2 \choose 1}={112}\) lintasan.
  3. \({3 \choose 2}{7 \choose 3} + {8 \choose 4}{2 \choose 1} - {3 \choose 2}{5 \choose 2}{2 \choose 1}= {185}\) lintasan.
3.9.11.
Penyelesaian.
Terdapat \({30 \choose 18}\left({30 \choose 18} - 1\right)\) rute. Untuk setiap pilihan di antara \(\binom{30}{18}\) rute menuju tempat kerja, banyaknya pilihan rute pulang yang berbeda tepat satu lebih sedikit.
3.9.12.
Penyelesaian.
Terdapat \(2^{2} + 2^{3} - 2^{0}\) string (dengan menggunakan prinsip inklusi–eksklusi).
3.9.13.
Penyelesaian.
Terdapat \({6 \choose 5} + {7 \choose 6} - {4 \choose 4}\) string.
3.9.14.
Penyelesaian.
  1. Terdapat 7 posisi yang mungkin untuk mengawali subkata tersebut, lalu terdapat \(6!\) cara untuk menyusun huruf-huruf lain pada 6 posisi yang tersisa. Jadi, banyaknya kata yang menghindari subkata “bad” sebagai tiga huruf berurutan adalah \(9! - 7\cdot 6!={357840}\text{.}\)
  2. Jika sekarang kita harus menghindari kata yang menempatkan “b” sebelum “a” dan “a” sebelum “d”, kita harus memilih posisi ketiga huruf tersebut (dalam urutan itu), lalu menyusun 6 huruf yang tersisa. Jadi, terdapat \(9! - {9 \choose 3}6!={302400}\) kata.
3.9.15.
Penyelesaian.
\(2^n\) adalah banyaknya lintasan kisi yang panjangnya \(n\text{,}\) sebab pada setiap langkah Anda dapat bergerak ke atas atau ke kanan. Lintasan semacam itu akan berakhir pada garis \(x + y = n\text{.}\) Jadi, Anda akan berakhir di \((0,n)\text{,}\) atau \((1,n-1)\text{,}\) atau \((2, n-2)\text{,}\) atau … atau \((n,0)\text{.}\) Jika lintasan menuju setiap titik tersebut dicacah secara terpisah, diperoleh \({n \choose 0}\text{,}\) \({n \choose 1}\text{,}\) \({n \choose 2}\text{,}\) …, \({n \choose n}\) (setiap kali dengan memilih langkah mana di antara \(n\) langkah yang bergerak ke kanan). Kedua metode ini mencacah kuantitas yang sama, sehingga hasilnya sama.
3.9.16.
Penyelesaian.
  1. \({18 \choose 13}={8568}\) cara.
  2. \({24 \choose 19}={42504}\) cara.
  3. \(\displaystyle \sum_{j=0}^{\lfloor 19/8\rfloor}(-1)^j{6 \choose j}{18-j8 \choose 5}={7056}\) cara.
3.9.17.
Penyelesaian.
  1. Terdapat \(6^5 + 6^5 - 6^4={14256}\) fungsi.
  2. Terdapat \(5\cdot 6^5 + 6 \cdot 5 \cdot 6^4 - 5 \cdot 5 \cdot 6^4={45360}\) fungsi.
  3. Terdapat \(6! - \left[ 5! + 5! - 4! \right]={504}\) fungsi. Perhatikan bahwa kita menggunakan faktorial, bukan perpangkatan, karena kita mencari fungsi injektif.
  4. Karena domain dan kodomain merupakan himpunan berhingga dengan kardinalitas yang sama, surjektif ekuivalen dengan injektif. Jadi, kita dapat memulai dengan semua \(6!\) fungsi injektif dan mengurangkan fungsi-fungsi yang memiliki satu atau lebih titik tetap. Kita memperoleh \(\displaystyle \sum_{j=0}^{6}(-1)^j{6 \choose j}(6-j)!={265}\) fungsi.
3.9.18.
Penyelesaian.
\(\displaystyle \sum_{j=0}^{5}(-1)^j{5 \choose j}(5-j)^{6}={1800}\text{.}\)
3.9.19.
Penyelesaian.
  1. Terdapat \({15 \choose 8}={6435}\) kombinasi. Kita harus memilih 8 dari 15 jenis kue. Urutan tidak penting.
  2. Terdapat \(P(15, 8) = 15 \cdot (15-1) \cdot (15-2) \cdot \dots \cdot (15-8+1)= {2.59459\times 10^{8}}\) cara. Kita memilih sekaligus mengurutkan 8 dari 15 jenis kue. Sekarang urutan penting.
  3. Terdapat \({36 \choose 22}={3.7963\times 10^{9}}\) pilihan. Kita menempatkan 14 batang untuk memisahkan 15 jenis saat menyusun 22 kue. Kue-kue tersebut merupakan batu, sedangkan batang menandai perpindahan antarjenis.
  4. Terdapat \(15^{22}\) pilihan. Ada 15 pilihan untuk kue berbentuk angka “1”, 15 pilihan untuk kue berbentuk angka “2”, dan seterusnya.
  5. Terdapat \(\displaystyle \sum_{j=0}^{15}(-1)^j{15 \choose j}(15-j)^{22}={4.51953\times 10^{23}}\) pilihan. Kita harus menggunakan prinsip inklusi–eksklusi untuk mengecualikan semua cara yang tidak menggunakan satu atau lebih jenis kue.
3.9.20.
Penyelesaian.
  1. Anda memberikan 4 jenis kue kering kepada dosen Anda yang dipilih dari 10 jenis kue kering berbeda. Persoalan ini tidak mudah ditafsirkan menggunakan fungsi. Kita dapat mengatakan bahwa domain memuat 4 jenis yang akan diberikan kepada dosen dan kodomain memuat 10 jenis yang dapat dipilih, tetapi pencacahan fungsi injektif akan menghasilkan terlalu banyak kemungkinan (tidak penting apakah Anda memilih jenis 3 terlebih dahulu dan jenis 2 kemudian, atau sebaliknya; yang penting adalah kedua jenis tersebut dipilih).
  2. Kita ingin meninjau fungsi injektif dari himpunan \(\{\)terbanyak, terbanyak kedua, tersedikit kedua, tersedikit\(\}\) ke himpunan 10 jenis kue kering. Kita menginginkan fungsi injektif karena kita tidak dapat memilih jenis kue kering yang sama untuk diberikan dalam jumlah terbanyak sekaligus tersedikit (misalnya).
  3. Persoalan ini tidak cocok ditafsirkan sebagai fungsi. Masalahnya, domain harus berupa 12 kue kering yang Anda panggang, tetapi elemen-elemen ini tidak dapat dibedakan (tidak ada kue kering pertama, kue kering kedua, dan seterusnya).
  4. Domainnya adalah 12 bentuk, sedangkan kodomainnya adalah 10 jenis kue kering. Karena kita dapat menggunakan jenis yang sama untuk bentuk yang berbeda, kita tertarik untuk mencacah semua fungsi di sini.
  5. Di sini kita mensyaratkan agar setiap jenis kue kering diberikan setidaknya satu kali, sehingga sekarang kita menanyakan banyaknya fungsi surjektif di antara fungsi-fungsi yang dicacah pada bagian sebelumnya.

4 Barisan
4.1 Mendeskripsikan Barisan
Latihan Tambahan

1.

Penyelesaian.
  1. Definisi rekursifnya adalah \(a_n = a_{n-1} + 2\) dengan \(a_1 = 1\text{.}\) Rumus tertutupnya adalah \(a_n = 2n-1\text{.}\)
  2. Barisan jumlah parsialnya adalah \(1, 4, 9, 16, 25, 36, \ldots\text{.}\) Definisi rekursifnya (seperti biasa) adalah \(b_n = b_{n-1} + a_n\text{,}\) yang dalam kasus ini menjadi \(b_n = b_{n-1} + 2n-1\text{.}\) Tampaknya rumus tertutupnya adalah \(b_n = n^2\)

2.

Penyelesaian.
  1. \(0, 1, 2, 4, 7, 12, 20, \ldots\text{.}\)
  2. \(F_0 + F_1 + \cdots + F_n = F_{n+2} - 1\text{.}\)

3.

Penyelesaian.
Semua barisan mempunyai relasi rekurensi yang sama: \(a_n = a_{n-1} + a_{n-2}\) (sama seperti bilangan Fibonacci). Satu-satunya perbedaan terletak pada syarat awalnya.

4.

Penyelesaian.
\(3, 10, 24, 52, 108,\ldots\text{.}\) Definisi rekursif untuk \(10, 24, 52, \ldots\) adalah \(a_n = 2a_{n-1} + 4\) dengan \(a_1 = 10\text{.}\)

5.

Penyelesaian.
\(-1, -1, 1, 5, 11, 19,\ldots\) Dengan demikian, barisan \(0, 2, 6, 12, 20,\ldots\) mempunyai rumus tertutup \(a_n = (n+1)^2 - 3(n+1) + 2\text{.}\)

6.

Penyelesaian.
Dari rumus tertutup ini diperoleh \(a_{n-1} = 3\cdot 2^{n-1} + 7 \cdot 5^{n-1}\) dan \(a_{n-2} = 3\cdot 2^{n-2} + 7 \cdot 5^{n-2}\text{.}\) Kemudian kita memperoleh
\begin{align*} 7a_{n-1} - 10a_{n-2} = \amp 7(3\cdot 2^{n-1} + 7 \cdot 5^{n-1}) - 10(3\cdot 2^{n-2} + 7 \cdot 5^{n-2})\\ = \amp 21\cdot 2^{n-1} + 49 \cdot 5^{n-1} - 30\cdot 2^{n-2} - 70 \cdot 5^{n-2}\\ = \amp 21\cdot 2^{n-1} + 49 \cdot 5^{n-1} - 15\cdot 2^{n-1} - 14 \cdot 5^{n-1}\\ = \amp 6\cdot 2^{n-1} + 35 \cdot 5^{n-1}\\ = \amp 3\cdot 2^{n} + 7 \cdot 5^{n} = a_n\text{.} \end{align*}
Jadi, rumus tertutup tersebut sesuai dengan relasi rekurensi. Rumus tertutup itu mempunyai suku awal \(a_0 = 10\) dan \(a_1 = 41\text{.}\)

10.

Penyelesaian.
  1. \(\d\sum_{k=1}^n 2k\text{.}\)
  2. \(\d\sum_{k=1}^{107} (1 + 4(k-1))\text{.}\)
  3. \(\d\sum_{k=1}^{50} \frac{1}{k}\text{.}\)
  4. \(\d\prod_{k=1}^n 2k\text{.}\)
  5. \(\d\prod_{k=1}^{100} \frac{k}{k+1}\text{.}\)

11.

Penyelesaian.
  1. \(\d\sum_{k=1}^{100} (3+4k) = 7 + 11 + 15 + \cdots + 403\text{.}\)
  2. \(\d\sum_{k=0}^n 2^k = 1 + 2 + 4 + 8 + \cdots + 2^n\text{.}\)
  3. \(\d\sum_{k=2}^{50}\frac{1}{(k^2 - 1)} = \frac{1}{3} + \frac{1}{8} + \frac{1}{15} + \cdots + \frac{1}{2499}\text{.}\)
  4. \(\d\prod_{k=2}^{100}\frac{k^2}{(k^2-1)} = \frac{4}{3}\cdot\frac{9}{8}\cdot\frac{16}{15}\cdots\frac{10000}{9999}\text{.}\)
  5. \(\d\prod_{k=0}^n (2+3k) = (2)(5)(8)(11)(14)\cdots(2+3n)\text{.}\)

4.2 Laju Pertumbuhan
Soal Latihan

8.

Penyelesaian.
Untuk barisan aritmetika: \(x = 83.6666666666667\text{,}\) \(y = 42.3333333333333\text{.}\) Kita mengetahui bahwa \(125 + d = x\text{,}\) \(x + d = y\text{,}\) dan \(y + d = 1\text{.}\) Dengan kata lain, \(125 + 3d = 1\text{,}\) sehingga \(d = -41.3333333333333\text{.}\) Untuk barisan geometri: \(x = {25}\) dan \(y = {5}\text{.}\) Kita dapat menentukan rasio tetap barisan geometri dengan menyelesaikan \(125\cdot r^3 = 1\) untuk \(r\text{.}\)

9.

Penyelesaian.
Untuk barisan aritmetika: \(x = 18 \text{,}\) \(y = 31 \text{.}\) Kita mengetahui bahwa \(5 + d = x\text{,}\) \(x + d = y\text{,}\) dan \(y + d = 44\text{.}\) Dengan kata lain, \(5 + 3d = 44\text{,}\) sehingga \(d = (39)/3\text{.}\)
Untuk barisan geometri: \(x = {10.3228}\) dan \(y = {21.312}\text{.}\) Kita dapat menentukan rasio tetap barisan geometri dengan menyelesaikan \(5\cdot r^3 = 44\) untuk \(r\text{.}\)

4.3 Barisan Polinomial
Soal Latihan

1.

Penyelesaian.
Ini adalah barisan aritmetika dengan suku awal 10 dan beda tetap 4.
Pada bagian terakhir, Anda menentukan barisan jumlah parsial yang kemudian ditambah dengan 5.

2.

Penyelesaian.
  1. \(50\text{,}\) yaitu \(38+12\text{.}\)
  2. Barisan tersebut adalah barisan aritmetika dengan \(a_0 = 2\) dan beda tetap 12, sehingga \(a_n = 2 + 12n\text{.}\)
  3. \(59600\text{.}\) Kita ingin menghitung \(2 + 14 + 26 + \cdots + 1190\text{.}\) Balik urutannya lalu jumlahkan untuk memperoleh 100 pasangan yang masing-masing berjumlah 1192, sehingga totalnya 119200. Nilai ini dua kali jumlah yang dicari.

3.

Penyelesaian.
  1. 33.
  2. \(\displaystyle \frac{294 \cdot (32+1)}{2} = 4851\text{.}\)

4.

Penyelesaian.
  1. \({n-2+1}\) suku, karena untuk memperoleh \(10\) dari rumus \(5n+0\) kita harus menggunakan \(n=2\text{.}\)
  2. \(5n - 5\text{,}\) yaitu 5 lebih kecil daripada \(5n+0\) (atau substitusikan \(n-1\) untuk \(n\)).
  3. \(\frac{(5n+10)*({n-2+1})}{2}\text{.}\) Balik urutan suku lalu jumlahkan. Setiap pasangan menghasilkan konstanta \(5n+10\text{,}\) dan terdapat \({n-2+1}\) suku.

5.

Penyelesaian.
\(666246\text{.}\) Jika kita menetapkan \(a_0 = 6\text{,}\text{,}\) suku-suku dalam jumlah tersebut membentuk barisan aritmetika dengan rumus tertutup \(a_n = 6+11n\text{.}\) Jadi, \(3823 = a_{347}\text{,}\) dan terdapat 348 suku dalam jumlah itu. Balik urutannya lalu jumlahkan untuk memperoleh 348 pasangan identik yang masing-masing berjumlah 3829. Hasil tersebut dua kali jumlah yang dicari. Maka \(3829\cdot 348/2 = 666246\text{.}\)

6.

Penyelesaian.
\(a_n = {2n^{2}+3n}\text{.}\) Kita mengetahui bahwa rumus yang dicari berbentuk kuadrat karena beda keduanya tetap. Jadi, \(a_n = an^2 + bn + c\text{.}\) Karena \(a_0 = 0\text{,}\text{,}\) diperoleh \(c= 0\text{.}\) Selanjutnya, selesaikan sistem
\(\begin{aligned} {5} \amp = a + b\\ {14} \amp = 4a + 2b \end{aligned}\)
untuk memperoleh \(a = 2\) dan \(b = 3\text{.}\)

7.

Penyelesaian.
\(a_n = {n^{2}+2n-1}\text{.}\) Kita mengetahui bahwa rumus yang dicari berbentuk kuadrat karena beda keduanya tetap. Jadi, \(a_n = an^2 + bn + c\text{.}\) Karena \(a_0 = {-1}\text{,}\) diperoleh \(c= {-1}\text{.}\) Selanjutnya, selesaikan sistem
\(\begin{aligned} {2} \amp = a + b + {-1}\\ {7} \amp = 4a + 2b + {-1} \end{aligned}\)
untuk memperoleh \(a = {1}\) dan \(b = {2}\text{.}\)

8.

Penyelesaian.
\(a_n = {\left({\frac{3}{2}}\right)n^{3}+\left({\frac{7}{2}}\right)n-1}\text{.}\) Kita mengetahui bahwa rumus yang dicari berbentuk kubik karena beda ketiganya tetap. Jadi, \(a_n = an^3 + bn^2 + cn + d\text{.}\) Karena \(a_0 = {-1}\text{,}\) diperoleh \(d= {-1}\text{.}\) Selanjutnya, selesaikan sistem
\begin{equation*} \begin{aligned} {4} \amp = a + b + c + {-1}\\ {18} \amp = 8a + 4b + 2c + {-1}\\ {50} \amp = 27a + 9b + 3c + {-1}\\ \end{aligned} \end{equation*}
untuk memperoleh \(a = {{\frac{3}{2}}}\text{,}\) \(b = 0\text{,}\) dan \(c = {{\frac{7}{2}}}\text{.}\)

9.

Penyelesaian.
\(a_n = {3n^{3}+2n^{2}+4n-4}\text{.}\) Kita mengetahui bahwa rumus yang dicari berbentuk kubik karena beda ketiganya tetap. Jadi, \(a_n = an^3 + bn^2 + cn + d\text{.}\) Dengan menelusuri barisan ke belakang, diperoleh \(a_0 = {-4}\text{,}\) sehingga \(d= {-4}\text{.}\) Kemudian selesaikan sistem
\(\begin{aligned} {5} \amp = a + b + c + {-4}\\ {36} \amp = 8a + 4b + 2c + {-4}\\ {107} \amp = 27a + 9b + 3c + {-4}\\ \end{aligned}\)
untuk memperoleh \(a = {3}\text{,}\) \(b = {2}\text{,}\) dan \(c = {4}\text{.}\)

10.

Penyelesaian.
\(a_{n-1} = 3(n-1)^2 - 3(n-1) - 5 = {3n^{2}-9n+1}\text{.}\) Jadi, \(a_n - a_{n-1} = {6n-6}\text{.}\) Perhatikan bahwa barisan ini linear (aritmetika).

11.

Penyelesaian.
\(a_n = {n^{3}+6n^{2}+n}\text{.}\) Kita mengetahui bahwa polinom yang dicari berderajat tiga karena selisih ketiganya konstan. Jadi, \(a_n = an^3 + bn^2 + cn + d\text{.}\) Dengan bekerja mundur, kita memperoleh \(a_0 = {0}\text{,}\) sehingga \(d= {0}\text{.}\) Selanjutnya, selesaikan sistem
\(\begin{aligned} {8} \amp = a + b + c\\ {34} \amp = 8a + 4b + 2c\\ {84} \amp = 27a + 9b + 3c\\ \end{aligned}\)
untuk memperoleh \(a = {1}\text{,}\) \(b = {6}\text{,}\) dan \(c = {1}\text{.}\)

Latihan Tambahan

4.

Penyelesaian.
\(a_n = n^2 - n + 1\text{.}\)

5.

Penyelesaian.
\(a_n = n^3 + n^2 - n + 1\)

6.

Penyelesaian.
Kita memiliki \(2 = 2\text{,}\) \(7 = 2+5\text{,}\) \(15 = 2 + 5 + 8\text{,}\) \(26 = 2+5+8+11\text{,}\) dan seterusnya. Suku-suku dalam penjumlahan tersebut diberikan oleh barisan aritmetika \(b_n = 2+3n\text{.}\) Dengan kata lain, \(a_n = \sum_{k=0}^n (2+3k)\text{.}\) Untuk menemukan rumus tertutupnya, kita balikkan urutan dan jumlahkan. Kita memperoleh \(a_n = \frac{(4+3n)(n+1)}{2}\) (faktor \(n+1\) muncul karena terdapat \(n+1\) suku dalam penjumlahan untuk \(a_n\)).

9.

Penyelesaian.
\(a_{n-1} = a(n-1)^2 + b(n-1) + c = an^2 - 2an + a + bn - b + c\text{.}\) Oleh karena itu, \(a_n - a_{n-1} = 2an - a + b\text{,}\) yang berbentuk aritmetika. Perhatikan bahwa bentuk ini tidak persis sama dengan turunan \(a_n\text{,}\) yaitu \(2an + b\text{,}\) tetapi keduanya hampir sama.

10.

Penyelesaian.
Tidak. Barisan selisihnya sama dengan barisan awal, sehingga tidak ada tingkat selisih yang akan menjadi konstan.

11.

Penyelesaian.
Tidak. Barisan tersebut merupakan barisan geometri dan memiliki rumus tertutup \(2\cdot 3^n\text{.}\) Rumus ini merupakan fungsi eksponensial, yang tidak sama dengan polinomial berderajat berapa pun. Jika barisan selisih ke-\(n\) konstan, rumus tertutup barisan awal akan berupa polinomial berderajat \(n\text{.}\)

4.4 Barisan Eksponensial
Soal Latihan

1.

Penyelesaian.
\(\frac{3\cdot 2^{19}-3}{1}\text{.}\) Misalkan jumlah tersebut adalah \(S\text{,}\text{,}\) lalu hitung \(2S - S = 1S\text{,}\) sehingga semua suku kecuali \(3\) dan \(3\cdot 2^{19}\) saling meniadakan. Selanjutnya, selesaikan persamaan untuk \(S\text{.}\)

2.

Penyelesaian.
\(\frac{1 - (-1)^{28} \frac{3^{28}}{5^{28}}}{8/5}\text{.}\) Hitung \(S + \frac{3}{5}S\text{.}\)

3.

Penyelesaian.
\(a_n = 1 + 2^{n+1}\text{.}\) Di sini kita perlu menggunakan metode teleskopik atau iterasi. Sebagai contoh, metode teleskopik menghasilkan
\begin{equation*} \begin{aligned} a_1 - a_0 \amp = 2^1\\ a_2 - a_1 \amp = 2^2\\ a_3 - a_2 \amp = 2^3\\ \vdots\amp \vdots \\ a_n - a_{n-1} \amp = 2^n \end{aligned} \end{equation*}
yang jika dijumlahkan menghasilkan \(a_n - a_0 = 2^{n+1} - 2\) (dengan menggunakan teknik kalikan-geser-kurangkan untuk deret geometri di ruas kanan). Substitusikan \(a_0 =3\text{,}\) lalu selesaikan persamaan untuk \(a_n\) guna menuntaskan penyelesaian.

4.

Penyelesaian.
Dengan teknik akar karakteristik, diperoleh \(a_n = {2^{n}+\left(-5\right)^{n}}\text{.}\)

5.

Penyelesaian.
Akar karakteristik untuk kedua barisan adalah \(4\) dan \(-3\) (karena kedua barisan memiliki relasi rekurensi yang sama, akar karakteristiknya juga sama). Dengan menentukan koefisien untuk masing-masing barisan, diperoleh rumus tertutupnya. Kita memperoleh \(a_n = {4^{n}+\left(-3\right)^{n}}\) dan \(b_n = {\left({\frac{25}{7}}\right)\cdot 4^{n}+\left({\frac{10}{7}}\right)\mathopen{}\left(-3\right)^{n}}\text{.}\)

6.

Penyelesaian.
Dengan teknik akar karakteristik, diperoleh \(a_n = {\left({\frac{18}{5}}\right)\cdot 3^{n}-\left({\frac{13}{5}}\right)\mathopen{}\left(-2\right)^{n}}\text{.}\)

Latihan Tambahan

1.

Penyelesaian.
171 dan 341. \(a_n = a_{n-1} + 2a_{n-2}\) dengan \(a_0 = 3\) dan \(a_1 = 5\text{.}\) Rumus tertutupnya adalah \(a_n = \frac{8}{3}2^n + \frac{1}{3}(-1)^n\text{.}\) Untuk menemukannya, selesaikan persamaan karakteristik \(x^2 - x - 2 = 0\) sehingga diperoleh akar karakteristik \(x = 2\) dan \(x=-1\text{.}\) Kemudian, selesaikan sistem
\begin{align*} 3 \amp = a + b\\ 5 \amp = 2a - b \end{align*}

3.

Penyelesaian.
Kita menyatakan bahwa \(a_n = 4^n\) memenuhi relasi tersebut. Substitusikan rumus itu: \(4^n = 3(4^{n-1}) + 4(4^{n-2})\text{.}\) Persamaan ini benar; cukup sederhanakan ruas kanannya.

6.

Penyelesaian.
  1. \(a_n = 4a_{n-1} + 5a_{n-2}\text{.}\)
  2. 4, 21, 104, 521, 2604, 13021
  3. \(a_n = \frac{5}{6} 5^n + \frac{1}{6}(-1)^n \text{.}\)

8.

Penyelesaian.
Polinomial karakteristiknya adalah \(x^2 - 2x + 1\text{,}\) yang memiliki \(x = 1\) sebagai satu-satunya akar; akar tersebut merupakan akar berulang. Jadi, dengan menggunakan teknik akar karakteristik untuk akar berulang, penyelesaian umumnya adalah \(a_n = a + bn\text{,}\) dengan \(a\) dan \(b\) bergantung pada syarat awal.
  1. \(a_n = 1 + n\text{.}\)
  2. Sebagai contoh, kita dapat memilih \(a_0 = 21\) dan \(a_1 = 22\text{.}\)
  3. Untuk setiap \(x\text{.}\) Ambil \(a_0 = x-9\) dan \(a_1 = x-8\text{.}\)

4.5 Pembuktian dengan Induksi
Latihan Tambahan

1.

Penyelesaian.
  1. Jika jumlah biji kita berakhiran 5 lalu jumlah itu digandakan, kita akan memperoleh jumlah biji yang berakhiran 0 (karena \(5\cdot 2 = 10\) ). Jika kemudian kita mengurangkan 5, kita kembali memperoleh jumlah biji yang berakhiran 5. Jadi, jika pada suatu hari jumlahnya berakhiran 5, pada hari berikutnya jumlahnya juga akan berakhiran 5.
  2. Jika Anda tidak memulai dengan jumlah biji yang berakhiran 5 (pada hari pertama), penalaran di atas tetap benar tetapi tidak membantu. Sebagai contoh, jika Anda mulai dengan jumlah yang berakhiran 3, pada hari berikutnya jumlahnya akan berakhiran 1.
  3. Bagian (b) adalah kasus dasar, dan bagian (a) adalah langkah induksi. Jika pada hari pertama jumlah kita berakhiran 5 (berdasarkan bagian (b)), maka pada hari kedua jumlahnya juga akan berakhiran 5 (berdasarkan bagian (a)). Kemudian, dengan kembali menggunakan bagian (a), jumlahnya akan berakhiran 5 pada hari ketiga. Dengan sekali lagi menggunakan bagian (a), jumlahnya juga akan berakhiran 5 pada hari keempat.
    Pembuktian dengan induksi menyatakan bahwa pada setiap hari jumlahnya akan berakhiran 5. Hal ini berlaku karena kita dapat memulai dari kasus dasar, lalu menggunakan langkah induksi berulang kali sampai mencapai \(n\) yang diinginkan.

2.

Penyelesaian.
Bukti.
Kita harus membuktikan bahwa \(1 + 2 + 2^2 + 2^3 + \cdots +2^n = 2^{n+1} - 1\) untuk semua \(n \in \N\text{.}\) Maka, misalkan \(P(n)\) adalah pernyataan \(1 + 2 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\text{.}\) Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\) Pertama, kita membuktikan kasus dasar, \(P(0)\text{,}\) yang menyatakan bahwa \(1 = 2^{0+1} -1\text{.}\) Karena \(2^1 - 1 = 2 - 1 = 1\text{,}\) kita melihat bahwa \(P(0)\) benar. Sekarang untuk langkah induksi. Asumsikan bahwa \(P(k)\) benar untuk suatu \(k \in \N\) sembarang. Artinya, \(1 + 2 + 2^2 + \cdots + 2^k = 2^{k+1} - 1\text{.}\) Kita harus menunjukkan bahwa \(P(k+1)\) benar (yakni bahwa \(1 + 2 + 2^2 + \cdots + 2^{k+1} = 2^{k+2} - 1\)). Untuk melakukannya, kita mulai dari ruas kiri \(P(k+1)\) dan bergerak menuju ruas kanan:
\begin{align*} 1 + 2 + 2^2 + \cdots + 2^k + 2^{k+1} = \amp ~ 2^{k+1} - 1 + 2^{k+1} \amp \text{berdasarkan hipotesis induksi.}\\ = \amp ~2\cdot 2^{k+1} - 1 \amp\\ = \amp ~ 2^{k+2} - 1 \amp \end{align*}
Jadi, \(P(k+1)\) benar, sehingga berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)

3.

Penyelesaian.
Bukti.
Misalkan \(P(n)\) adalah pernyataan, “\(7^n - 1\) merupakan kelipatan 6.” Kita akan menunjukkan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\) Pertama, kita membuktikan kasus dasar, \(P(0)\text{.}\) Karena \(7^0 - 1 = 0\text{,}\) dan \(0\) merupakan kelipatan 6, \(P(0)\) benar. Sekarang untuk langkah induksi. Asumsikan \(P(k)\) berlaku untuk suatu \(k \in \N\) sembarang. Artinya, \(7^k - 1\) merupakan kelipatan 6, atau dengan kata lain, \(7^k - 1 = 6j\) untuk suatu bilangan bulat \(j\text{.}\) Sekarang perhatikan \(7^{k+1} - 1\text{:}\)
\begin{align*} 7^{k+1} - 1 ~ \amp = 7^{k+1} - 7 + 6 \amp \text{dengan trik:} -1 = -7 + 6\\ \amp = 7(7^k - 1) + 6 \amp \text{keluarkan faktor 7 dari dua suku pertama}\\ \amp = 7(6j) + 6 \amp \text{berdasarkan hipotesis induksi}\\ \amp = 6(7j + 1) \amp \text{keluarkan faktor 6} \end{align*}
Oleh karena itu, \(7^{k+1} - 1\) merupakan kelipatan 6, atau dengan kata lain, \(P(k+1)\) benar. Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)

4.

Penyelesaian.
Bukti.
Misalkan \(P(n)\) adalah pernyataan \(1+3 +5 + \cdots + (2n-1) = n^2\text{.}\) Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \ge 1\text{.}\) Pertama, kasus dasar \(P(1)\text{.}\) Kita memiliki \(1 = 1^2\text{,}\) yang benar, sehingga \(P(1)\) terbukti. Sekarang untuk langkah induksi. Asumsikan bahwa \(P(k)\) benar untuk suatu \(k \ge 1\) tetap yang sembarang. Artinya, \(1 + 3 + 5 + \cdots + (2k-1) = k^2\text{.}\) Sekarang kita akan membuktikan bahwa \(P(k+1)\) juga benar (yakni bahwa \(1 + 3 + 5 + \cdots + (2k+1) = (k+1)^2\)). Kita mulai dari ruas kiri \(P(k+1)\) dan bergerak menuju ruas kanan:
\begin{align*} 1 + 3 + 5 + \cdots + (2k-1) + (2k+1) ~ \amp = k^2 + (2k+1) \amp \text{berdasarkan hipotesis induksi}\\ \amp = (k+1)^2 \amp \text{dengan memfaktorkan} \end{align*}
Jadi, \(P(k+1)\) berlaku, sehingga berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \ge 1\text{.}\)

5.

Penyelesaian.
Bukti.
Misalkan \(P(n)\) adalah pernyataan \(F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\text{.}\) Kita akan menunjukkan bahwa \(P(n)\) benar untuk semua \(n \ge 0\text{.}\) Kasus dasarnya mudah karena \(F_0 = 0\) dan \(F_1 = 1\text{,}\) sehingga \(F_0 = F_1 - 1\text{.}\) Sekarang perhatikan langkah induksi. Asumsikan \(P(k)\) benar; artinya, asumsikan \(F_0 + F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\text{.}\) Untuk membuktikan \(P(k+1)\text{,}\) kita bergerak dari kiri ke kanan:
\begin{align*} F_0 + F_2 + \cdots + F_{2k} + F_{2k+2} ~ \amp = F_{2k+1} - 1 + F_{2k+2} \amp \text{berdasarkan hipotesis induksi.}\\ \amp = F_{2k+1} + F_{2k+2} - 1 \amp\\ \amp = F_{2k+3} - 1 \amp \text{berdasarkan definisi rekursif.} \end{align*}
Oleh karena itu, \(F_0 + F_2 + F_4 + \cdots + F_{2k+2} = F_{2k+3} - 1\text{,}\) yang berarti \(P(k+1)\) berlaku. Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \ge 0\text{.}\)

6.

Penyelesaian.
Bukti.
Misalkan \(P(n)\) adalah pernyataan \(2^n \lt n!\text{.}\) Kita akan menunjukkan bahwa \(P(n)\) benar untuk semua \(n \ge 4\text{.}\) Pertama, kita memeriksa kasus dasar dan melihat bahwa \(2^4 \lt 4!\) (karena \(16 \lt 24\)), sehingga \(P(4)\) benar. Sekarang untuk langkah induksi. Asumsikan \(P(k)\) benar untuk suatu \(k \ge 4\) sembarang. Artinya, \(2^k \lt k!\text{.}\) Sekarang perhatikan \(P(k+1)\text{:}\) \(2^{k+1} \lt (k+1)!\text{.}\) Untuk membuktikannya, kita mulai dari ruas kiri dan bergerak menuju ruas kanan.
\begin{align*} 2^{k+1}~ \amp = 2\cdot 2^k \amp\\ \amp \lt 2\cdot k! \amp \text{berdasarkan hipotesis induksi}\\ \amp \lt (k+1) \cdot k! \amp \text{ karena } k+1 \gt 2\\ \amp = (k+1)! \amp \end{align*}
Oleh karena itu, \(2^{k+1} \lt (k+1)!\text{,}\) sehingga kita telah membuktikan \(P(k+1)\text{.}\) Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \ge 4\text{.}\)

12.

Penyelesaian.
Masalahnya adalah kita tidak pernah membuktikan kasus dasar. Tentu saja, ketika \(n = 0\text{,}\) berlaku \(0+3 \ne 0+7\text{.}\)

13.

Penyelesaian.
Bukti.
Misalkan \(P(n)\) adalah pernyataan bahwa \(n + 3 \lt n + 7\text{.}\) Kita akan membuktikan bahwa \(P(n)\) benar untuk semua \(n \in \N\text{.}\) Pertama, perhatikan bahwa kasus dasar berlaku: \(0+3 \lt 0+7\text{.}\) Sekarang, untuk langkah induksi, asumsikan bahwa \(P(k)\) benar. Artinya, \(k+3 \lt k+7\text{.}\) Kita harus menunjukkan bahwa \(P(k+1)\) benar. Karena \(k + 3 \lt k + 7\text{,}\) tambahkan 1 pada kedua ruas. Ini menghasilkan \(k + 3 + 1 \lt k + 7 + 1\text{.}\) Dengan mengelompokkan kembali, diperoleh \((k+1) + 3 \lt (k+1) + 7\text{.}\) Namun, ini tepat merupakan \(P(k+1)\text{.}\) Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \in \N\text{.}\)

14.

Penyelesaian.
Masalahnya adalah meskipun \(P(0)\) benar, dan meskipun \(P(k) \imp P(k+1)\) berlaku untuk beberapa nilai \(k\text{,}\) terdapat setidaknya satu nilai \(k\) (yaitu \(k = 99\)) yang membuat implikasi tersebut gagal. Agar pembuktian dengan induksi sah, \(P(k) \imp P(k+1)\) harus benar untuk semua nilai \(k\) yang lebih besar daripada atau sama dengan nilai pada kasus dasar.

16.

Penyelesaian.
Sekali lagi, kita gagal membuktikan kasus dasar: ketika \(n = 0\text{,}\) berlaku \(n^2 + n = 0\text{,}\) yang genap, bukan ganjil.

22.

Penyelesaian.
Gagasannya adalah bahwa jika kita mengambil logaritma dari \(a^n\text{,}\) kita dapat menaikkan \(n\) sebesar 1 dengan mengalikan satu faktor \(a\) lagi (di dalam logaritma). Akibatnya, satu \(\log(a)\) lagi ditambahkan pada jumlah tersebut.
Bukti.
Tetapkan sembarang bilangan real positif \(a\text{.}\) Misalkan \(P(n)\) adalah pernyataan \(\log(a^n) = n \log(a)\text{.}\) Kasus dasar, \(P(2)\text{,}\) benar karena \(\log(a^2) = \log(a\cdot a) = \log(a) + \log(a) = 2\log(a)\text{,}\) berdasarkan aturan hasil kali logaritma. Sekarang, untuk langkah induksi, asumsikan bahwa \(P(k)\) benar. Artinya, \(\log(a^k) = k\log(a)\text{.}\) Perhatikan \(\log(a^{k+1})\text{.}\) Kita memperoleh
\begin{equation*} \log(a^{k+1}) = \log(a^k\cdot a) = \log(a^k) + \log(a) = k\log(a) + \log(a)\text{,} \end{equation*}
dengan kesamaan terakhir diperoleh dari hipotesis induksi. Bentuk ini menyederhana menjadi \((k+1) \log(a)\text{,}\) sehingga membuktikan \(P(k+1)\text{.}\) Jadi, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk semua \(n \ge 2\text{.}\)

4.6 Induksi Kuat
Latihan Tambahan

3.

Penyelesaian.
Pembuktian akan dilakukan dengan induksi kuat.
Bukti.
Misalkan \(P(n)\) adalah pernyataan, “\(n\) merupakan pangkat dari 2 atau dapat ditulis sebagai jumlah beberapa pangkat dari 2 yang saling berbeda.” Kita akan menunjukkan bahwa \(P(n)\) benar untuk semua \(n \ge 1\text{.}\)
Kasus dasar: \(1 = 2^0\) merupakan pangkat dari 2, sehingga \(P(1)\) benar.
Langkah induksi: Misalkan \(P(k)\) benar untuk semua \(k \lt n\text{.}\) Jika \(n\) merupakan pangkat dari 2, kita selesai. Jika tidak, misalkan \(2^x\) adalah pangkat terbesar dari 2 yang benar-benar lebih kecil daripada \(n\text{.}\) Perhatikan \(n - 2^x\text{,}\) yang merupakan bilangan lebih kecil, bahkan lebih kecil daripada \(n\) maupun \(2^x\text{.}\) Jadi, \(n-2^x\) merupakan pangkat dari 2 atau dapat ditulis sebagai jumlah beberapa pangkat dari 2 yang saling berbeda, tetapi tidak satu pun dari pangkat-pangkat itu merupakan \(2^x\text{.}\) Dengan demikian, setelah menyertakan \(2^x\text{,}\) kita telah menulis \(n\) sebagai jumlah beberapa pangkat dari 2 yang saling berbeda.
Oleh karena itu, berdasarkan prinsip induksi matematika (kuat), \(P(n)\) benar untuk semua \(n \ge 1\text{.}\)

4.7 Ringkasan Bab

Tinjauan Bab

4.7.1.
Penyelesaian.
Barisan tersebut memuat 128+1 suku, sehingga jumlahnya adalah \(\frac{1028\cdot (128+1)}{2} = {66306}\text{.}\)
4.7.2.
Penyelesaian.
  1. Ada \({n-3+1}\) suku.
  2. \(\displaystyle {4n+\left(-3\right)}\text{.}\)
  3. \(\displaystyle \frac{(4n+14)*({n-3+1})}{2}\text{.}\)
4.7.3.
Penyelesaian.
  1. \(3, 15, 75, 375, \ldots\) Barisan tersebut merupakan barisan geometri.
  2. \(\displaystyle \frac{3\cdot5^{21}-3}{4}={3.57628\times 10^{14}}\text{.}\)
4.7.5.
Penyelesaian.
\(a_n = {n^{2}-n+3}\text{.}\) Kita mengetahui bahwa polinom yang dicari berderajat dua karena selisih keduanya konstan. Jadi, \(a_n = an^2 + bn + c\text{.}\) Dengan bekerja mundur, kita memperoleh \(a_0 = {3}\text{,}\) sehingga \(c= {3}\text{.}\) Selanjutnya, selesaikan sistem
\begin{equation*} \begin{aligned} {3} \amp = a + b + {3}\\ {5} \amp = 4a + 2b + {3} \end{aligned} \end{equation*}
untuk memperoleh \(a = {1}\) dan \(b = {-1}\text{.}\)
4.7.6.
Penyelesaian.
  1. Barisan jumlah parsial merupakan polinom berderajat 4 (barisan bedanya adalah barisan semula).
  2. Barisan beda kedua merupakan polinom berderajat 1 (sebuah barisan aritmetika).
4.7.7.
Penyelesaian.
  1. \(4, 6, 10, 16, 26, 42, \ldots\text{.}\)
  2. Tidak. Mengambil beda menghasilkan kembali barisan semula, sehingga bedanya tidak akan pernah tetap.
4.7.8.
Penyelesaian.
\(b_n = (n+3)n\text{.}\)
4.7.10.
Penyelesaian.
Barisannya adalah \(3, 6, {12}, {24}, {48}, \ldots\text{.}\) Dengan teknik akar karakteristik, diperoleh rumus tertutup \(a_n = {3\cdot 2^{n}}\text{.}\)
4.7.11.
Penyelesaian.
Barisan tersebut adalah \(5, 9, {39}, {93}, {327}, \ldots\text{.}\) Dengan teknik akar karakteristik, diperoleh rumus tertutup \(a_n = {\left({\frac{19}{5}}\right)\cdot 3^{n}+\left({\frac{6}{5}}\right)\mathopen{}\left(-2\right)^{n}}\text{.}\)
4.7.12.
Penyelesaian.
  1. Pada hari pertama, 2 kelinci mini Anda menjadi 2 kelinci besar. Pada hari ke-2, 2 kelinci besar tersebut menghasilkan 4 kelinci mini. Pada hari ke-3, Anda memiliki 4 kelinci mini (yang dihasilkan oleh 2 kelinci besar Anda) ditambah 6 kelinci besar (2 kelinci semula ditambah 4 kelinci yang baru tumbuh dewasa). Pada hari ke-4, Anda memiliki \(12\) kelinci mini (masing-masing 2 dari keenam kelinci besar) ditambah 10 kelinci besar (6 kelinci sebelumnya ditambah 4 kelinci yang baru tumbuh dewasa). Barisan jumlah seluruh kelinci adalah \(2, 2, 6, 10, 22, 42\ldots\text{,}\) dimulai dengan \(a_0 = 2\) dan \(a_1 = 2\text{.}\)
  2. \(a_n = a_{n-1} + 2a_{n-2}\text{.}\) Hal ini berlaku karena jumlah kelinci sama dengan jumlah kelinci yang Anda miliki pada hari sebelumnya (baik mini maupun besar) ditambah 2 kali jumlah kelinci yang Anda miliki dua hari sebelumnya (karena semua kelinci yang Anda miliki 2 hari lalu kini sudah besar dan masing-masing menghasilkan 2 kelinci baru).
  3. Dengan menggunakan teknik akar karakteristik, kita memperoleh \(a_n = a\mathbin{\cdot}2^n + b(-1)^n\text{,}\) lalu menentukan \(a\) dan \(b\) sehingga diperoleh \(a_n = \frac{4}{3}2^n + \frac{2}{3}(-1)^n\text{.}\)
4.7.17.
Penyelesaian.
Misalkan \(P(n)\) adalah pernyataan, “Setiap himpunan yang memuat \(n\) anggota memiliki \(2^n\) himpunan bagian yang berbeda.” Kita akan menunjukkan bahwa \(P(n)\) benar untuk setiap \(n \ge 1\text{.}\) Kasus dasar: Setiap himpunan dengan 1 anggota, misalnya \(\{a\}\text{,}\) memiliki tepat 2 himpunan bagian: himpunan kosong dan himpunan itu sendiri. Jadi, banyaknya himpunan bagian adalah \(2= 2^1\text{.}\) Dengan demikian, \(P(1)\) benar. Kasus induksi: Misalkan \(P(k)\) benar untuk suatu \(k \ge 1\) sembarang. Jadi, setiap himpunan yang memuat tepat \(k\) anggota memiliki \(2^k\) himpunan bagian yang berbeda. Sekarang perhatikan suatu himpunan yang memuat \(k+1\) anggota: \(A = \{a_1, a_2, \ldots, a_k, a_{k+1}\}\text{.}\) Setiap himpunan bagian dari \(A\) harus memuat \(a_{k+1}\) atau tidak memuatnya. Dengan kata lain, setiap himpunan bagian dari \(A\) adalah suatu himpunan bagian dari \(\{a_1, a_2,\ldots, a_k\}\text{,}\) dengan atau tanpa \(a_{k+1}\text{.}\) Jadi, terdapat \(2^k\) himpunan bagian dari \(A\) yang memuat \(a_{k+1}\) dan \(2^k\) himpunan bagian lain dari \(A\) yang tidak memuat \(a_{k+1}\text{.}\) Jumlah keseluruhannya adalah \(2^k + 2^k = 2\cdot 2^k = 2^{k+1}\) himpunan bagian dari \(A\text{.}\) Karena pilihan \(A\) sembarang, argumen ini berlaku bagi setiap himpunan yang memuat \(k+1\) anggota, sehingga \(P(k+1)\) benar. Oleh karena itu, berdasarkan prinsip induksi matematika, \(P(n)\) benar untuk setiap \(n \ge 1\text{.}\)

5 Meninjau Kembali Struktur Diskret
5.1 Himpunan
Latihan

1.

Penyelesaian.
  1. \(A \cup B = {\left\{5,7,8,9,10,11,15,20\right\}}\text{.}\) Himpunan ini memuat semua anggota yang berada di \(A\) atau \(B\) atau keduanya.
  2. \(A \cap B = {\left\{5,10\right\}}\text{.}\) Himpunan ini memuat semua anggota yang berada di \(A\) sekaligus \(B\text{.}\)
  3. \(A \setminus B = {\left\{7,8,9\right\}}\text{.}\) Himpunan ini memuat semua anggota \(A\) kecuali anggota yang juga berada di \(B\text{.}\) Himpunan tersebut juga dapat ditulis sebagai \(A \cap \bar{B}\text{.}\)
  4. \(B \setminus A = {\left\{11,15,20\right\}}\text{.}\) Himpunan ini memuat semua anggota \(B\) kecuali anggota yang juga berada di \(A\text{.}\) Bentuk lain penulisannya adalah \(B \cap \bar{A}\text{.}\) Perhatikan bahwa \(A \setminus B \ne B \setminus A\text{.}\)

2.

Penyelesaian.
  1. Himpunan ini adalah \(\{4, 5, 6, \ldots\}\) karena setiap elemennya harus berupa bilangan asli yang kuadratnya sekurang-kurangnya 5 lebih besar daripada 5. Karena \(4^2 - 5 = 11\text{,}\) sedangkan \(3^2 - 5 = 4\text{,}\) bilangan asli pertama yang memenuhi syarat tersebut adalah 4.
  2. Kita memperoleh himpunan yang sama seperti pada bagian sebelumnya, dan bilangan taknegatif terkecil yang membuat \(n^2 - 10\) menjadi bilangan asli adalah 4.
    Perhatikan bahwa jika kita tidak menetapkan \(n \ge 0\) melalui syarat \(n \in \mathbb N\text{,}\) maka setiap bilangan bulat yang lebih kecil daripada \(-4\) juga akan berada dalam himpunan tersebut, sehingga tidak akan ada elemen terkecil.
  3. Himpunan ini adalah \(\{3, 4, 7, 12, \ldots\}\text{,}\) yaitu himpunan bilangan yang menjadi hasil dari menguadratkan suatu bilangan asli lalu menambahkan 3. (\(0^2 + 3 = 3\text{,}\) \(1^2 + 3 = 4\text{,}\) \(2^2 + 3 = 7\text{,}\) dan seterusnya.) Jadi, elemen terkecil himpunan tersebut adalah 3.
  4. Sekarang kita mencari bilangan asli yang diperoleh dengan mengambil suatu bilangan asli, menguadratkannya, lalu menambahkan 3. Himpunannya adalah \(\{3, 4, 7, 12, \ldots\}\text{,}\) sama seperti pada bagian sebelumnya. Jadi, sekali lagi, elemen terkecilnya adalah 3.

4.

Penyelesaian.
Himpunan berukuran terbesar yang merupakan himpunan bagian dari \(A \text{ dan } B\) adalah irisan \(A \text{ dan } B \text{,}\) yaitu \(A \cap B = {\left\{2,4,5,6\right\}}\text{.}\)

7.

Penyelesaian.
Terdapat tepat 4 himpunan semacam itu: \({\left\{3,6,14\right\}}\text{,}\) \({\left\{3,6,13,14\right\}}\text{,}\) \({\left\{3,6,11,14\right\}}\text{,}\) dan \({\left\{3,6,11,13,14\right\}}\text{.}\)

8.

Penyelesaian.
  1. \(\displaystyle A \cap B = {\left\{7,8,9\right\}}\text{.}\)
  2. \(\displaystyle A \cup B = {\left\{5,6,7,8,9,10,11\right\}}\text{.}\)
  3. \(\displaystyle A \setminus B ={\left\{5,6\right\}}\text{.}\)
  4. \(\displaystyle A \cap \overline{(B \cup C)} = {\left\{5\right\}}\text{.}\)

11.

Penyelesaian.
Sebagai contoh, \(A = \{2,3,5,7,8\}\) dan \(B = \{3,5\}\) .

12.

Penyelesaian.
Sebagai contoh, \(A = \{1,2,3\}\) dan \(B = \{1,2,3,4,5,\{1,2,3\}\}\)

13.

Penyelesaian.
  1. Tidak.
  2. Tidak.
  3. \(2\Z \cap 3\Z\) adalah himpunan semua bilangan bulat yang merupakan kelipatan 2 sekaligus 3 (jadi, kelipatan 6). Oleh karena itu, \(2\Z \cap 3\Z = \{x \in \Z \st \exists y\in \Z(x = 6y)\}\text{.}\)
  4. \(2\Z \cup 3\Z\text{.}\)

15.

Penyelesaian.
  1. \(A \cup \bar B\text{:}\)
    Diagram Venn dua himpunan, A dan B. Setiap daerah diarsir kecuali daerah yang hanya berada di dalam B.
  2. \(\bar{(A \cup B)}\text{:}\)
    Diagram Venn dua himpunan, A dan B. Satu-satunya daerah yang diarsir adalah daerah di luar kedua lingkaran.
  3. \(A \cap (B \cup C)\text{:}\)
    Diagram Venn tiga himpunan, A, B, dan C. Tiga dari delapan daerah diarsir: daerah tengah yang dimiliki bersama oleh semua himpunan, daerah yang dimiliki bersama oleh A dan B, serta daerah yang dimiliki bersama oleh A dan C.
  4. \((A \cap B) \cup C\text{:}\)
    Diagram Venn tiga himpunan, A, B, dan C. Seluruh C diarsir, demikian pula daerah yang dimiliki bersama oleh A dan B.
  5. \(\bar A \cap B \cap \bar C\text{:}\)
    Diagram Venn tiga himpunan, A, B, dan C. Satu-satunya daerah yang diarsir adalah daerah yang hanya berada di dalam B.
  6. \((A \cup B) \setminus C\text{:}\)
    Diagram Venn tiga himpunan, A, B, dan C. Daerah yang diarsir adalah daerah yang hanya berada di dalam A, daerah yang hanya berada di dalam B, dan daerah yang berada di dalam A dan B (tetapi di luar C).

17.

Penyelesaian.
\begin{align*} \pow(A) = \{\amp \emptyset, \{a\}, \{b\}, \{c\}, \{d\}, \{a,b\}, \{a,c\}, \{a,d\}, \{b,c\}, \{b,d\},\\ \amp \{c,d\}, \{a,b,c\}, \{a,b,d\}, \{a,c,d\}, \{b,c,d\}, \{a,b,c,d\}\}\text{.} \end{align*}

18.

Penyelesaian.
Masing-masing dari 13 anggota dapat membentuk sebuah himpunan tunggal, sehingga terdapat 13 himpunan bagian semacam itu.
Untuk menghitung himpunan bagian beranggota dua, perhatikan bahwa terdapat 12 himpunan yang memuat 1, kemudian 11 himpunan yang memuat 2 tetapi tidak memuat 1, kemudian 10 himpunan yang memuat 3 tetapi tidak memuat 1 atau 2, dan seterusnya. Jadi, 78 dapat diperoleh dengan menjumlahkan bilangan dari 1 sampai 12.

20.

Penyelesaian.
Sebagai contoh, \(A = \{1,2,3,4\}\) dan \(B = \{5,6,7,8,9\}\) menghasilkan \(A \cup B = \{1,2,3,4,5,6,7,8,9\}\text{.}\)

28.

Penyelesaian.
Di sini kita perlu sedikit berhati-hati. Jika \(B\) memuat 3 elemen, maka \(A\) hanya memuat bilangan 3 (yang dituliskan dua kali). Dengan demikian, \(|A| = 1\text{,}\) sehingga \(B = \{1, 3\}\text{,}\) yang hanya memiliki 2 elemen. Jadi, \(|B| \ne 3\text{.}\) Ini berarti bahwa \(|A| = 2\text{,}\) sehingga \(B\) setidaknya memuat elemen 1 dan 2. Karena \(\card{B} \ne 3\text{,}\) harus berlaku \(\card{B} = 2\text{,}\) yang sesuai dengan definisi \(B\text{.}\)
Oleh karena itu, harus berlaku \(A = \{2,3\}\) dan \(B = \{1, 2\}\text{.}\)

5.2 Fungsi
Latihan

1.

Penyelesaian.
  1. \(f(5) = 2\text{,}\) karena 2 adalah bilangan yang terletak di bawah 5 dalam notasi dua baris.
  2. Salah satu \(n\) yang memenuhi adalah \(n= 1\text{,}\) karena \(f(1) = 5\text{.}\) Perhatikan bahwa 1 terletak di atas 5 dalam notasi tersebut.
  3. \(n = 3\) memenuhi sifat tersebut. Kita menyebut 3 sebagai titik tetap dari \(f\text{.}\) Tidak semua fungsi memiliki titik semacam itu.
  4. Anggota tersebut adalah 1 (bahkan, inilah satu-satunya anggota kodomain yang tidak berada dalam daerah hasil). Dengan kata lain, 1 bukan citra dari anggota mana pun di bawah \(f\text{;}\) tidak ada anggota yang dipetakan ke 1.

5.

Penyelesaian.
Terdapat 16 fungsi berbeda. Tidak satu pun fungsi tersebut injektif. Tepat 14 fungsi bersifat surjektif (ada 2 yang tidak surjektif, yaitu fungsi yang memetakan semua anggota ke \(a\) atau semuanya ke \(b\)). Tidak ada fungsi yang bijektif karena tidak ada fungsi injektif dalam soal ini.

6.

Penyelesaian.
Terdapat 16 fungsi: tersedia empat pilihan keluaran bagi \(f(1)\text{,}\) dan untuk setiap pilihan tersebut tersedia empat pilihan keluaran bagi \(f(2)\text{.}\) Dari fungsi-fungsi ini, 12 bersifat injektif, 0 bersifat surjektif, dan 0 memiliki kedua sifat tersebut (yaitu, bijektif):
\begin{equation*} f = \twoline{1 \amp 2}{a\amp a} \quad f = \twoline{1 \amp 2}{b \amp b} \quad f = \twoline{1 \amp 2}{c \amp c} \quad f = \twoline{1 \amp 2}{d \amp d} \end{equation*}
\begin{equation*} f = \twoline{1 \amp 2}{a\amp b} \quad f = \twoline{1 \amp 2}{a \amp c} \quad f = \twoline{1 \amp 2}{a \amp d} \quad f = \twoline{1 \amp 2}{b \amp c} \end{equation*}
\begin{equation*} f = \twoline{1 \amp 2}{b \amp a} \quad f = \twoline{1 \amp 2}{c \amp a} \quad f = \twoline{1 \amp 2}{d \amp a} \quad f = \twoline{1 \amp 2}{c \amp b} \end{equation*}
\begin{equation*} f = \twoline{1 \amp 2}{b \amp d} \quad f = \twoline{1 \amp 2}{d \amp b} \quad f = \twoline{1 \amp 2}{c \amp d} \quad f = \twoline{1 \amp 2}{d \amp c} \end{equation*}

7.

Penyelesaian.
  1. \(f\) tidak injektif karena \(f(2) = f(5)\text{;}\) dua masukan yang berbeda memiliki keluaran yang sama.
  2. \(f\) surjektif karena setiap elemen kodomain termasuk dalam daerah hasil.
  3. \(f=\begin{pmatrix}1 \amp 2 \amp 3 \amp 4 \amp 5 \\ 3 \amp 2 \amp 4 \amp 1 \amp 2\end{pmatrix}\text{.}\)

12.

Penyelesaian.
  1. \(f\) injektif, tetapi tidak surjektif (misalnya, 0 tidak pernah menjadi keluaran).
  2. \(f\) injektif dan surjektif. Berbeda dengan pertanyaan sebelumnya, setiap bilangan bulat merupakan keluaran (dari bilangan bulat yang nilainya 4 lebih kecil).
  3. \(f\) injektif, tetapi tidak surjektif (misalnya, 10 bukan 8 kurang dari suatu kelipatan 5).
  4. \(f\) tidak injektif, tetapi surjektif. Setiap bilangan bulat merupakan keluaran (misalnya, dari dua kali bilangan itu sendiri), tetapi beberapa bilangan bulat merupakan keluaran dari lebih dari satu masukan: \(f(5) = 3 = f(6)\text{.}\)

13.

Penyelesaian.
  1. \(f\) tidak injektif. Untuk membuktikannya, kita cukup mencari dua elemen berbeda dalam domain yang dipetakan ke elemen kodomain yang sama. Karena \(f(\{1\}) = 1\) dan \(f(\{2\}) = 1\text{,}\) kita melihat bahwa \(f\) tidak injektif.
  2. \(f\) tidak surjektif. Himpunan bagian terbesar dari \(A\) adalah \(A\) itu sendiri, dan \(|A| = 10\text{.}\) Jadi, tidak ada bilangan asli yang lebih besar dari 10 yang dapat menjadi keluaran.
  3. \(f\inv(1) = \{\{1\}, \{2\}, \{3\}, \ldots, \{10\}\}\) (himpunan semua himpunan bagian beranggota tunggal dari \(A\) ).
  4. \(f\inv(0) = \{\emptyset\}\text{.}\) Perhatikan bahwa menulis \(f\inv(0) = \emptyset\) merupakan kekeliruan; bentuk itu akan menyatakan bahwa tidak ada masukan yang memiliki 0 sebagai keluaran.
  5. \(f\inv(12) = \emptyset\) karena tidak ada himpunan bagian dari \(A\) yang berkardinalitas 12.

16.

Penyelesaian.
  1. \(|f\inv(3)| \le 1\text{.}\) Dengan kata lain, \(f\inv(3)\) merupakan himpunan kosong atau himpunan yang memuat tepat satu elemen. Fungsi injektif tidak mungkin memiliki dua elemen domain yang keduanya dipetakan ke 3.
  2. \(|f\inv(3)| \ge 1\text{.}\) Dengan kata lain, \(f\inv(3)\) merupakan himpunan yang memuat paling sedikit satu elemen, mungkin lebih. Pada fungsi surjektif, harus ada sesuatu yang dipetakan ke 3.
  3. \(|f\inv(3)| = 1\text{.}\) Terdapat tepat satu elemen \(X\) yang dipetakan ke 3, sehingga \(f\inv(3)\) merupakan himpunan yang memuat satu elemen tersebut.

17.

Penyelesaian.
\(X\) sebenarnya dapat berupa sembarang himpunan, asalkan \(f(x) = 0\) atau \(f(x) = 1\) untuk setiap \(x \in X\text{.}\) Sebagai contoh, \(X = \N\) dan \(f(n) = 0\) memenuhi syarat.

21.

Penyelesaian.
  1. \(f\) injektif.
    Bukti.
    Misalkan \(x\) dan \(y\) merupakan elemen domain \(\Z\text{.}\) Asumsikan \(f(x) = f(y)\text{.}\) Jika \(x\) dan \(y\) keduanya genap, maka \(f(x) = x+1\) dan \(f(y) = y+1\text{.}\) Karena \(f(x) = f(y)\text{,}\) kita memperoleh \(x + 1 = y + 1\text{,}\) yang mengakibatkan \(x = y\text{.}\) Demikian pula, jika \(x\) dan \(y\) keduanya ganjil, maka \(x - 3 = y-3\text{,}\) sehingga sekali lagi \(x = y\text{.}\) Satu-satunya kemungkinan lain adalah \(x\) genap dan \(y\) ganjil (atau sebaliknya). Namun, dalam hal itu \(x + 1\) akan ganjil, sedangkan \(y - 3\) akan genap, sehingga tidak mungkin \(f(x) = f(y)\text{.}\) Oleh karena itu, jika \(f(x) = f(y)\text{,}\) kita memperoleh \(x = y\text{,}\) yang membuktikan bahwa \(f\) injektif.
  2. \(f\) surjektif.
    Bukti.
    Misalkan \(y\) adalah elemen kodomain \(\Z\text{.}\) Kita akan menunjukkan bahwa terdapat elemen \(n\) dalam domain (\(\Z\)) sedemikian sehingga \(f(n) = y\text{.}\) Ada dua kasus. Pertama, jika \(y\) genap, misalkan \(n = y+3\text{.}\) Karena \(y\) genap, \(n\) ganjil, sehingga \(f(n) = n-3 = y+3-3 = y\) seperti yang diinginkan. Kedua, jika \(y\) ganjil, misalkan \(n = y-1\text{.}\) Karena \(y\) ganjil, \(n\) genap, sehingga \(f(n) = n+1 = y-1+1 = y\) seperti yang diperlukan. Oleh karena itu, \(f\) surjektif.

22.

Penyelesaian.
Ya, hal ini merupakan fungsi jika domain dan kodomain dipilih dengan tepat. Domainnya adalah himpunan mahasiswa, sedangkan kodomainnya adalah himpunan nilai yang mungkin. Fungsi tersebut hampir pasti tidak injektif karena kemungkinan ada dua mahasiswa yang memperoleh nilai yang sama. Fungsi tersebut mungkin surjektif – sifat ini terpenuhi jika untuk setiap nilai terdapat sedikitnya satu mahasiswa yang memperolehnya.

24.

Penyelesaian.
Pembagian ini bukan fungsi.

25.

Penyelesaian.
Definisi rekursifnya adalah \(f(0) = 0;~ f(n+1) = f(n) + n\text{.}\)

26.

Penyelesaian.
Secara umum, \(\card{A} \ge \card{f(A)}\) karena banyaknya keluaran tidak mungkin melebihi banyaknya masukan (setiap masukan menuju tepat satu keluaran), tetapi banyaknya keluaran dapat lebih sedikit jika fungsi tersebut tidak injektif. Jika fungsi tersebut injektif, maka \(\card{A} = \card{f(A)}\text{,}\) meskipun kesamaan dapat terjadi bahkan jika \(f\) tidak injektif (fungsi tersebut harus injektif ketika dibatasi pada \(A\)). Surjektivitas \(f\) saja tidak memberikan hubungan tambahan untuk \(A\) sembarang. Jika \(f\) bijektif, maka \(\card{A} = \card{f(A)}\text{.}\)

27.

Penyelesaian.
Secara umum, tidak ada hubungan antara \(\card{B}\) dan \(\card{f\inv(B)}\text{.}\) Hal ini karena \(B\) mungkin memuat elemen yang tidak termasuk dalam daerah hasil \(f\text{,}\) sehingga bahkan mungkin \(f\inv(B) = \emptyset\text{.}\) Di sisi lain, mungkin terdapat banyak elemen domain yang semuanya dipetakan ke sedikit elemen dalam \(B\text{,}\) sehingga \(f\inv(B)\) lebih besar daripada \(B\text{.}\)
Lebih khusus lagi, jika \(f\) injektif, maka \(\card{B} \ge \card{f\inv(B)}\) (karena setiap elemen dalam \(B\) berasal dari paling banyak satu elemen domain). Jika \(f\) surjektif, maka \(\card{B} \le \card{f\inv(B)}\) (karena setiap elemen dalam \(B\) harus berasal dari paling sedikit satu elemen domain). Jadi, jika \(f\) bijektif, maka \(\card{B} = \card{f\inv(B)}\text{.}\)

6 Topik Tambahan
6.1 Fungsi Pembangkit
Latihan

1.

Penyelesaian.
  1. \(\dfrac{4}{1-x}\text{.}\)
  2. \(\dfrac{2}{(1-x)^2}\text{.}\)
  3. \(\dfrac{2x^3}{(1-x)^2}\text{.}\)
  4. \(\dfrac{1}{1-5x}\text{.}\)
  5. \(\dfrac{1}{1+3x}\text{.}\)
  6. \(\dfrac{1}{1-5x^2}\text{.}\)
  7. \(\dfrac{x}{(1-x^3)^2}\text{.}\)

2.

Penyelesaian.
  1. \(0, 4, 4, 4, 4, 4, \ldots\text{.}\)
  2. \(1, 4, 16, 64, 256, \ldots\text{.}\)
  3. \(0, 1, -1, 1, -1, 1, -1, \ldots\text{.}\)
  4. \(0, 3, -6, 9, -12, 15, -18, \ldots\text{.}\)
  5. \(1, 3, 6, 9, 12, 15, \ldots\text{.}\)

4.

Penyelesaian.
Nyatakan fungsi pembangkitnya dengan \(A\text{.}\) Hitung \(A - xA = 4 + x + 2x^2 + 3x^3 + 4x^4 + \cdots\text{.}\) Dengan demikian, \(A - xA = 4 + \dfrac{x}{(1-x)^2}\text{.}\) Menyelesaikan persamaan untuk memperoleh \(A\) memberikan \(\d\frac{4}{1-x} + \frac{x}{(1-x)^3}\text{.}\)

5.

Penyelesaian.
\(\dfrac{1+2x}{1-3x + x^2}\text{.}\)

6.

Penyelesaian.
Hitung \(A - xA - x^2A\text{,}\) lalu selesaikan persamaan untuk memperoleh \(A\text{.}\) Fungsi pembangkitnya adalah \(\dfrac{x}{1-x-x^2}\text{.}\)

7.

Penyelesaian.
\(\dfrac{x}{(1-x)(1-x-x^2)}\text{.}\)

8.

Penyelesaian.
\(\dfrac{2}{1-5x} + \dfrac{7}{1+3x}\text{.}\)

9.

Penyelesaian.
\(a_n = \begin{cases}1 & n=0,\\3\cdot 4^{n-1} + 1 & n\ge 1.\end{cases}\)

12.

Penyelesaian.
  1. \(\frac{1}{(1-x^2)^2}\text{.}\)
  2. \(\frac{1}{(1+x)^2}\text{.}\)
  3. \(\frac{3x}{(1-x)^2}\text{.}\)
  4. \(\frac{3x}{(1-x)^3}\text{.}\) (jumlah parsial).

13.

Penyelesaian.
  1. \(0,0,1,1,2,3,5,8, \ldots\text{.}\)
  2. \(1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, \ldots\text{.}\)
  3. \(1, 3, 18, 81, 405, \ldots\text{.}\)
  4. \(1, 2, 4, 7, 12, 20, \ldots\text{.}\)

15.

Penyelesaian.
\(\frac{x^3}{(1-x)^2} + \frac{1}{1-x}\text{.}\)

6.2 Pengantar Teori Bilangan
Latihan

1.

Penyelesaian.
Bukti.
Misalkan \(a \mid b\text{.}\) Maka \(b\) merupakan kelipatan \(a\text{,}\) atau dengan kata lain, \(b = ak\) untuk suatu bilangan bulat \(k\text{.}\) Namun, dengan demikian \(bc = akc\text{,}\) dan karena \(kc\) adalah bilangan bulat, ini menyatakan bahwa \(bc\) merupakan kelipatan \(a\text{.}\) Dengan kata lain, \(a \mid bc\text{.}\)

3.

Penyelesaian.
\(\{\ldots, -8, -4, 0, 4, 8, 12, \ldots\}\text{,}\) \(\{\ldots, -7, -3, 1, 5, 9, 13, \ldots\}\text{,}\)
\(\{\ldots, -6, -2, 2, 6, 10, 14, \ldots\}\text{,}\) dan \(\{\ldots, -5, -1, 3, 7, 11, 15, \ldots\}\text{.}\)

5.

Penyelesaian.
Bukti.
Asumsikan \(a \equiv b \pmod n\) dan \(c \equiv d \pmod n\text{.}\) Ini berarti \(a = b + kn\) dan \(c = d + jn\) untuk suatu bilangan bulat \(k\) dan \(j\text{.}\) Perhatikan \(a-c\text{.}\) Kita peroleh:
\begin{equation*} a-c = b+kn - (d+jn) = b-d + (k-j)n\text{.} \end{equation*}
Dengan kata lain, \(a-c\) sama dengan \(b-d\) ditambah suatu kelipatan \(n\text{,}\) sehingga \(a-c \equiv b-d \pmod n\text{.}\)

6.

Penyelesaian.
  1. \(3^{456} \equiv 1^{456} = 1 \pmod 2\text{.}\)
  2. \(3^{456} = 9^{228} \equiv (-1)^{228} = 1 \pmod{5}\text{.}\)
  3. \(3^{456} = 9^{228} \equiv 2^{228} = 8^{76} \equiv 1^{76} = 1 \pmod 7\text{.}\)
  4. \(3^{456} = 9^{228} \equiv 0^{228} = 0 \pmod{9}\text{.}\)

8.

Penyelesaian.
Untuk setiap kongruensi ini, cukup substitusikan semua bilangan bulat mulai dari 0 hingga satu kurang dari modulusnya untuk melihat mana, jika ada, yang memenuhi.
  1. Tidak ada solusi.
  2. \(x = 2\text{,}\) \(x = 5\text{,}\) \(x = 8\text{.}\)
  3. Tidak ada solusi.

10.

Penyelesaian.
\(x = 5+22k\) untuk \(k \in \Z\text{.}\)

12.

Penyelesaian.
\(x = 6 + 15k\) untuk \(k \in \Z\text{.}\)

14.

Penyelesaian.
Kita harus menyelesaikan \(7x + 5 \equiv 2 \pmod{11}\text{.}\) Ini menghasilkan \(x \equiv 9 \pmod{11}\text{.}\) Secara umum, \(x = 9 + 11k\text{,}\) tetapi jika sembarang \(x\) seperti itu dibagi 11, sisanya akan selalu 9.

15.

Penyelesaian.
Bagi seluruh persamaan dengan 2: \(3x + 5y = 16\text{.}\) Ubah menjadi kongruensi modulo 3: \(5y \equiv 16 \pmod 3\text{,}\) yang tereduksi menjadi \(2y \equiv 1 \pmod 3\text{.}\) Jadi, \(y \equiv 2 \pmod 3\) atau \(y = 2 + 3k\text{.}\) Substitusikan kembali ke \(3x + 5y = 16\text{,}\) lalu selesaikan untuk \(x\text{,}\) sehingga diperoleh \(x = 2-5k\text{.}\) Jadi, solusi umumnya adalah \(x = 2-5k\) dan \(y = 2+3k\) untuk \(k \in \Z\text{.}\)
🔗
SblmTopLnjt
Umpan Balik