MAKALAHPRINSIP PIGEONHOLE DAN RELASI BERULANG

(RELASI REKURSIF)

DISUSUN SEBAGAI TUGAS KELOMPOKMATA KULIAH KOMBINATORIK

OLEH:KELOMPOK VI :

RIRIN ARIANTI NIM. G2 I1 14 026IMAN ASHARI NIM. G2 I1 14 024LUKMAN SANI NIM. G2 I1 14 028

PROGRAM STUDI PENDIDIKAN MATEMATIKA PROGRAM PASCASARJANAUNIVERSITIAS HALU OLEO

KENDARI2015

DAFTAR ISI

HalamanHALAMAN SAMPUL .................................................................. iDAFTAR ISI .............................................................................. iiBAB I PENDAHULUAN .............................................................. 1

A. Latar Belakang .............................................................. 1B. Rumusan Masalah ......................................................... 2C. Tujuan Penelitian ........................................................... 2

BAB II TINJAUAN PUSTAKA ...................................................... 3A. Prinsip Pigeonhole ......................................................... 3

1. Prinsip Pigeonhole Bentuk Pertama ........................... 42. Prinsip Pigeonhole Bentuk Kedua .............................. 53. Prinsip Pigeonhole Bentuk Ketiga .............................. 7

B. Relasi Berulang ............................................................. 8

BAB III PENUTUP .................................................................... 11A. Kesimpulan .................................................................... 11B. Saran.............................................................................. 11

DAFTAR PUSTAKA.................................................................... 12

BAB I

PENDAHULUAN

A. Latar Belakang

Matematika yang sering disebut ratu ilmu pengetahuan memiliki ruang lingkup

yang luas dan banyak aplikasi di kehidupan nyata. Ruang lingkupnya pun walaupun

mengkaji aspek yang berbeda namun tetap memiliki kesinambungan. Seperti adanya

beberapa prinsip kombinatorik dalam matematika diskrit yang dapat membantu

pembuktian teorema-teorema dalam teori bilangan. Matematika diskrit itu sendiri

merupakan cabang matematika yang mempelajari tentang obyek-obyek diskrit. Diskrit

itu sendiri adalah sejumlah berhingga elemen yang berbeda atau elemen-elemen yang

tidak bersambungan. Dimana data diskrit merupakan data yang satuannya selalu bulat

dalam bilangan asli, tidak berbentuk pecahan. Matematika diskrit meliputi

kombinatorik, relasi dan fungsi, relasi rekursif (relasi berulang), prinsip sangkar

burung merpati dan juga teori graf. Pada makalah ini akan dibahas mengenai

prinsip rumah merpati dan relasi rekursif (relasi berulang). 

Prinsip rumah merpati (Pigeonhole principle atau disebut The Box Principle pada

beberapa referensi) ditemukan pada tahun 1834 oleh seorang matematikwan Jerman

bernama Johann Peter Gustav Lejeune Dirichlet.

Pada umumnya Prinsip Pigeonhole merupakan salah satu teknik pembuktian

yang sederhana dan efektif. Selain itu prinsip ini merupakan salah satu alat

kombinatorial yang berguna dalam menghitung objek dengan property tertentu.

Prinsip pigeonhole mempunyai banyak pengaplikasian atau penerapan, diantaranya

dalam sains komputer, permasalahan relasi, pembagian, permasalahan numerikal,

permasalahan geometri umum, trik kartu kombionatorik, fungsi kuadrat, dan teori

ramsey. Prinsip sarang merpati juga merupakan sebuah contoh dari argument

menghitung yang biasa diaplikasikan pada banyak masalah formal, termasuk yang

mengandung himpunan tak terhingga yang tidak bisa dinyatakan dalam fungsi

korespodensi satu-satu.

Sedangkan Relasi berulang mendefinisikan sebuah barisan dengan memberikan

nilai ke-n yang dikaitkan dengan suku-suku sebelumnya. Untuk mendefinisikan

sebuah barisan, relasi ulang memerlukan nilai awal yang sudah ditentukan.

B. Rumusan Masalah

