Saya tahu kalau kamu tahu apa yang saya tahu

Pernyataan ini mengandung logika yang cukup membingungkan. Namun, pada kenyataannya aplikasi dari logika ini sangat memengaruhi teori pertukaran informasi. Sebagai contoh kita akan mulai dari teka-teki ini:

 

Tiga orang siswa bertopi berbaris sehingga setiap orang hanya bisa melihat orang yang ada didepannya. Topi yang mereka kenakan diambil secara acak dari lima topi yang tersedia berwarna dua merah dan tiga biru, tetapi tiap orang tidak tahu warna topi yang mereka kenakan. Kemudian seorang guru menanyai tiap orang apakah tahu warna topi yang dikenakan mulai dari siswa paling belakang. Jawaban yang didapat berturut-turut adalah: tidak, tidak, dan ya. Dengan asumsi bahwa setiap siswa cerdas dan jujur, apa warna topi siswa terdepan?

 

Masalah utama teka-teki ini adalah apa yang membuat siswa terdepan dapat mengetahui warna topi yang ia kenakan. Nomori mulai dari siswa terdepan berturut-turut dengan 1,2,3. Informasi yang didapatkan siswa 1 hanya berasal dari siswa 2 dan 3, sehingga dapat dipastikan bahwa informasi-informasi inilah yang membuatnya bahwa ia tahu warna topi yang ia kenakan. Jadi mari kita telusiri kesimpulan yang diambil tiap anak.

 

Karena siswa 3 menjawab tidak, maka paling tidak ada satu biru yang dikenakan dua siswa didepannya, karena jika tidak ia bisa menyimpulkan topi yang dikenakannya biru. Pada giliran siswa 2 yang mengambil kesimpulan, ia mendapat informasi berdasarkan siswa 3, sehingga jika siswa 1 bertopi merah ia bisa menyimpulka bahwa ia bertopi biru, tetapi ia menjawab tidak tahu, berarti ia melihat siswa 1 bertopi biru. Inilah alasan mengapa ia menjawab tidak tahu. Siswa satulah yang paling susah mengambil keputusan. Pertama ia berpikir bahwa karena siswa 3 menjawab tidak, maka paling tidak satu orang didepannya bertopi biru. Kemudian ia berpikir bahwa kalau saya menggunakan topi merah siswa dua pasti menjawab ya, dia tahu warna topi yang dikenakannya, tetapi ia menjawab tidak tahu karena topi saya berwarna biru, sehingga ia tidak bisa menyimpulkan warna topi yang dikenakannya. Berdasarkan argumentasi inilah siswa 1 dapat menyimpulkan bahwa ia tahu warna topi yang dikenakannya yang tidak lain adalah biru.

 

Tampak bahwa informasi berantai ini sangat memengaruhi kesimpulan yang dapat diambil untuk tiap siswa. Pengambilan kesimpulan seperti ini sangat penting, karena bisa jadi pengambilan kesimpulan secara positif tidak pernah terjadi seperti pada contoh berikunya.

 

Asumsikan cerita ini berlangsung pada zaman dimana keterbatasan masih sangat kentara. Dua kompi tentara yang bermarkas di puncak dua buah bukit yang beriringan sedang mempersiapkan penyerangan kompi musuh yang berada di lembah antara dua dua bukit itu. Dua jendral itu memutuskan untuk bersama-sama menyerang atau tidak. Keputusan baru diambil ketika jendral yang satu sudah tahu bahwa jendral lainnya juga tahu kalau penyerangan akan dilakukan. Cara mereka mengirim informasi adalah hanya dengan menggunakan burung merpati pos. Jadi misalkan jendral pertama sudah memutuskan akan melakukan serangan, maka ia akan mengirimkan pesan berisi, “serangan dilakukan pada saat fajar” dan dikirim ke jendral kedua dengan merpati pos. Lalu bila jendral kedua sudah menerima pesan itu ia harus mengirimkan pesan balasan yang isinya memberitahukan bahwa ia telah menerima pesan jendral pertama itu. Namun, jendral kedua masih menunggu konfirmasi dari jendral pertama yang meyakinkannya bahwa jendral pertama sudah tahu bahwa jendral kedua sudah mendapatkan pesan jendral pertama. Jendral pertama pun mengirimkan konfirmasi balasan. Jika konfirmasi balasan ini terus dilakukan menggunakan merpati pos, apakah serangan akan dilakukan? Berapa jumlah total konfirmasi balasan sebelum akhirnya dilakukan?

 

Masalah ini merupakan masalah klasik yang pengembangannya memunculkan teori baru yang dikenal sebagai teori informasi. Jawaban dari dilema kedua jendral itu mudah: karena setiap jendral harus yakin bahwa informasi yang didapatkan keduanya bernilai sama, maka konfirmasi balasan akan terus dilakukan tak terhingga kali. Jadi penyerangan tidak pernah terjadi. Pada kasus ini terlihat bahwa kondisi saya tahu bahwa kamu tahu apa yang saya tahu tidak pernah tercapai. Alasannya adalah karena informasi yang dibutuhkan kurang. Pada masalah sebelumnya setiap siswa bisa mendengar secara langsung kesimpulan siswa yang ada di belakangnya, tetapi masalah kali ini informasi tidak dilakukan secara langsung. Pengiriman pesan melalui merpati tidak membuat kedua jendral dapat melihat kondisi masing-masing. Agar penyerangan tetap dapat dilakukan kita perlu memperbaiki metode pengiriman pesan dan konfirmasi balasan ini. Salah satu caranya adalah dengan menyalakan obor agar jendral pada bukit di seberang dapat melihatnya. Ketika jendral pertama memutuskan melakukan serangan, ia mengirim pesan lewat merpati, “serangan akan dilakukan saat fajar, nyalakan obor ketika kamu menerima pesan ini dan saya juga akan menyalakan obor ketika saya lihat bahwa obormu telah menyala.” Dengan metode seperti ini jasa merpati hanya dibutuhkan sekali, lainnya dari nyala obor yang dapat dilihat di bukit seberang.

 

