Permasalahan Topi dengan Tak Hingga Orang

Permasalahan topi adalah salah satu teka-teki yang sering digunakan untuk bermain-main dengan logika. Ada cukup banyak invarian dari permasalahan ini. Di kuliah Paradox and Infinity dari MIT edX, saya menemukan salah satu yang menarik. Permasalahan ini menarik karena selain baru, juga memiliki solusi yang lumayan cute. Terlebih-lebih, solusi ini memancing diskusi filosofis yang menarik terkait strategi dan probabilitas.

Misalkan terdapat tak hingga banyaknya orang P_1,P_2,P_3,\dots. Setiap orang secara acak dipasangkan topi hitam atau putih di kepalanya dengan peluang masing-masing sama. Untuk setiap i \ge 1, setiap orang P_i dapat melihat warna topi P_{i+1},P_{i+2},P_{i+3},\dots sekaligus, namun tidak dapat melihat warna topi orang lain, termasuk dirinya sendiri. Selain itu, tidak boleh terdapat komunikasi di antara mereka setelah topi dipasangkan. Kemudian, pada saat bersamaan, setiap orang harus berteriak “Topi saya hitam!” atau “Topi saya putih!” secara bersamaan. Orang yang membuat pernyataan yang salah ditembak mati sementara sisanya dibebaskan. Namun, sebelum dipasangkan topi, mereka diperbolehkan untuk merencanakan suatu strategi (siapa teriak apa) agar yang selamat sebanyak mungkin orang dengan informasi topi yang bisa dilihat).

Apakah mungkin hanya berhingga orang yang ditembak mati?


Jawaban dari permasalahan di atas adalah Ya.

Pandang pemasangan topi pada tak berhingga orang tersebut sebagai barisan biner \langle t_1, t_2, t_3, \dots \rangle dengan t_i \in \{0,1\} untuk i=1,2,3,\dots. Interpretasi dari barisan ini adalah untuk setiap i=1,2,\dots, orang P_i menggunakan topi hitam jika t_i=1 dan putih jika t_i=0. Sebagai contoh, \langle 0,1,0,0,1,\dots \rangle berarti orang pertama, kedua, ketiga, keempaat, dan kelima berturut-turut memakai topi putih, hitam, putih, putih, dan hitam.

Salah satu strategi yang dapat digunakan orang-orang ini adalah dengan melihat orbit dari barisan-barisan biner. KIta perkenalkan istilah baru dari orbit dengan cara berikut:

Dua buah barisan biner \langle t_1,t_2,\dots \rangle dan \langle t_1',t_2',\dots \rangle dikatakan memiliki orbit yang sama jika hanya terdapat berhingga i \in \mathbb{N} demikian sehingga t_i \ne t_i'.

Hal pertama yang penting di sini adalah “memiliki orbit yang sama” tentunya merupakan relasi ekivalensi pada himpunan barisan biner:

  • sifat refleksif: setiap barisan memiliki orbit yang sama dengan dirinya sendiri.
  • sifat simetris: jika barisan (t_n) dan (t_n') memiliki orbit yang sama,  maka barisan (t_n') dan (t_n) memiliki orbit yang sama.
  • sifat transitif: jika barisan (t_n) dan (t_n') memiliki orbit yang sama dan barisan (t_n') dan (t_n'') memiliki orbit yang sama, maka barisan (t_n) dan (t_n'') memiliki orbit yang sama.

Dengan demikian, himpunan barisan biner dapat dipartisi berdasarkan orbit-orbitnya, yaitu menjadi kelas-kelas ekivalensinya. Dengan definisi orbit dan sifatnya ini, orang-orang ini sekarang dapat menyusun strategi sebagai berikut.

Untuk setiap orbit o, orang-orang ini secara bersama-sama menentukan wakil dari orbit o ini. Notasi (t_n^o) merupakan barisan yang menjadi wakil untuk orbit o. Setelah topi dipasangkan, setiap orang dapat melihat potongan barisan pemasangan topi untuk orang-orang berindeks lebih besar dari indeksnya sehingga bisa mengidentifikasi jenis orbit di mana barisan biner ini berada, sebut saja o. Kemudian, setelah mengingat kembali barisan (t_n^o) dan orang P_i akan berteriak “Topi saya hitam!” jika t_n^o(i)=1 dan “Topi saya putih!” jika t_n^o(i)=0.

Dengan strategi ini, banyak orang yang ditembak mati pasti hanya berhingga, sesuai dengan definisi orbit.

Advertisements

