TUGAS MATEMATIKA DISKRIT TENTANG PELUANG DAN SARANG MERPATI

1. Informasi terkecil yang dapat disimpan di dalam memori computer adalaha byte, setiap byte disusun oleh 8 bit. Berapa banyak jumlah byte yang dimulai dengan satu-satu atau berakhir dengan satu-satu?

|A|= Banyaknya kotak yang terisi diawal dengan ‘1,1’. Maka 2⁶ = 64, karena posisi 2 diawal sudah terisi.

|B|= Banyaknya kotak yang terisi diakhir dengan ‘1,1’, maka 2⁶ = 64. Karena posisi 2 diakhir sudah terisi

|A∩B|= Karena posisi diawal dan diakhir sudah terisi. Maka yang terisi 4 posisi 2⁴ = 16 Sehingga:

|A∪B|  =   |A|+|B|-|A∩B|

           = 64+64-16

           = 112

2. Misalkan |A| adalah banyaknya anggota himpunan A |

|A|=a

|B|=b

|C|=c

|A∩B|=d

|A∩C|=e

|B∩C|=f

Dan |A∩B∩C|=g

Tentukan |A∪B∪C|!

Jawab: |A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∪B∪C|

3. Dari 27 orang mahasiswa, buktikan paling sedikit terdapat 2 orang yang namanya diawali dengan huruf yang sama!

Jawab:

Dari 27 orang mahasiswa, paling sedikit terdapat dua orang yang namanya diawali dengan huruf yang sama, karena hanya ada 26 huruf dalam alphabet. Jika kita menganggap 27 huruf awal dari nama-nama mahasiswa mrpati dan 26 huruf alphabet sebagai 26 buah sarang merpati, kita bias menetapkan pemasangan 27 huruf awal nama ke 26 huruf alphabet seperti halnya pemasangan merpati ke sarang merpati. Menurut prinsip sarang merpati, beberapa huruf awal alphabet dipasangkan dengan paling sedikit dua huruf awal nama mahasiswa.

4. Misalkan terdapat banyak bola merah, bola putih, dan bola biru di dalam sebuah kotak. Berapa paling sedikit jumlah bola yang terambil dari kotak (tanpa melihat ke dalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?

Jawab:

Jika setiap warna dianggap seagai sarang merpati, maka n=3. Karena itu, jika orang mengambil paling sedikit n+1= 4( merpati), maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil. Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain. Jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.

5. Misalkan sebuah turnamen basket diikuti oleh n buah tim yang dalam hal ini setiap tim bertanding dengan setiap tim lainnya dan setiap tim menang paling sedikit satu kali. Tunjukkan bahwa paling sedikit ada 2 tim yang mempunyai jumlah kemenangan yang sama.

Jawab;

Jumlah kemenangan setiap tim paling sedikit 1x dan paling banyak n-1 x. angka n-1 berkoresponden dengan n-1 buah sarang untuk menampung n ekor merpati (tim basket). Jadi, paling sedikit 2 tim basket yang mempunyai jumlah kemenangan sama.

6. Diantara 50 mahasiswa. Tunjukkan bahwa sedikitnya 5 orang lahir di bulan yang sama.

Jawab:

Misalkan ada 50 mahasiswa sebagai merpati dan ada 12 bulan sebagai sarang merpati, maka terdapat paling sedikit orang yang lahir pada bulan yang sama.

7. Ada n anak. Perlu berapa anak yang menjamin bahwa diantaranya memiliki 6 orang yang hari lahirnya sama

Jawab:

Dimisalkan

8. Suatu kartu bridge lengkap diambil satu-persatu dengan pengambilan. Berapa banyak cara yang mungkin untuk mengambil 10 kartu sedemikian sehingga kartu ke 10 adalah perulangan dari kartu yang telah diambil sebelumnya?

Jawab:

# Caea mengambil 10 kartu satu persatu

51 51 51 51 51 51 51 51 51 52

#memilih satu mengambil 10 kartu 52¹⁰

52¹⁰ – (51⁹.52) = 52(52⁹-51⁹)

9. Suatu pertandingan bola basket dengan system gugur diikuti oleh 101 regu. Dalam system tersebut regu yang kalah akan langsung gugur dan regu yang menang akan maju ke babak berikutnya. Jika jumlah regu dalam suatu babak tertentu ganjil, maka ada satu regu yang mendapatkan ‘bye’ (menang tenpa bertanding). Berapa banyak keseluruhan pertandingan yang harus dilakukan untuk mendapatkan 1 regu yang jadi juara?

Jawab:

Diketahui : banyak regu 101 regu

Ditanyakan : banyak keseluruhan pertandingan

Babak I 101:2 = 50 pertandingan dan 1 bye

Babak II 51:2 = 25 pertandingan dan 1 bye

Babak III 26:2 = 13 pertandingan

Babak IV 13:2 = 6 pertandingan dan 1 bye

Babak V 7:2 = 3 pertandingan dan 1 bye

Babak VI 4:2 = 2 pertandingan

Babak VII 2:2 = 1 prtandingan

Jumlah 56+25+13+6+3+2+1= 100 pertandingan

10. Fifty student were surveyed about their participation in hockey and baseball. The result of the survey were:

33 students played hockey

24 students played baseball

8 students played neither hockey or baseball

How many of the student surveyed played both hockey and baseball

The answer is