Teorema teman dan orang asing

Friends strangers graph

Teorema teman dan orang asing adalah sebuah teorema matematika dalam cabang matematika yang disebut teori Ramsey.

Pernyataan

Misalkan sebuah pesta dihadiri oleh enam orang. Perhatikan dua orang di antaranya. Mereka mungkin baru pertama kali bertemu—dalam hal ini kita akan menyebut mereka orang asing satu sama lain; atau mereka mungkin sudah pernah bertemu sebelumnya—dalam hal ini kita akan menyebut mereka kenalan satu sama lain. Teorema ini menyatakan:

Dalam pesta apa pun yang dihadiri oleh enam orang, setidaknya tiga orang di antaranya adalah (secara berpasangan) saling menjadi orang asing atau saling menjadi kenalan.

Konversi ke dalam konteks teori graf

Bukti dari teorema ini hanya memerlukan tiga langkah logika. Akan lebih mudah untuk menyatakan masalah ini dalam bahasa teori graf.

Misalkan sebuah graf memiliki 6 simpul dan setiap pasang simpul (yang berbeda) dihubungkan oleh sebuah sisi. Graf seperti ini disebut graf lengkap (karena tidak bisa ditambahkan sisi lagi). Sebuah graf lengkap dengan $n$ simpul dilambangkan dengan simbol $K_n$.

Sekarang, ambil sebuah $K_6$. Graf ini memiliki total 15 sisi. Misalkan ke-6 simpul tersebut mewakili 6 orang di dalam pesta kita. Misalkan sisi-sisinya diberi warna merah atau biru secara berurutan, bergantung pada apakah kedua orang yang diwakili oleh simpul yang terhubung oleh sisi tersebut saling menjadi orang asing atau saling menjadi kenalan. Teorema ini sekarang menegaskan:

Bagaimana pun cara Anda mewarnai 15 sisi dari sebuah $K_6$ dengan warna merah dan biru, Anda tidak akan dapat menghindari kemunculan segitiga merah—yaitu segitiga yang ketiga sisinya berwarna merah, mewakili tiga pasang orang yang saling asing—atau segitiga biru, mewakili tiga pasang orang yang saling mengenal. Dengan kata lain, warna apa pun yang Anda gunakan, akan selalu ada setidaknya satu segitiga monokromatik (yaitu segitiga yang semua sisinya memiliki warna yang sama).

Bukti

Mari kita ambil satu simpul acak dan sebut saja simpul P. Dari simpul P ini, terdapat lima sisi (garis penghubung) yang menuju ke lima simpul lainnya. Masing-masing sisi tersebut diberi warna merah atau biru. Berdasarkan prinsip sarang burung merpati, setidaknya ada tiga sisi yang pasti memiliki warna yang sama. Logikanya sederhana: jika jumlah sisi berwarna merah kurang dari tiga (misalnya hanya ada satu atau dua), maka sisa sisi lainnya—yaitu minimal tiga sisi—pasti berwarna biru.

Katakanlah tiga sisi yang sewarna itu berwarna biru, dan ujung-ujung dari ketiga sisi ini terhubung ke simpul A, B, dan C. Sekarang, mari kita perhatikan hubungan antara simpul A, B, dan C itu sendiri (sisi AB, BC, dan CA). Jika salah satu saja dari ketiga sisi tersebut berwarna biru (misalnya sisi AB), maka sisi AB ini bersama dengan dua garis biru dari P (yaitu PA dan PB) akan langsung membentuk satu segitiga utuh berwarna biru. Sebaliknya, jika tidak ada satu pun dari sisi AB, BC, maupun CA yang berwarna biru, artinya ketiga sisi tersebut mau tidak mau harus berwarna merah. Akibatnya, simpul A, B, dan C akan otomatis membentuk sebuah segitiga utuh berwarna merah (segitiga ABC).

Makalah Ramsey

Daya tarik utama dari teorema ini terletak pada kesederhanaan argumennya yang mampu menghasilkan kesimpulan yang sangat kuat dan menarik. Pada tahun 1930, dalam sebuah makalah ilmiah berjudul On a Problem of Formal Logic, ahli matematika Frank Ramsey membuktikan sebuah teorema yang jauh lebih umum (kini dikenal sebagai teorema Ramsey). Kasus enam orang di atas hanyalah sebuah contoh kasus sederhana dari teorema tersebut. Karya Ramsey inilah yang kemudian meletakkan batu pertama bagi perkembangan teori Ramsey dalam cabang matematika kombinatorika.

Batasan teorema

Penting untuk dicatat bahwa kesimpulan dari teorema ini tidak berlaku jika jumlah orang di dalam pesta kurang dari enam orang. Untuk membuktikannya, kita bisa membuat pola pewarnaan pada graf lengkap dengan lima simpul ($K_5$) tanpa membentuk satu pun segitiga searah (monokromatik).

Caranya, gambarlah graf $K_5$ dalam bentuk pentagon (segi lima) yang mengelilingi sebuah bintang bertanduk lima (pentagram). Jika kita mewarnai semua sisi luar pentagon dengan warna merah dan semua sisi dalam pentagram dengan warna biru, kita tidak akan menemukan satu pun segitiga yang seluruh sisinya berwarna murni merah atau murni biru.

Oleh karena itu, angka 6 adalah jumlah minimal terkecil agar kondisi teorema ini pasti terpenuhi. Dalam teori Ramsey, fakta matematika ini dituliskan dengan notasi formal:

$R(3,3:2)=6.$

Pranala luar

• Party Acquaintances at cut-the-knot (membutuhkan Java)

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29439894 (2026-07-10T12:36:14Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.