Jika Enam Orang Bertemu

enam orang

Sumber: sparkselite.com.au

Jika ada 6 orang bertemu, melakukan pertemuan maka jelas setiap 2 orang dari 6 orang tersebut hanya memiliki 2 kemungkinan hubungan: saling mengenal atau sebaliknya tidak saling mengenal, baru berkenalan pada pertemuan tersebut. Nah.. yang jadi pertanyaan adalah:

Ada berapa orang yang saling mengenal atau sebaliknya tidak saling mengenal?

Pertanyaan diatas dapat dijawab oleh teorema berikut:

Teorema: Jika 6 orang bertemu maka paling tidak ada 3 orang saling mengenal atau sebaliknya paling tidak ada 3 orang tidak saling mengenal

Teorema diatas punya banyak nama ada yang menyebutnya Teorema pada teman dan orang asing (Theorem on friends and strangers), ada yang menyebutnya Teorema pesta (Party Theorem) ,ada yang yang menyebutnya Teorema Ramsey (Ramsey’s Theorem) karena pertama kali di publish oleh Frank P. Ramsey.

Jika 6 orang tersebut direpresentasikan dengan 6 titik, Hubungan saling mengenal dengan garis berwarna biru dan hubungan tidak saling mengenal dengan garis berwarna merah. Itu berarti setiap 2 titik terhubung garis bisa garis merah atau biru. Diperoleh Graph komplit yaitu setiap 2 titik terhubung garis dengan 6 titik dan 15 garis, dinotasikan K_6. Sekarang kita bisa menyatakan teorema diatas menurut Teori Graph:

Bagaimanapun cara mewarnai 15 garis pada  K_6 dengan warna merah atau biru maka akan mucul segitiga merah yaitu segitiga yang ke-3 sisinya berwana merah yang merepresentasikan 3 orang tidak saling mengenal atau mucul segitiga biru yang merepresentasikan 3 orang saling mengenal,

Dengan kata lain jika kita mewarnai ke-15 garis pada K_6 dengan warna merah atau biru maka akan selalu terdapat 2 kemungkinan muncul segitiga merah atau segitiga biru.

Bukti: 

segitiga merahAmbil salah satu titik, sebut saja P_1 maka terdapat 5 garis yang menghubungkan P_1 dengan ke-5 titik lainnya dengan kemungkinan warna merah atau biru. Berdasarkan prinsip sarang merpati (pigeonhole Principle)  ada 3 garis berwarna sama. Tanpa kehilangan keumuman ( Without loss of generality) Sebut saja 3 garis tersebut berwana merah menghubungkan P_1 dengan P_2P_3 dan P_4. Jika salah satu garis yang antara P_2P_3 dan P_4 berwarna merah maka akan terbentuk segitiga merah, sebaliknya akan terbentuk segitiga biru

QED 

Advertisements

About Aria Turns

Seorang Alumnus Matematika UGM, dengan ilmu yang didapat ketika kuliah (Padahal sering bolos kuliah :p ), saya menyebarkan virus matematika
This entry was posted in graph theory, pembuktian and tagged , , , , , . Bookmark the permalink.

One Response to Jika Enam Orang Bertemu

  1. andri says:

    so what?

Silahkan, tinggalkan komentar

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s