Test IIMA 2281 Matematika Diskrit Departemen MatematikaHari,Tanggal: Kamis, 31 Maret 2005 Institut Teknologi BandungWaktu: 100 MenitSemester: II, 2004/2005

No. 1. (Prinsip Sarang Merpati)

Berapa banyak bilangan yang harus dipilih dari himpunan {1,3,5,7,9,11,13,15} untuk menjamin bahwa paling sedikit satu pasang bilangan memiliki jumlah 16?Gunakan prinsip sarang merpati untuk menjelaskan jawaban Anda.

No. 2. (Counting)

Empat belas mahasiswa Departemen Matematika akan bertanding sepakbola.a. Ada berapa cara untuk memilih sebelas pemain pertama?b. Ada berapa cara untuk memilih sebelas pemain pertama dengan memperhatikan

nomor urut (posisi) pemain?c. Jika tiga dari mahasiswa tersebut adalah wanita, ada berapa cara untuk memilih

kesebelas pemain pertama dengan syarat minimal terdapat satu pemain wanita yang terpilih?

No. 3. (Koefisien Binomial)

Misalkan n dan k adalah bilangan bulat dengan 1 ≤ k ≤ n. Buktikan bahwa

a. dengan menggunakan bukti kombinatorial.b. dengan menggunakan bukti secara aljabar.

No. 4. (Counting)

Terdapat 10 soal dalam ujian akhir Matematika Diskrit. Ada berapa cara untuk memberikan nilai bagi setiap soal jika total nilai untuk kesepuluh soal tersebut adalah 100 dan setiap soal mempunyai nilai minimal 5?

Ujian Tengah Semester IMA 2281 Matematika Diskrit Departemen MatematikaHari,Tanggal: Rabu, 17 Maret 2004 Institut Teknologi BandungWaktu: 100 MenitSemester: II, 2003/2004

Solusi

No. 1. (Prinsip Sarang Merpati)

Pandang empat subhimpunan yang mempartisi {1,3,5,7,9,11,13,15} berikut:{1,15}, {3,13}, {5,11}, {7,9}

Anggota-anggota dari keempat subhimpunan tersebut, bila dijumlahkan, akan tepat sama dengan 16.

Jadi, jika kita memilih 5 bilangan dari {1,3,5,7,9,11,13,15}, menurut prinsip sarang merpati, paling tidak terdapat sepasang bilangan yang merupakan anggota dari subhimpunan yang sama. Akibatnya, pasangan bilangan tersebut jumlahnya sama dengan 16.

No. 2. (Counting)

a. Ada berapa cara untuk memilih sebelas pemain pertama?

Karena urutan tidak penting, maka banyaknya cara adalah C(14,11).

b. Ada berapa cara untuk memilih sebelas pemain pertama dengan memperhatikan nomor urut (posisi) pemain?

Karena urutan penting, maka banyaknya cara adalah P(14,11).

c. Jika tiga dari mahasiswa tersebut adalah wanita, ada berapa cara untuk memilih kesebelas pemain pertama dengan syarat minimal terdapat satu pemain wanita yang terpilih?

Banyaknya cara untuk memilih satu pemain dari 3 wanita adalah C(3,1).Banyaknya cara untuk memilih sepuluh pemain sisanya dari 11 pria adalah C(11,10).Jadi, banyaknya cara untuk memilih sebelas pemain dengan tepat 1 pemain wanita adalah C(3,1) . C(11,10).

Dengan cara yang sama dapat dihitung banyaknya cara untuk memilih sebelas pemain dengan tepat 2 pemain wanita dan tepat 3 pemain wanita.

Ujian Tengah Semester IMA 2281 Matematika Diskrit Departemen MatematikaHari,Tanggal: Rabu, 17 Maret 2004 Institut Teknologi BandungWaktu: 100 MenitSemester: II, 2003/2004

Jadi, secara keseluruhan, banyaknya cara untuk memilih kesebelas pemain pertama dengan syarat minimal terdapat satu pemain wanita adalah

C(3,1) . C(11,10) + C(3,2) . C(11,9) + C(3,3) . C(11,8).No. 3. (Koefisien Binomial)

a. dengan menggunakan bukti kombinatorial.

Misalkan S adalah himpunan dengan n anggota, akan dihitung banyaknya cara memilih subhimpunan S yang memiliki tepat k anggota dan memilih suatu anggota tertentu dari subhimpunan tersebut.

Cara pertama dilakukan dengan terlebih dahulu memilih subhimpunan yang

dapat dilakukan dengan cara. Baru kemudian diikuti dengan memilih satu

anggota subhimpunan yang dapat dilakukan dengan k cara. Jadi, terdapat

cara untuk memilih subhimpunan S yang memiliki k anggota dan memilih suatu anggota tertentu dari subhimpunan tersebut.

Cara kedua dilakukan dengan pertama-tama memilih satu anggota dari himpunan S, yang dapat dilakukan dengan n cara. Kemudian, untuk memilih subhimpunannya, kita hanya tinggal memilih k-1 dari n-1 anggota S yang tersisa,

yang dapat dilakukan dengan cara. Jadi, terdapat cara untuk

memilih subhimpunan S yang memiliki k anggota dan memilih suatu anggota tertentu dari subhimpunan tersebut.

Akibatnya, .

b. dengan menggunakan bukti secara aljabar.

Ujian Tengah Semester IMA 2281 Matematika Diskrit Departemen MatematikaHari,Tanggal: Rabu, 17 Maret 2004 Institut Teknologi BandungWaktu: 100 MenitSemester: II, 2003/2004

No. 4. (Counting)

Misalkan nilai untuk soal ke-i dalam ujian adalah Ni, i=1,2,…,10. Karena nilai total adalah 100, maka

Banyaknya solusi untuk persamaan di atas adalah C(100-5.10,10-1) = C(50,9).