Adapun rumusan masalah pada makalah ini sebagai berikut :1. Bagaimana definisi Prinsip Pigeonhole?

2. Bagaimanakah contoh soal dari Prinsip Pigeonhole?

3. Bagaimana definisi relasi berulang?

4. Bagaimana contoh soal dari relasi berulang?

C. Tujuan

Tujuan dari makalah ini yaitu sebagai berikut :1. Memahami definisi Prinsip Pigeonhole.

2. Mengetahui contoh soal serta penyelesaian mengenai Prinsip Pigeonhole.

3. Memahami definisi relasi berulang.

4. Mengetahui contoh soal dan penyelesaian mengenai mengenai relasi

berulang.

BAB IIPEMBAHASAN

A. Prinsip Pigeonhole

Sebagai ilustrasi untuk memahami prinsip Pigeonhole, misalkan terdapat 3 burung merpati dan 2 sangkar burung merpati. Terdapat beberapa kemungkinan bagaimana burung-burung tersebut menempati sangkarnya. Berikut ini disajikan peristiwa bagaimana burung merpati menempati sangkar-sangkar itu.

Peristiwa 1 Peristiwa 2 Peristiwa 3 Peristiwa 4

Dari keempat peristiwa yang terjadi pada ilustrasi di atas, tampak bahwa di setiap peristiwa itu selalu ada satu sangkar burung atau lebih yang ditempati beberapa burung merpati. Lebih tepatnya kita katakan “paling sedikit ada satu sangkar burung yang ditempati oleh paling sedikit dua ekor burung merpati”.

Perhatikan bagaimana yang terjadi jika terdapat 4 burung merpati yang menempati 3 sangkar burung. Peristiwa yang terjadi diantaranya dapat dilihat pada gambar berikut. Pertama-tama perhatikan kemungkinan yang terjadi jika semua sangkar terisi. Karena banyaknya merpati melebihi banyaknya sangkar, maka peristiwa semua sangkar terisi ini dapat digambarkan sebagai berikut:

Peristiwa 1 Peristiwa 2 Peristiwa 3

Jika terdapat satu sangkar yang tidak terisi, maka kemungkinan yang dapat terjadi adalah seperti di bawah ini :

Peristiwa 1 Peristiwa 2 Peristiwa 3

Peristiwa 4 Peristiwa 5 Peristiwa 6

Peristiwa 7 Peristiwa 8 Peristiwa 9

Dari berbagai situasi yang diperlihatkan pada gambar di atas, dapat disimpulkan bahwa jika jumlah burung merpati melebihi jumlah sangkar, maka akan selalu “terdapat paling sedikit satu sangkar burung yang ditempati oleh paling sedikit dua ekor burung merpati”. Pernyataan ini tidak menentukan sangkar mana yang ditempati oleh paling sedikit 2 ekor burung merpati, tetapi hanya menjelaskan keberadaan dari sangkar tersebut. Secara formal Prinsip Pigeonhole ini dijelaskan dalam pernyataan berikut ini.

1. Prinsip Pigeonhole Bentuk Pertama“Jika n merpati ditempatkan pada m rumah merpati, dimana n > m, maka terdapat rumah merpati yang memuat paling sedikit dua merpati”.Untuk membuktikan pernyataan Prinsip Pigeonhole bentuk pertama ini, kita gunakan kontradiksi. Misalkan kesimpulan dari pernyataan tersebut salah, sehingga setiap rumah merpati memuat paling banyak satu merpati.Karena ada m rumah merpati, maka paling banyak m merpati yang bisa dimuat.Padahal ada n merpati yang tersedia dan n > m, sehingga kita dapatkan sebuah kontradiksi.

Contoh 1Pada saat pembentukan tugas kelompok yang dibagi menjadi enam kelompok, tujuh mahasiswa tidak masuk kuliah sehingga mereka belum terdaftar dalam kelompok yang sudah dibagi. Tunjukkan bahwa paling sedikit ada dua mahasiswa yang bergabung dalam satu kelompok!

