Lewati ke konten utama

Latihan 2.9 Latihan

1.

Alfabet Hawaii terdiri atas \(12\) huruf. Berapa banyak string enam karakter yang dapat dibuat menggunakan alfabet Hawaii?

2.

Berapa banyak bilangan bulat positif \(2n\) digit yang dapat dibentuk jika digit pada posisi ganjil (dengan digit paling kanan dihitung sebagai posisi \(1\)) harus ganjil dan digit pada posisi genap harus genap serta positif?

3.

Matt sedang merancang sistem autentikasi situs web. Ia tahu bahwa kata sandi paling aman jika memuat huruf, angka, dan simbol. Namun, ia belum sepenuhnya memahami bahwa keamanan tambahan ini hilang jika ia menentukan posisi kemunculan setiap jenis karakter. Ia memutuskan bahwa kata sandi yang valid untuk sistemnya diawali tiga huruf (huruf besar maupun kecil diperbolehkan), diikuti dua digit, lalu satu dari \(10\) simbol, dua huruf besar, satu digit, dan akhirnya satu dari \(10\) simbol. Berapa banyak kata sandi berbeda yang tersedia dalam sistem situs webnya? Bagaimana jumlah ini dibandingkan dengan banyaknya semua string panjang \(10\) yang dibuat dari alfabet yang terdiri atas semua huruf besar dan kecil bahasa Inggris, digit desimal, serta \(10\) simbol?

4.

Berapa banyak string terner panjang \(2n\) yang angka nolnya hanya muncul pada posisi bernomor ganjil?

5.

Misalkan kita membuat pelat nomor berbentuk \(l_1l_2l_3-d_1d_2d_3\text{,}\) dengan \(l_1,l_2,l_3\) merupakan huruf besar dalam alfabet bahasa Inggris dan \(d_1,d_2,d_3\) merupakan digit desimal (i.e., anggota himpunan \(\{0,1,2,3,4,5,6,7,8,9\}\)), dengan syarat sedikitnya satu digit tidak nol dan sedikitnya satu huruf adalah \(K\text{.}\) Berapa banyak pelat nomor yang dapat kita buat?

6.

Kelas tiga Ibu Steffen terdiri atas \(30\) siswa. Para siswa dibagi menjadi tiga kelompok (bernomor \(1\text{,}\) \(2\text{,}\) dan \(3\)), masing-masing beranggotakan \(10\) siswa.
  1. Para siswa dalam kelompok \(1\) memperoleh tambahan waktu istirahat selama \(10\) menit karena memenangi perlombaan kelas. Sebelum keluar untuk menikmati waktu istirahat tambahan tersebut, mereka berbaris satu-satu. Dalam berapa cara mereka dapat berbaris?
  2. Ketika seluruh \(30\) siswa kembali dari waktu istirahat bersama-sama, mereka kembali berbaris satu-satu. Namun, kali ini para siswa diatur sedemikian rupa sehingga siswa pertama berasal dari kelompok \(1\text{,}\) siswa kedua dari kelompok \(2\text{,}\) siswa ketiga dari kelompok \(3\text{,}\) dan selanjutnya kelompok mereka terus berselang-seling menurut urutan tersebut. Dalam berapa cara mereka dapat berbaris untuk kembali dari waktu istirahat?

7.

Berapa banyak string berbentuk \(l_1l_2d_1d_2d_3l_3l_4d_4l_5l_6\) yang memenuhi ketentuan berikut?
  • untuk \(1\leq i\leq 6\text{,}\) \(l_i\) merupakan huruf besar dalam alfabet bahasa Inggris;
  • untuk \(1\leq i\leq 4\text{,}\) \(d_i\) merupakan digit desimal;
  • \(l_2\) bukan huruf vokal (i.e., \(l_2\nin\{\text{A,E,I,O,U} \}\)); dan
  • digit \(d_1\text{,}\) \(d_2\text{,}\) dan \(d_3\) semuanya berbeda (i.e., \(d_1\neq d_2\neq d_3\neq d_1\)).