4 Comments

  1. Wah menarik 😀

    Saya jadi ada beberapa pertanyaan, yang sepertinya tidak dijelaskan:

    1. Apakah secara umum bisa terdapat sebuah “label” untuk setiap kelas orbit yang ada? Ini akan sangat memudahkan; misalnya, kita jadi bisa mengatakan dengan praktis bahwa barisan termasuk dalam orbit X. Salah satu cara sebenarnya adalah dengan memberikan X = “wakil” dari orbit tersebut. Hal ini menimbulkan pertanyaan kedua,

    2. Bagaimana cara mengonstruksi wakil dari sebuah kelas orbit? Apakah menentukan wakil dari semua kelas orbit membutuhkan waktu yang berhingga?

    Reply

    1. 1. Sepertinya saya tidak mengerti maksud “label” di sini. Sifat apa yang diinginkan dari “label” yang Anda maksud? Soalnya, sepertinya nama o untuk suatu orbit bukankah juga label?
      2. Nah, Ashar, setelah saya belajar set theory, sepertinya saya menemukan hal yang mengakibatkan perbedaan pada matematika yang populer sekarang dengan matematika konstruktivis yaitu salah satu aksioma di teori himpunan: Axiom of Choice (AC). Ini yang mengakibatkan kita bisa berbicara “suatu objek di set” ada tanpa perlu memikirkan konstruksinya. Sepertinya, loh, ya. Pengetahuan saya masih terbatas.
      Terkait pertanyaan Anda, ada beberapa orbit yang tidak bisa dikomputasi (setidaknya dengan kemampuan komputer zaman ini). Kita dapat menunjukkan bahwa banyaknya barisan f:\mathbb{N} \rightarrow \{0,1\} adalah uncountably infinite (f ini berkorespondensi dengan satu buah barisan biner). Kemudian, banyaknya fungsi g:\mathbb{N} \rightarrow \{0,1\} sehingga f \equiv g (ekivalensi orbit) itu sama banyaknya dengan banyaknya bilangan asli; dengan kata lain, countably infinite. Jadi, banyaknya orbit tetap uncountably infinite. Sebagaimana banyaknya program (bahkan mesin Turing) itu countably infinite, ada orbit yang tidak bisa dikonstruksi dengan mesin Turing.
      Setelah dipikirkan lagi, kalau seandainya kita selalu bisa mengkonstruksi wakil dari orbit o, sepertinya terjadi kontradiksi. Sebut saja ada sebuah mesin M yang menerima sembarang orbit o dan menghasilkan sebuah barisan (t_n^o), kita tulis M(o)=(t_n^o). Kalau kita pandang himpunan \{x: x=M(o) \}, himpunan ini juga uncountably infinite. Jadi, tetap ada wakil yang tidak bisa dikonstruksi menggunakan mesin Turing.
      Berarti diasumsikan manusia-manusia ini memiliki kemampuan superpower yang bisa memilih wakil dari masing-masing orbit. Saya tidak tahu cara memilihnya secara matematis. Ada kemungkinan juga tidak bisa. Namun, menggunakan AC, saya tetap bisa memilih wakil dari orbit. Menurut Ashar bagaimana? Apakah Ashar percaya dengan aksioma himpunan yang satu ini? 🙂

      Reply

      1. 1. Label yang saya maksud di sini adalah nilai (sederhana) yang bisa dikomputasi dari setiap orbit, sedemikian sehingga untuk setiap dua buah orbit dalam kelas yang sama, nilainya juga sama.

        Contohnya adalah dalam masalah isomorfisme pohon. Kita dapat mengkomputasi nilai yang sama untuk dua pohon yang isomorfis (= berada dalam kelas yang sama). Sumber: http://logic.pdmi.ras.ru/~smal/files/smal_jass08_slides.pdf, mulai slide no 13 (AHU algorithm).

        Dengan kata lain, label o di atas bukanlah yang saya maksud karena bukan merupakan suatu nilai yang terkomputasi.

        2. Bagaimana cara menunjukkan kebenaran kalimat ini?

        Kemudian, banyaknya fungsi g:\mathbb{N} \rightarrow \{0,1\} sehingga f \equiv g (ekivalensi orbit) itu sama banyaknya dengan banyaknya bilangan asli; dengan kata lain, countably infinite.

        Bagaimana cara mengenumerasi fungsi g tersebut?

      2. 1. Jika s adalah barisan biner dan [s] adalah kelas ekivalensinya, dengan aksioma AC (axiom of choice), ada fungsi f:\{[s]:s \in \{0,1\}^{\omega}\} \rightarrow \{0,1\}^{\omega} sehingga s \equiv f([s]) untuk sebarang s \in \{0,1\}^{\omega}. Fungsi ini ada. Saya pikir pada dasarnya fungsi ini bisa dikomputasi jika dan hanya jika label yang Anda maksud seperti isomorphism invariant tersebut bisa dikomputasi (buktinya saya belum punya). Sepertinya sih tidak bisa. Akan saya coba pikirkan.
        Catatan: Saya edit komentar saya dari pernyataan mesin dengan masukan barisan biner tak hingga tidak bisa halt. Bisa saja, kalau misalnya f(x)=x atau f(x)=x’ di mana x’ diperoleh dengan meng-flip 1000 bit pertama x.

        2. Bisa diurutkan dengan cara berikut: diberikan f, daftarkan semua i sehingga f(i) \ne g(i). Misalkan barisannya i_1,i_2,\dots,i_k, pasti berhingga, kemudian kode buat f adalah p_1^{i_1}p_2^{i_2} \dots p_k^{i_k} dengan p_i adalah bilangan prima ke-i. Jelas bahwa setiap f berkorespondensi dengan sebuah bilangan asli. Pada kasus barisannya kosong, petakan ke 1.

Leave a Reply

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