Penyelesaian : Kita asumsikan tujuh mahasiswa tersebut dengan merpati dan enam kelompok sebagai rumah merpati. Berdasarkan prinsip pigeonhole bentuk pertama terdapat rumah merpati yang memuat paling sedikit dua merpati. Dengan demikian terdapat suatu kelompok yang memuat paling sedikit dua mahasiswa.

Contoh 2Seorang kyai di sebuah desa yang selalu diminta untuk memberikan nama bayi yang lahir, menyiapkan nama depan Mohammad, Akhmad, Abdul dan nama belakang Hadi, Akbar, Gofur bagi bayi yang lahir dalam suatu bulan tertentu.Pada bulan

tersebut terdapat sebelas bayi yang lahir di desa itu. Tunjukkan bahwa paling sedikit ada dua bayi yang mempunyai nama yang sama dengan asumsi bahwa kyai tersebut selalu memberikan nama depan dan belakang!

Penyelesaian : Terdapat sembilan kombinasi nama depan dan belakang yang mungkin untuk sebelas bayi yang lahir pada bulan tersebut. Kita asumsikan sebelas bayi tersebut dengan merpati dan sembilan nama sebagai rumah merpati.Berdasarkan prinsip pigeonhole bentuk pertama terdapat rumah merpati yang memuat paling sedikit dua merpati. Dengan demikian terdapat kombinasi nama yang dipakai paling sedikit dua bayi.

Prinsip Pigeonhole ini bisa kita nyatakan dalam bentuk lain seperti berikut ini.

2. Prinsip Pigeonhole Bentuk KeduaJika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y dan |X| > |Y |, maka f(x1) = f(x2) untuk beberapa x1, x2∈ X, dimana x1 ≠ x2.Untuk membuktikan Prinsip Pigeonhole Bentuk Kedua ini kita bisa menggunakan Prinsip Pigeonhole Bentuk Pertama dengan mengasumsikan X sebagai himpunan merpati dan Y sebagai himpunan rumah merpati. Selanjutkan kita memasangkan merpati x ke rumah merpati f(x). Karena jumlah merpati lebih banyak dari rumahnya, maka terdapat paling sedikit dua merpati, x1, x2 ∈ X yang dipasangkan ke rumah merpati yang sama, yaitu f(x1) = f(x2) untuk beberapa x1, x2 ∈ X, dimana x1 ≠ x2.

Contoh 3Ketua Program Studi Pendidikan Matematika akan membuat kode mata kuliah untuk mata kuliah - mata kuliah bidang studi matematika dengan cara menambahkan tiga angka pada huruf

KPM. Terdapat 51 mata kuliah yang harus diberi kode dan tiga angka yang harus ditambahkan pada huruf KPM harus berkisar antara 101 sampai dengan 200. Tunjukkan bahwa terdapat paling sedikit dua mata kuliah yang diberi kode dengan angka berurutan.

Penyelesaian : Misalkan angka-angka yang dipilih adalah :a1, a2, ..., a51

Jika angka-angka di atas digunakan bersama-sama dengana1 + 1, a2 + 1, ..., a51 + 1

maka terdapat 102 nomor yang merentang antara 101 sampai dengan 201. Karena ada 100 nomor yang disediakan (yaitu 101 sampai dengan 200) dan ada 102 nomor yang akan digunakan, maka menurut Prinsip Pigeonhole Bentuk Kedua terdapat paling sedikit dua nomor yang sama. Nomor a1, a2, ..., a51 dan a1 + 1, a2

+ 1, ..., a51 + 1 semuanya berbeda. Sehingga kita mempunyaiai= aj+ 1

Dengan demikian kode ai berurutan dengan kode aj.

Prinsip Pigeonhole Bentuk Kedua ini dapat dinyatakan ke dalam bentuk yang lebih umum seperti penyataan berikut ini.

3. Prinsip Pigeonhole Bentuk KetigaJika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y , dimana |X| = n, |Y | = m dan

[ nm ]=k, maka terdapat paling sedikit k anggota x1, x2, ..., xk ∈ X

sedemikian hinggaf(x1) = f(x2) = ... = f(xk)