8.

Dalam latihan ini, kita mempertimbangkan string yang dibuat dari huruf besar dalam alfabet bahasa Inggris dan digit desimal. Berapa banyak string panjang \(10\) yang dapat dibuat dalam setiap skenario berikut?
  1. Karakter pertama dan terakhir string merupakan huruf.
  2. Karakter pertama merupakan huruf vokal, karakter kedua merupakan huruf konsonan, dan karakter terakhir merupakan digit.
  3. Huruf vokal (tidak harus berbeda) muncul pada posisi ketiga, keenam, dan kedelapan, serta tidak muncul pada posisi lain.
  4. Huruf vokal (tidak harus berbeda) muncul tepat pada dua posisi.
  5. Tepat empat karakter dalam string merupakan digit dan tidak ada digit yang muncul lebih dari sekali.

9.

Sebuah basis data menggunakan string \(20\) karakter sebagai pengenal rekaman. Karakter yang valid dalam string tersebut adalah huruf besar dalam alfabet bahasa Inggris dan digit desimal. (Ingatlah bahwa terdapat \(26\) huruf dalam alfabet bahasa Inggris dan \(10\) digit desimal.) Berapa banyak pengenal rekaman valid yang mungkin jika setiap pengenal rekaman valid harus memenuhi semua kriteria berikut?
  • Huruf dari himpunan \(\{A,E,I,O,U\}\) muncul pada tepat tiga posisi dalam string.
  • Tiga karakter terakhir dalam string merupakan digit desimal yang semuanya berbeda dan tidak muncul di tempat lain dalam string.
  • Posisi karakter yang tersisa boleh diisi dengan sembarang huruf atau digit desimal yang masih tersedia.

10.

Misalkan \(X\) adalah himpunan yang terdiri atas \(26\) huruf kecil bahasa Inggris dan \(10\) digit desimal. Berapa banyak string-\(X\) panjang \(15\) yang memenuhi semua sifat berikut secara bersamaan?
  • Simbol pertama dan terakhir dalam string merupakan digit yang berbeda (dan boleh muncul di tempat lain dalam string).
  • Tepat empat simbol dalam string merupakan huruf ’\(t\)’.
  • Tepat tiga karakter dalam string merupakan anggota himpunan \(V=\{a,e,i,o,u\}\text{,}\) dan ketiga karakter tersebut semuanya berbeda.

11.

Sebuah toko donat menjual 12 jenis donat. Seorang manajer ingin membeli enam donat, masing-masing satu untuk dirinya dan lima orang pegawainya.
  1. Misalkan ia melakukannya dengan memilih jenis donat tertentu untuk setiap orang. (Ia boleh memilih jenis donat yang sama untuk lebih dari satu orang.) Dalam berapa cara ia dapat melakukannya?
  2. Dalam berapa cara ia dapat memilih donat jika ia ingin memastikan bahwa setiap orang memperoleh jenis donat yang berbeda?
  3. Sebagai kemungkinan lain, misalkan ia ingin memilih masing-masing satu donat dari enam jenis yang berbeda dan meletakkannya di ruang istirahat. Dalam berapa cara ia dapat melakukannya? (Urutan donat di dalam kotak tidak diperhitungkan.)

12.

Olahraga korfball dimainkan oleh tim yang terdiri atas delapan pemain. Setiap tim beranggotakan empat pria dan empat wanita. SMA Halliday memiliki tujuh siswa pria dan \(11\) siswa wanita yang berminat bermain korfball. Dalam berapa cara mereka dapat membentuk tim korfball dari 18 siswa yang berminat tersebut?

13.

