Sebuah sekolah memiliki \(147\) siswa kelas tiga. Para guru kelas tiga telah merencanakan sajian istimewa untuk hari terakhir sekolah dan membawa es krim bagi siswa mereka. Tersedia tiga rasa: mint dengan kepingan cokelat, cokelat, dan stroberi. Misalkan \(60\) siswa menyukai (sedikitnya) rasa mint dengan kepingan cokelat, \(103\) menyukai cokelat, \(50\) menyukai stroberi, \(30\) menyukai mint dengan kepingan cokelat dan stroberi, \(40\) menyukai mint dengan kepingan cokelat dan cokelat, \(25\) menyukai cokelat dan stroberi, serta \(18\) menyukai ketiga rasa tersebut. Berapa banyak siswa yang tidak menyukai satu pun rasa yang tersedia?
Terdapat \(1189\) mahasiswa yang mengambil program studi ilmu komputer di sebuah universitas tertentu. Mereka disurvei mengenai pengetahuan tentang tiga bahasa pemrograman: C++, Java, dan Python. Hasil survei menunjukkan bahwa \(856\) mahasiswa menguasai C++, \(792\) menguasai Java, dan \(692\) menguasai Python. Selain itu, \(639\) mahasiswa menguasai C++ dan Java, \(519\) menguasai C++ dan Python, serta \(632\) menguasai Java dan Python. Terdapat \(488\) mahasiswa yang melaporkan bahwa mereka menguasai ketiga bahasa tersebut. Berapa banyak mahasiswa yang melaporkan bahwa mereka tidak menguasai satu pun dari ketiga bahasa pemrograman itu?
Berapa banyak bilangan bulat positif yang kurang dari atau sama dengan \(100\) yang habis dibagi \(2\text{?}\) Berapa banyak bilangan bulat positif yang kurang dari atau sama dengan \(100\) yang habis dibagi \(5\text{?}\) Gunakan informasi ini untuk menentukan berapa banyak bilangan bulat positif yang kurang dari atau sama dengan \(100\) yang bukan kelipatan\(2\) maupun \(5\text{.}\)
Berapa banyak bilangan bulat positif yang kurang dari atau sama dengan \(100\) yang tidak habis dibagi oleh satu pun dari \(2\text{,}\)\(3\text{,}\) dan \(5\text{?}\)
Berapa banyak bilangan bulat positif yang kurang dari atau sama dengan \(1000\) yang tidak habis dibagi oleh satu pun dari \(3\text{,}\)\(8\text{,}\) dan \(25\text{?}\)
Negara Bagian Georgia membagikan dana sebesar $\(173\) juta kepada wilayah administratif Fulton, Gwinnett, DeKalb, Cobb, dan Clayton (dalam jutaan dolar). Dalam berapa cara dana ini dapat dibagikan jika setiap wilayah menerima sedikitnya $\(1\) juta, wilayah Clayton menerima paling banyak $\(10\) juta, dan wilayah Cobb menerima paling banyak $\(30\) juta? Bagaimana jika kita menambahkan syarat bahwa wilayah Fulton harus menerima sedikitnya $\(5\) juta (alih-alih sedikitnya $\(1\) juta)?
Seorang mahasiswa pascasarjana makan siang di pujasera kampus setiap hari Selasa selama satu semester yang berlangsung \(15\) minggu. Setiap minggu, ia ditemani oleh suatu subhimpunan dari kelompok enam orang temannya yang berasal dari berbagai penjuru kampus. Selama satu semester, ia makan siang dengan setiap teman sebanyak \(11\) kali, setiap pasangan teman sebanyak \(9\) kali, dan setiap kelompok tiga teman sebanyak \(6\) kali. Ia makan siang dengan setiap kelompok empat teman sebanyak \(4\) kali dan setiap kelompok lima teman sebanyak \(4\) kali. Ketujuh orang tersebut makan siang bersama-sama hanya sekali pada semester itu. Apakah mahasiswa pascasarjana tersebut pernah makan siang sendirian? Jika ya, berapa kali?
Sekelompok \(268\) mahasiswa disurvei mengenai kemampuan mereka berbahasa Mandarin, Korea, dan Jepang. Terdapat \(37\) mahasiswa yang tidak dapat berbicara dalam satu pun dari ketiga bahasa yang disurvei. Bahasa Mandarin dikuasai oleh \(174\) mahasiswa, bahasa Jepang dikuasai oleh \(139\) mahasiswa, dan bahasa Korea dikuasai oleh \(112\) mahasiswa. Hasil survei juga menunjukkan bahwa \(102\) mahasiswa menguasai bahasa Mandarin dan Jepang, \(81\) mahasiswa menguasai bahasa Mandarin dan Korea, serta \(71\) mahasiswa menguasai bahasa Jepang dan Korea. Berapa banyak mahasiswa yang menguasai ketiga bahasa tersebut?
Seperti dalam Contoh 7.4, misalkan \(X\) adalah himpunan fungsi dari \([n]\) ke \([m]\) dan suatu fungsi \(f\in X\) memenuhi sifat \(P_i\) jika tidak ada \(j\) sedemikian sehingga \(f(j)=i\text{.}\)
Misalkan fungsi \(f\colon [8]\to [7]\) didefinisikan oleh Gambar 7.18. Apakah \(f\) memenuhi sifat \(P_2\text{?}\) Mengapa demikian atau mengapa tidak? Bagaimana dengan sifat \(P_3\text{?}\) Cantumkan semua sifat \(P_i\) (dengan \(i\leq 7\)) yang dipenuhi oleh \(f\text{.}\)
Apakah mungkin mendefinisikan fungsi \(g\colon [8]\to [7]\) yang tidak memenuhi satu pun sifat \(P_i\text{,}\)\(i\leq 7\text{?}\) Jika mungkin, berikan sebuah contoh. Jika tidak, jelaskan alasannya.
Apakah mungkin mendefinisikan fungsi \(h\colon [8]\to [9]\) yang tidak memenuhi satu pun sifat \(P_i\text{,}\)\(i\leq 9\text{?}\) Jika mungkin, berikan sebuah contoh. Jika tidak, jelaskan alasannya.
Seperti dalam Contoh 7.5, misalkan \(X\) adalah himpunan permutasi pada \([n]\) dan katakan bahwa \(\sigma\in X\) memenuhi sifat \(P_i\) jika \(\sigma(i) = i\text{.}\)
Misalkan permutasi \(\sigma\colon [8]\to [8]\) didefinisikan oleh Gambar 7.19. Apakah \(\sigma\) memenuhi sifat \(P_2\text{?}\) Mengapa demikian atau mengapa tidak? Bagaimana dengan sifat \(P_6\text{?}\) Cantumkan semua sifat \(P_i\) (dengan \(i\leq 8\)) yang dipenuhi oleh \(\sigma\text{.}\)
Berikan contoh permutasi \(\tau\colon[8]\to[8]\) yang memenuhi sifat \(P_1\text{,}\)\(P_4\text{,}\) dan \(P_8\text{,}\) tetapi tidak memenuhi sifat \(P_i\) lainnya dengan \(1\leq i\leq 8\text{.}\)
Seperti dalam Contoh 7.6, misalkan \(m\) dan \(n\) adalah bilangan bulat positif dan \(X=[n]\text{.}\) Kita katakan bahwa \(j\in X\) memenuhi sifat \(P_i\) untuk suatu \(i\) dengan \(1\leq i\leq m\) jika \(i\) merupakan pembagi dari \(j\text{.}\)
Misalkan \(m=n=15\text{.}\) Apakah \(12\) memenuhi sifat \(P_3\text{?}\) Mengapa demikian atau mengapa tidak? Bagaimana dengan sifat \(P_5\text{?}\) Cantumkan sifat-sifat \(P_i\) dengan \(1\leq i\leq 15\) yang dipenuhi oleh \(12\text{.}\)
Berikan contoh bilangan bulat \(j\) dengan \(1\leq j\leq 15\) yang memenuhi tepat empat sifat \(P_i\) dengan \(1\leq i\leq 15\text{,}\) atau jelaskan mengapa bilangan bulat semacam itu tidak ada.
Berikan contoh bilangan bulat \(j\) dengan \(1\leq j\leq 15\) yang memenuhi tepat tiga sifat \(P_i\) dengan \(1\leq i\leq 15\text{,}\) atau jelaskan mengapa bilangan bulat semacam itu tidak ada.
Seorang guru memiliki \(10\) buku (semuanya berbeda) yang ingin ia bagikan kepada John, Paul, Ringo, dan George dengan memastikan bahwa setiap orang menerima sedikitnya satu buku. Dalam berapa cara ia dapat melakukannya?
Seorang penyelia memiliki sembilan tugas yang harus diselesaikan dan lima karyawan yang dapat ia beri tugas-tugas tersebut. Jika ia ingin memastikan bahwa setiap karyawan diberi sedikitnya satu tugas untuk dikerjakan, ada berapa cara untuk membagikan tugas-tugas tersebut kepada para karyawan?
Seorang profesor bekerja bersama enam mahasiswa sarjana dalam kegiatan penelitian. Ia memiliki \(12\) topik yang ingin mulai diteliti oleh para mahasiswa tersebut. Karena ia telah bekerja bersama Katie selama beberapa semester, ia ingin memastikan bahwa Katie diberi topik yang paling menantang (dan mungkin topik-topik lainnya). Setiap topik harus diberikan kepada tepat satu mahasiswa. Dengan ketentuan ini, dalam berapa cara ia dapat membagikan topik-topik tersebut kepada para mahasiswanya jika setiap mahasiswa harus diberi sedikitnya satu topik?
Cantumkan semua permutasi tanpa titik tetap pada \([4]\text{.}\) (Agar ringkas, Anda boleh menuliskan permutasi \(\sigma\) sebagai string \(\sigma(1)\sigma(2)\sigma(3)\sigma(4)\text{.}\))
Petugas perlengkapan sebuah tim sepak bola sedang terburu-buru membagikan seragam kepada enam pemain terakhir yang datang sebelum pertandingan. Alih-alih memastikan bahwa setiap pemain menerima seragamnya sendiri, ia sekadar menyerahkan satu seragam kepada masing-masing dari keenam pemain tersebut. Dalam berapa cara ia dapat membagikan seragam-seragam itu sehingga tidak ada pemain yang menerima seragamnya sendiri? (Anggaplah bahwa enam seragam yang tersisa memang milik enam pemain yang datang terakhir.)
Seorang petugas penggajian yang ceroboh memasukkan cek gaji para karyawan ke dalam amplop-amplop yang telah diberi label. Amplop-amplop itu sudah disegel sebelum petugas tersebut menyadari bahwa ia tidak mencocokkan nama pada cek gaji dengan nama pada amplop. Jika terdapat tujuh karyawan, dalam berapa cara ia mungkin telah memasukkan cek-cek gaji ke dalam amplop sehingga tepat tiga karyawan menerima cek gaji yang benar?
Prinsip inklusi–eksklusi bukan satu-satunya pendekatan yang tersedia untuk menghitung permutasi tanpa titik tetap. Kita mengetahui bahwa \(d_1=0\) dan \(d_2=1\text{.}\) Dengan menggunakan informasi awal ini, kita dapat memberikan bentuk rekursif untuk \(d_n\text{.}\) Dalam latihan ini, kita mempertimbangkan dua relasi rekursif untuk \(d_n\text{.}\)
Berikan argumen kombinatorial untuk membuktikan bahwa banyaknya permutasi tanpa titik tetap memenuhi rumus rekursif \(d_n = (n-1)(d_{n-1}+d_{n-2})\) untuk \(n\geq 3\text{.}\)
Untuk suatu permutasi tanpa titik tetap \(\sigma\text{,}\) tinjau bilangan bulat \(k\) dengan \(\sigma(k)=1\text{.}\) Susun argumen berdasarkan banyaknya pilihan untuk \(k\text{,}\) lalu berdasarkan apakah \(\sigma(1)=k\) atau tidak.
Di sebuah sekolah yang sangat kecil, terdapat satu kelas yang berisi sembilan siswa. Para siswa, yang akan kita nyatakan sebagai \(A\text{,}\)\(B\text{,}\)\(C\text{,}\)\(D\text{,}\)\(E\text{,}\)\(F\text{,}\)\(G\text{,}\)\(H\text{,}\) dan \(I\text{,}\) berjalan dari ruang kelas menuju ruang makan dalam urutan \(ABCDEFGHI\text{.}\) (Anggaplah \(A\) berada paling depan dalam barisan.) Dalam perjalanan kembali ke ruang kelas setelah makan siang, mereka ingin berjalan dalam suatu urutan sedemikian sehingga tidak ada siswa yang berjalan tepat di belakang teman sekelas yang sama dengan saat berangkat makan siang. (Sebagai contoh, \(ACBDIHGFE\) dan \(IHGFEDCBA\) akan memenuhi kriteria mereka. Namun, mereka tidak akan puas dengan \(CEFGBADHI\) karena urutan tersebut memuat \(FG\) dan \(HI\text{,}\) sehingga \(G\) kembali mengikuti \(F\) dan \(I\) kembali mengikuti \(H\text{.}\))
Seorang siswa bertanya-tanya ada berapa kemungkinan bagi mereka untuk berbaris dengan memenuhi kriteria ini. Bantulah ia dengan menentukan nilai tepat dari banyaknya kemungkinan tersebut.
Apakah bilangan ini lebih besar, lebih kecil, atau sama dengan banyaknya cara mereka dapat kembali sedemikian sehingga tidak ada siswa yang berjalan di posisi yang sama seperti sebelumnya (i.e., \(A\) tidak berada di posisi pertama, \(B\) tidak berada di posisi kedua, …, dan \(I\) tidak berada di posisi terakhir)?
Berapa proporsi (nyatakan sebagai bilangan desimal) dari seluruh kemungkinan susunan barisan mereka yang memenuhi kriteria bahwa dalam perjalanan pulang tidak ada siswa yang berjalan tepat di belakang siswa yang sama seperti sebelumnya?