Untuk membuktikan pernyataan Prinsip Pigeonhole bentuk ketiga ini, kita gunakan kontradiksi. Misalkan Y = {y1, y2, ..., ym}. Andaikan kesimpulan dari pernyataan tersebut salah, maka terdapat paling banyak k − 1 anggota x∈ X dengan f(x) = y1; terdapat paling banyak k − 1 anggota x ∈ X dengan f(x) = y2, dan seterusnya sampai dengan terdapat paling banyak k − 1 anggota x ∈ X dengan f(x) = ym. Sehingga terdapat paling banyak m(k − 1) anggota X. Namun demikian

m(k − 1) < m. nm= n

yang merupakan sebuah kontradiksi. Oleh karena itu, terdapat paling sedikit k anggota x1, x2, ..., xk∈X sedemikian hingga

f(x1) = f(x2) = ... = f(xk)

Contoh 4Dalam mata kuliah Matematika Diskrit diberikan tugas kelompok yang akan dibagi menjadi enam kelompok. Jika terdapat 62 mahasiswa yang menempuh mata kuliah tersebut, tunjukkan bahwa terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama!

Penyelesaaian : Kita asumsikan mahasiswa tersebut sebagai anggota dari himpunan daerahasal X dan kelompoknya sebagai

anggota daerah kawan Y. Karena |X| =62, |Y| = 6 dan [ 626 ]= 11.

Maka berdasarkan Prinsip Pigeonhole Bentuk Ketiga, terdapat paling sedikit 11 anggota X yang dipasangkan dengan suatu anggota Y yang sama. Dengan demikian terdapat paling sedikit ada 11 mahasiswa yang menjadi anggota suatu kelompok yang sama.

B. Relasi Berulang

Relasi berulang mendefinisikan sebuah barisan dengan memberikan nilai ke-n yang dikaitkan dengan suku-suku sebelumnya. Untuk mendefinisikan sebuah barisan, relasi ulang memerlukan nilai awal yang sudah ditentukan. Secara formal relasi berulang ini didefinisikan sebagai berikut.

Definisi :Sebuah relasi berulang untuk barisan a0, a1, ... merupakan sebuah persamaan yang mengaitkan an dengan a0, a1, ... , an−1. Syarat awal untuk barisan a0, a1, ... adalah nilai-nilai yang diberikan secara eksplisit pada beberapa suku dari barisan tersebut.

Contoh 5Barisan 3, 7, 11, 15, ... didefinisikan dengan relasi berulang

an= an−1 + 4, n≥1dengan syarat awal a0 = 3.

Contoh 6Carilah sebuah relasi berulang dan syarat awal yang membentuk sebuah barisan 1, 1, 2, 4, 16, 128, 4096, ....Penyelesaian :

2 = 2 × 1 × 14 = 2 × 2 × 116 = 2 × 4 × 2128 = 2 × 16 × 44096 = 2 × 128 × 16

Dengan demikian relasi berulangnya adalahan= 2 × an−1× an−2 dengan n ≥2

dengan syarat awal a0 = 1 dan a1 = 1.

Contoh 7

Seseorang mendepositokan uang sebesar Rp. 1.000.000,- pada sebuah bank dengan bunga majemuk 12% per tahun. Jika An menyatakan jumlah uang pada akhir tahun ke-n, carilah sebuah relasi berulang dan syarat awal yang mendefinisikan barisan An.Penyelesaian :Pada akhir tahun ke-1, jumlah uangnya adalah A1 sama dengan jumlah awal ditambah bunga. Jika jumlah awal dinyatakan dengan A0, makaA1 = A0 + 0, 12 × A0 = 1, 12 × A0

Pada akhir tahun ke-2, jumlah uangnya adalah A2 sama dengan jumlah uang pada akhir tahun ke-1 ditambah bunga. SehinggaA2 = A1 + 0, 12 × A1 = 1, 12 × A1

Pada akhir tahun ke-n, jumlah uangnya adalah An sama dengan jumlah uang pada akhir tahun ke-n − 1 ditambah bunga. SehinggaAn= An−1 + 0, 12 × An−1 = 1, 12 × An−1