Dua puluh siswa mengikuti kompetisi pemrograman. Empat siswa terbaik menerima trofi untuk juara pertama, kedua, ketiga, dan keempat.
  1. Berapa banyak hasil berbeda yang mungkin untuk empat peringkat teratas?
  2. Pada saat terakhir, para juri memutuskan untuk memberikan piagam penghargaan kepada empat peserta yang tidak menerima trofi. Dalam berapa cara penerima piagam penghargaan dapat dipilih (setelah empat peringkat teratas ditentukan)? Lalu, berapa banyak hasil keseluruhan yang mungkin (trofi beserta piagam)?

14.

Sebuah kedai es krim menawarkan promosi khusus banana split, dan Xing memanfaatkannya. Ia terkesima melihat begitu banyak pilihan untuk meracik banana split-nya:
  • Ia harus memilih tiga rasa es krim yang berbeda untuk ditempatkan dalam mangkuk asimetris tempat banana split disajikan. Kedai tersebut menyediakan 20 rasa es krim.
  • Setiap sendok es krim harus diberi saus yang dipilih dari enam pilihan berbeda. Xing boleh menggunakan jenis saus yang sama pada lebih dari satu sendok es krim.
  • Tersedia \(10\) macam taburan, dan ia harus memilih tiga di antaranya untuk ditaburkan di seluruh banana split.
  1. Dalam berapa cara berbeda Xing dapat meracik banana split di kedai es krim ini?
  2. Misalkan Xing tidak diwajibkan memilih tepat tiga macam taburan, tetapi diperbolehkan memilih antara nol dan tiga macam taburan. Dalam skenario ini, dalam berapa cara berbeda ia dapat meracik banana split?

15.

Misalkan seorang guru ingin membagikan \(25\) pensil identik kepada Ahmed, Barbara, Casper, dan Dieter, dengan syarat Ahmed dan Dieter masing-masing menerima sedikitnya satu pensil, Casper menerima paling banyak lima pensil, dan Barbara menerima sedikitnya empat pensil. Dalam berapa cara pembagian semacam itu dapat dilakukan?

16.

Berapa banyak solusi bernilai bilangan bulat untuk setiap persamaan dan pertidaksamaan berikut?
  1. \(x_1+x_2+x_3+x_4+x_5=63\text{,}\) semua \(x_i>0\)
  2. \(x_1+x_2+x_3+x_4+x_5=63\text{,}\) semua \(x_i\geq 0\)
  3. \(x_1+x_2+x_3+x_4+x_5\leq 63\text{,}\) semua \(x_i\geq 0\)
  4. \(x_1+x_2+x_3+x_4+x_5=63\text{,}\) semua \(x_i\geq 0\text{,}\) \(x_2\geq 10\)
  5. \(x_1+x_2+x_3+x_4+x_5=63\text{,}\) semua \(x_i\geq 0\text{,}\) \(x_2\leq 9\)

17.

Berapa banyak solusi bilangan bulat untuk persamaan
\begin{equation*} x_1+x_2+x_3+x_4 = 132 \end{equation*}
jika \(x_1>0\) dan \(x_2,x_3,x_4\geq 0\text{?}\) Bagaimana jika kita menambahkan syarat \(x_4\lt 17\text{?}\)

18.

Berapa banyak solusi bilangan bulat untuk pertidaksamaan
\begin{equation*} x_1+x_2+x_3+x_4+x_5\leq 782 \end{equation*}
jika \(x_1,x_2>0\text{,}\) \(x_3\geq 0\text{,}\) dan \(x_4,x_5\geq 10\text{?}\)

19.

Seorang guru memiliki \(450\) butir permen identik. Ia ingin membagikannya kepada kelas yang terdiri atas \(65\) siswa, meskipun ia bersedia membawa pulang sebagian permen yang tersisa. (Namun, ia tidak mengharuskan adanya permen yang dibawa pulang.) Siswa yang memenangi perlombaan pada pertemuan sebelumnya akan menerima sedikitnya \(10\) butir permen sebagai hadiah. Di antara siswa lainnya, \(34\) siswa bersikeras menerima sedikitnya satu butir permen, sedangkan \(30\) siswa yang tersisa bersedia tidak menerima permen sama sekali.

(a)