Masalah seperti ini bahwa pernah diajukan untuk menjadi masalah IMO tahun 1991.

 

Setiap siswa A dan B memberi tahu seorang guru suatu bilangan bulat positif, tetapi tidak seorang siswa pun tahu bilangan pilihan siswa lain. Guru itu kemudian menuliskan dua bulat positif di papan tulis dan menyatakan pada mereka bahwa salah satu dari bilangan itu merupakan jumlah dua bilangan yang telah diberitahukan padanya. Lalu ia bertanya pada A, “apakah kamu tahu jumlah dua bilangan itu?” jika jawabannya “tidak,” maka guru bertanya kepada B pertanyaan yang sama, begitu seterusnya.

Dengan asumsi bahwa kedua siswa itu cerdas dan jujur, buktikan bahwa ada suatu saat ketika jawaban dari salah satu siswa, “ya.”

 

Solusi dari masalah ini berdasarkan SAV03.

 

Untuk dapat memodelkan masalah ini secara matematika kita perlu mengenalkan beberapa simbol. Misalkan A dan B memberitahu si guru a, dan b berturut-turut. Misalkan S1,S2 adalah bilangan yang ditulis si guru di papan tulis dengan 0 < S1 < S2. simbol d kita misalkan selisih S2 dan S1. Kita akan menyelesaikan masalah ini secara kontradiksi, sehingga misalkan bahwa semua jawaban berturut-turut siswa-siswa itu adalah “tidak.” Juga misalkan AKk, BKk adalah kesimpulan yang berturut-turut A,B dapat ambil setelah jawaban “tidak” berturut-turut B,A.

 

Jawaban “tidak” A yang pertama membuat B berkesimpulan 0 < a < S­1. Jika tidak, a >= S1, maka a + b > S1, sehingga A tahu bahwa a + b = S2 yang membuatnya menjawab “ya.” Jadi

 

BK1: 0 < a < S1.

 

Jawaban “tidak” pertamanya B ini akan membuat A mengambil kesimpulan

 

AK1: d < b < S1.

 

Misalkan tidak demikian, dari informasi B, A tahu 0 < b < S1. Argumentasi yang dikembangkan A adalah “B tahu 0 < b < S1 dan jika b <= d, maka B juga tahu

 

a + b <= a + d < S1 + (S2 – S1) = S2.

 

Jadi satu-satunya kemungkinan a + b adalah S1, sehingga B akan menjawab ‘ya,’ tetapi ternyata tidak.”

 

Setelah jawaban “tidak” A yang kedua, dengan alasan serupa seperti sebelumnya, B akan mengambil kesimpulan

 

BK2: 0 < a < S1 – d,

 

sedangkan kesimpulan A

 

AK2: 2d < b < S1.

 

Proses ini berlanjut sampai tak hingga, dan setelah jawaban “tidak” kedua siswa berurutan ke-k, kita dapatkan

 

BKk: 0 < a < S1 – (k – 1)d,

AKk: kd < b < S1.

 

Karena d positif, ada suatu k sehingga kd > S1. Pada saat ini A akan tahu bahwa b < S1, dilain pihak, b > kd > S1. Kontradiksi. Jadi akan ada jawaban “ya” dari salah satu siswa.

 

Masalah diatas sangat kental matematikannya dan sudah ditemukan bentuk yang lebih umumnya. Masalah di bawah ini persis seperti masalah pertama.

 

Ada 13 pakar logika bertopi berkumpul melingkar dalam suatu ruangan. Pada beberapa topi itu tertera huruf X yang cukup besar sehingga pakar yang mengenakan topi itu tidak bisa lihat huruf X itu, sedangkan pakar lain bisa. Sebelum memasuki ruangan setiap pakar telah diberi informasi bahwa paling tidak ada satu pakar yang topinya ber-X. masalahnya adalah setiap pakar harus memutuskan apakah topinya ber-X atau tidak.

 

Pengambilan keputusan itu harus dilakukan dengan aturan tertentu. Misalkan keputusan diambil pada beberapa putaran. Dalam setiap putaran pakar yang belum bisa memutuskan harus berbicara. Mereka bergiliran bicara sesuai arah jarum jam. Apa yang boleh mereka ungkapkan adalah salah satu dari ungkapan:

 

  1. Saya tidak tahu apakah topi saya ber-X.
  2. Topi saya tidak ber-X.
  3. Topi saya memang ber-X dan paling tidak ada satu pakar lain yang topinya ber-X, tetapi ia belum bisa memutuskan.
  4. Topi saya ber-X dan setiap pakar lain yang topinya ber-X sudah mengatakannya.

 

Setelah seorang pakar memutuskan topinya ber-X atau tidak, pada setiap putaran berikutnya ia tidak boleh ikut berbicara. Jika pada putaran pertama empat orang pakar berhasil mengambil keputusan, pada putaran kedua tiga pakar melakukan hal yang sama, tetapi salah seorang dari mereka menungkapkan ungkapan 3, sedangkan pada putaran ketiga enam pakar sisanya berhasil membuat keputusan, tentukan pakar mana saja yang topinya ber-X.

 

Selamat mencoba, pastikan kamu mengoordianasikan informasi dengan baik.

 

 

 

Referensi

 

[SAV03]       Savchev, Svetoslav; Andreescu, Titu, Mathematical Miniatures, MAA, 2003.

[SHA95]       Shasha, Dennis, (terjemahan) Teka-teki Petualangan Dr. Ecco, Erlangga, 1995.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s