Karena A0 merupakan jumlah awal, maka A0 = 1.000.000.Dengan demikian relasi berulangnya adalah

An= 1, 12 × An−1 dengan n ≥1dengan syarat awal A0 = 1.000.000.

Penyelesaian Relasi Berulang

Menyelesaikan relasi berulang yang melibatkan barisan a0, a1, ...sama halnya dengan mencari sebuah rumus eksplisit untuk bentuk umum an. Pada bagian ini kita hanya akan membahas penyelesaian relasi berulang dengan menggunakan metode iterasi. Untuk menyelesaikan relasi berulang dengan metode iterasi ini, kita menuliskan bentuk ke-n, yaitu an dalam bentuk-bentuk suku sebelumnya, yaitu an−1, an−2, ..., a0. Kemudian secara berurutan kita gunakan relasi berulang untuk menempatkan setiap an−1, ... dengan ketentuan pendahulunya. Kita lakukan terus sampai sebuah rumus eksplisit diperoleh.

Contoh 8Selesaikan relasi berulang

an= an−1 + 4, dengan n ≥1dengan syarat awal a0 = 3.Penyelesaian :Dengan mengganti n dengan n − 1 pada rumus diatas, kita peroleh

an−1 = an−2 + 4Sehingga

an = an−1 + 4 = (an−2 + 4) + 4= ((an−3 + 4) + 4) + 4...= a0 + 4n

Karena a0 = 3, maka kita perolehan= 3 + 4n

Contoh 9Selesaikan relasi berulang yang diperoleh dari Contoh 7 tentang deposito uang di bank dengan bunga 12%.Penyelesaian :Relasi berulangnya adalahAn= 1, 12 × An−1 dengann ≥1dengan syarat awal A0 = 1000000.

An = 1, 12 × An−1

= 1, 12 × (1, 12 × An−2)= 1, 12 × (1, 12 × (1, 12 × An−3))...= 1, 12n × A0

Karena A0 = 1000000, maka kita perolehAn= 1000000 × 1,12n

BAB IIIPENUTUP

A. KesimpulanBerdasarkan uraian di atas dapat disimpulkan beberapa hal sebagai berikut :1. Dalam bentuk yang paling umum, prinsip Pigeonhole didefinisikan

sebagai berikut:Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y , dimana |X| = n, |Y | = m dan

[ nm ]=k, maka terdapat paling sedikit k anggota x1, x2, ..., xk∈ X

sedemikian hinggaf(x1) = f(x2) = ... = f(xk)

2. Relasi berulang didefinisikan sebagai berikut:Sebuah relasi berulang untuk barisan a0, a1, ... merupakan sebuah persamaan yang mengaitkan an dengan a0, a1, ..., an−1. Syarat awal untuk barisan a0, a1, ...adalah nilai-nilai yang diberikan secara eksplisit pada beberapa suku dari barisan tersebut.

B. Saran

1. Materi Pigeonhole principle dan relasi berulang sesungguhnya banyak sekali

ditemukan di kehidupan kita sehari-hari, dan kasusnya tidak sesederhana kasus-

kasus yang telah diberikan di atas. Selain, teori bilangan, prinsip pigeonhole bisa

diterapkan pada kasus geometri, trigonometri dan sebagainya. Lalu relasi berulang

juga dapat diterapan pada kasus Bilangan Fibonacci, Menara Hanoi dan

sebagainya. Jadi para pembaca disarankan untuk mengkaji atau mempelajari lebih

jauh kedua materi tersebut.

2. Makalah ini masih belum sempurna dikarenakan keterbatasan bahan, data atau

sumber materi. Oleh karena itu, saran dan kritik sangat diperlukan untuk perbaikan

makalah ini.

DAFTAR PUSTAKA

https://www.academia.edu/9726501/Prinsip_Sarang_Merpati

http://www.scribd.com/doc/76137612/05-Prinsip-Pigeonhole#scribd

http://math-solar.blogspot.com/2012/05/relasi-rekursif.html

http://apriyani13.blogspot.com/2013/05/makalah-madis-relasi-berulang.html