Permainan Menebak Angka
Wati dan Budi memainkan permainan tebak angka. Wati meminta Budi untuk memikirkan suatu angka dari 0 sampai dengan 15. Untuk bisa menebak angka ini, Budi diminta menjawab tujuh pertanyaan berikut dengan jawaban ya atau tidak. Budi diperbolehkan berbohong paling banyak satu kali ketika menjawab.
Tujuh pertanyaan yang Wati ajukan, semuanya berbentuk: apakah bilangan yang kamu pikirkan ada dihimpunan ? dengan himpunan
berturut-turut adalah ketujuh himpunan berikut:
Jawaban Budi dari ketujuh pertanyaan di atas adalah: ya, ya, ya, ya, tidak, tidak, ya. Setelah mencoret-coret sesuatu di kertas, satu menit berikutnya Wati mengumumkan bahwa Budi telah berbohong ketika menjawab pertanyaan ketiga dan angka yang dipikirkan Budi adalah 13! Budi membenarkan apa yang dikatakan Wati.
Karena merasa penasaran Budi ingin mencobanya sekali lagi. Setelah memikirkan suatu angka, berikut adalah jawaban Budi atas pertanyaan-pertanyaan yang sama seperti pada permainan yang pertama: tidak, ya, tidak, tidak, ya, tidak, tidak. Bisakah anda membantu Wati untuk menebak apa angka yang dipikirkan Budi?
Solusi Wati
Berikut adalah cara Wati untuk menentukan bilangan apa yang dipikirkan Budi. Untuk setiap jawaban Budi, Wati menuliskan angka 1 jika Budi menjawab ya dan 0 jika Budi menjawab tidak. Ketujuh kombinasi angka 1 dan 0 tersebut ditempatkan kedalam daerah-daerah yang dipisahkan oleh tiga buah lingkaran seperti yang terlihat pada gambar berikut
dengan bilangan 1 sampai dengan 7 menunjukkan didaerah mana angka 1 atau 0 harus ditempatkan ketika Wati mendengar jawaban Budi. Sebagai contoh, pada permainan pertama Budi menjawab ya, ya, ya, ya, tidak, tidak, ya yang berarti Wati memperoleh barisan bilangan 1,1,1,1,0,0,1 yang akan ditempatkan sesuai pada gambar di atas. Setelah ditempatkan sesuai pada tempatnya diperoleh sebagai berikut
Jika Budi tidak berkata bohong, angka 1 pada setiap lingkaran muncul sebanyak genap kali. Pada gambar di atas lingkaran sebelah kanan memuat 1 sebanyak 4 kali (genap), sedangkan lingkaran kiri dan bawah muncul sebanyak ganjil kali. Ini menandakan Budi bohong pada pertanyaan yang sekaligus termuat di lingkaran kiri dan lingkaran bawah tapi tidak termuat di lingkaran kanan, yakni pertanyaan nomor 3! Dengan demikian jika Budi jujur maka Budi harus menjawab tidak pada pertanyaan ketiga sehingga angka 1 harus digantikan dengan angka 0 pada daerah untuk pertanyaan nomor 3. Sekarang untuk mengetahui bilangna Budi yang sebenarnya, Wati cukup membaca empat angka pertama pada lingkaran, yakni 1101 dan mengubahnya dari biner ke desimal untuk mendapatkan 13.
Bagaimana Metode Ini Bisa Jalan?
Misalkan Budi memberi jawaban dengan masing-masing
bisa bernilai 0 atau 1 untuk setiap
. Jika Budi tidak bohong maka berdasarkan gambar lingkaran yang paling atas, himpunan-himpunan
masing-masingnya memiliki angka 1 sebanyak genap kali. Kondisi ini kita bisa tuliskan sebagai
dimana persamaan ini kita tinjau sebagai persamaan di lapangan yang memiliki dua unsur 0 dan 1. Ingat bahwa di
penjumlahan bersifat komutatif dan
dan
.
Sistem persamaan di atas dapat kita tinjau sebagai persamaan matriks
dengan . Dari sini kita lihat bahwa “himpunan jawaban jujur” adalah kernel dari
dan merupakan subruang dari
. Karena setiap ruang vektor memiliki basis, kita bisa menanyakan berapa dimensinya dan apa basisnya. Perhatikan bahwa ketiga kolom terakhir dari
bebas linier. Dengan demikian
dan akibatnya kernel dari
berdimensi
.
Perhatikan bahwa matriks dapat dilihat sebagai blok-blok matriks
untuk suatu matriks
. Untuk
, perhatikan bahwa
Dengan demikian baris-baris dari merupakan bagian dari jawaban-jawan jujur. Akan tetapi karena
dan empat kolom pertama dari bebas linier. Dengan demikian ruang baris dari G, juga berdimensi 4. Ini menunjukan bahwa himpunan semua jawaban jujur adalah semua kombinasi linier dari baris-baris
.
Dari sini kita bisa melihat bahwa bilangan-bilangan 0 sampai dengan 15 harus kita “sandikan” sebagai unsur di ruang baris dengan tambahan syarat bahwa meskipun telah disandikan kita masih mengenalinya dengan mudah sebagai bilangan 0 sampai dengan 15. Cara yang kita lakukan sebagai berikut: untuk setiap bilangan dari 0 sampai dengan 15 tersebut, pertama kita tuliskan sebagai bilangan biner dengan panjang 4, katakan
. Kemudian kita sandikan ia sebagai
. Sebagai contoh, untuk bilangan 5, dalam bilangan biner dengan panjang 4 ia bisa kita tuliskan sebagai
. Sehingga 5 kita sandikan menjadi
Dengan melakukan hal serupa seperti di atas untuk semua bilangan 0 sampai dengan 15 kita peroleh tabel berikut:
Kemudian pertanyaan Wati yang ke-i bernilai sama dengan menanyakan apakah digit ke-i pada bilangan yang telah disandikan merupakan angka 1. Sebagai contoh pertanyaan kedua Wati senilai dengan menanyakan apakah bilangan yang telah disandikan digit keduanya 1. Dari tabel di atas kita lihat bahwa bilangan-bilangan yang digit ke-2 nya 1 adalah bilangan-bilangan di himpunan . Dengan melakukan hal serupa untuk pertanyaan pertama sampai ketujuh maka kita peroleh semua pertanyaan Wati yang diberikan pada bagian pertama tulisan ini.
Masih ada pertanyaan yang tersisa. Darimana kita tahu bahwa dengan melakukan semua hal di atas Wati pasti selalu bisa menebak angka Budi asalkan Budi berbohong tidak lebih dari satu kali? Kita katakan dua string berjarak jika mereka berbeda di
buah posisi. Jika kita lihat setiap string dengan 7 digit pada tabel di atas, setiap dua string sedikitnya berjarak 3. Sebagai contoh, string untuk 8 dan 12 yakni 1000101 dan 1100110 berjarak 3 karena mereka berbeda dalam 3 posisi, yakni pada posisi ke 2,6 dan 7. Misalkan Budi memberikan string
dengan panjang 7 sebagai jawaban dari Wati. Jika Budi berbohong maka
ini didapat dari suatu string
dari tabel yang salah satu digitnya diubah (dari 0 ke 1 atau sebaliknya). Wati bisa menyimpulkan bahwa si
ini berasal dari
jika dan hanya jika
adalah satu-satunya string di tabel yang berjarak 1 dari
. Jika ada dua string
di tabel yang berjarak 1 terhadap
maka
paling banyak berjarak 2. Tapi ini tidak mungkin karena tadi sudah kita lihat bahwa setiap dua string di tabel berbeda sedikitnya berjarak 3!. Dari sini disimpulkan bahwa apapun angka Budi, asalkan ia tidak berbohong lebih dari satu kali, Wati pasti bisa menebaknya.
Bisa kita lihat jarak minimum memegang peranan yang sangat penting dalam solusi permasalahan ini. Secara teoretis, jika kita mempunyai himpunan yang jarak minumumnya maka Budi boleh berbohong spaling banyak
kali agar Wati masih bisa menebak angka Budi. Bagaimana mengkonstruksi himpunan dengan jarak
yang besar dapat dipelajari lebih lanjut di buku-buku yang membahas tentang error correcting codes.