Dalam berapa cara guru tersebut dapat membagikan permen?

(b)

Dalam berapa cara guru tersebut dapat membagikan permen jika, selain syarat di atas, salah seorang siswanya menderita diabetes dan boleh menerima paling banyak \(7\) butir permen? (Siswa ini merupakan salah satu dari \(34\) siswa yang bersikeras menerima sedikitnya satu butir permen.)

20.

Berikan argumen kombinatorial untuk membuktikan identitas
\begin{equation*} k\binom{n}{k} = n\binom{n-1}{k-1}. \end{equation*}
Petunjuk.
Pikirkan proses memilih sebuah tim beserta kaptennya.

21.

Misalkan \(m\) dan \(w\) adalah bilangan bulat positif. Berikan argumen kombinatorial untuk membuktikan bahwa bagi bilangan bulat \(k\geq 0\text{,}\)
\begin{equation*} \sum_{j=0}^k \binom{m}{j}\binom{w}{k-j} = \binom{m+w}{k}. \end{equation*}

22.

Berapa banyak lintasan kisi dari \((0,0)\) ke \((10,12)\text{?}\)

23.

Berapa banyak lintasan kisi dari \((3,5)\) ke \((10,12)\text{?}\)

24.

Berapa banyak lintasan kisi dari \((0,0)\) ke \((10,12)\) yang melalui \((3,5)\text{?}\)

25.

Berapa banyak lintasan kisi dari \((0,0)\) ke \((17,12)\) yang melalui \((7,6)\) dan \((12,9)\text{?}\)

26.

Berapa banyak lintasan kisi dari \((0,0)\) ke \((14,73)\) yang tidak melalui \((6,37)\text{?}\)

27.

Seorang perampok bank di kota kecil sedang mengendarai mobil pelariannya dari bank yang baru saja dirampok menuju tempat persembunyiannya. Bank tersebut berada di persimpangan Jalan \(1^\text{st}\) dan Adimarga \(1^\text{st}\text{.}\) Ia harus kembali ke tempat persembunyiannya di persimpangan Jalan \(7^\text{th}\) dan Adimarga \(5^\text{th}\text{.}\) Namun, salah seorang pengintainya melaporkan bahwa satu-satunya polisi di kota itu sedang berhenti di persimpangan Jalan \(4^\text{th}\) dan Adimarga \(4^\text{th}\text{.}\) Dengan menganggap bahwa perampok bank tersebut tidak ingin ditangkap dan hanya berkendara di jalan dan adimarga, dalam berapa cara ia dapat kembali dengan aman ke tempat persembunyiannya? (Jalan dan adimarga di kota kecil ini berjarak seragam dan diberi nomor secara berurutan.)

28.

Soal ini berlatar di kota fiktif Mascotville, yang ditata seperti kisi. Para maskot hanya boleh berjalan di sepanjang jalan, bukan menempuh lintasan lurus “seperti tawon terbang.” Buzz, maskot Georgia Tech, ingin mengunjungi temannya Thundar, maskot North Dakota State University, yang tinggal \(6\) blok di sebelah timur dan \(7\) blok di sebelah utara sarang Buzz. Namun, Uga VIII baru saja pindah ke rumah anjing yang terletak \(2\) blok di sebelah timur dan \(3\) blok di sebelah utara sarang Buzz, dan sudah memiliki perintah hukum yang melarang Buzz mendekatinya. Ada pula sepasang harimau (induk dan anak) dari Clemson yang tinggal \(1\) blok di sebelah timur dan \(2\) blok di sebelah utara Uga VIII; keduanya dikenal suka memasang perangkap untuk Buzz. Buzz ingin pergi dari sarangnya ke kandang Thundar setiap hari tanpa bertemu Uga VIII maupun The Tiger dan The Tiger Cub. Namun, ia ingin menghindari kebosanan akibat menggunakan rute yang pernah dilaluinya. Berapa banyak hari berturut-turut paling lama Buzz dapat melakukan perjalanan untuk mengunjungi Thundar tanpa mengulangi rute (Anda boleh menganggap bahwa rute yang ditempuh Buzz hanya bergerak ke timur dan ke utara)?

29.

Tentukan koefisien \(x^{15}y^{120}z^{25}\) dalam \((2x+3y^2+z)^{100}\text{.}\)

30.

Tentukan koefisien \(x^{12}y^{24}\) dalam \((x^3+2xy^2+y+3)^{18}\text{.}\) (Berhati-hatilah karena kini \(x\) dan \(y\) masing-masing muncul dalam beberapa suku!)

31.

Untuk setiap kata di bawah ini, tentukan banyaknya susunan ulang yang menggunakan semua huruf dalam kata tersebut.
  1. OVERNUMEROUSNESSES
  2. OPHTHALMOOTORHINOLARYNGOLOGY
  3. HONORIFICABILITUDINITATIBUS (kata terpanjang dalam bahasa Inggris yang huruf konsonan dan vokalnya berselang-seling secara ketat
     1 
    http://www.rinkworks.com/words/oddities.shtml
    )

32.

Dalam berapa cara anggota suatu himpunan dengan \(27\) anggota dapat diwarnai sedemikian rupa sehingga \(7\) anggota berwarna putih, \(6\) berwarna emas tua, \(2\) berwarna biru, \(7\) berwarna kuning, \(5\) berwarna hijau, dan \(0\) berwarna merah?

33.

Ada banyak himpunan berguna yang banyak anggotanya dihitung oleh bilangan Catalan. (Jilid kedua karya R.P. Stanley, Enumerative Combinatorics, memuat sebuah latihan terkenal—atau mungkin terkenal buruk—dengan \(66\) bagian yang meminta pembaca menemukan bijeksi untuk menunjukkan bahwa banyaknya berbagai struktur kombinatorial adalah \(C(n)\text{,}\) sedangkan laman web-nya memuat daftar tambahan dengan sedikitnya \(100\) bagian.) Berikan argumen bijektif untuk menunjukkan bahwa banyaknya setiap kelas objek di bawah ini dihitung oleh \(C(n)\text{.}\) (Ketiganya dipilih dari daftar dalam buku Stanley.)
  1. Banyaknya cara memberi tanda kurung lengkap pada hasil kali \(n+1\) faktor seolah-olah operasi “perkalian” yang digunakan tidak harus asosiatif. Sebagai contoh, terdapat satu cara untuk memberi tanda kurung pada hasil kali dua faktor \((a_1a_2)\text{,}\) terdapat dua cara untuk memberi tanda kurung pada hasil kali tiga faktor (\((a_1(a_2a_3))\) dan \(((a_1a_2)a_3)\)), serta terdapat lima cara untuk memberi tanda kurung pada hasil kali empat faktor:
    \begin{equation*} (a_1(a_2(a_3a_4))), (a_1((a_2a_3)a_4)), ((a_1a_2)(a_3a_4)), ((a_1(a_2a_3))a_4), (((a_1a_2)a_3)a_4). \end{equation*}
  2. Barisan yang terdiri atas \(n\) buah \(1\) dan \(n\) buah \(-1\text{,}\) dengan jumlah \(i\) suku pertamanya merupakan bilangan bulat tak negatif untuk setiap \(i\text{.}\)
  3. Barisan bilangan bulat \(1\leq a_1\leq \cdots \leq a_n\) yang memenuhi \(a_i\leq i\text{.}\) Sebagai contoh, untuk \(n=3\text{,}\) barisan tersebut adalah
    \begin{equation*} 111\qquad 112\qquad 113\qquad 122\qquad 123. \end{equation*}
Petunjuk.
Untuk bagian ini 2.9.33.c, pikirkan cara menggambar lintasan kisi pada kertas bergaris kotak-kotak dan, pada dasarnya, menghitung banyaknya kotak di bawah suatu lintasan kisi dalam kolom tertentu.
SblmKe AtasLnjt