Tags

4. Bongkar Sandi

Pembuat soal: Brian Marshal

URL:

Subsoal 1

Batasan: N = 2, maksimal pertanyaan 100.
Solusi: Coba semua kemungkinan sandi (cuma ada 100).

Subsoal 2 hingga 5:
Tebak banyaknya kemunculan masing-masing digit dengan tebakan-tebakan berikut:

? 000000
? 111111
? 222222
...
? 888888

Dari masing-masing tebakan, kita memperoleh frekwensi kemunculan masing-masing digit dari 0 hingga 8. Banyaknya kemunculan digit 9 pada sandi adalah 6 dikurangi dengan total banyak kemunculan digit-digit lain.

Banyak tebakan sejauh ini: 9

Asumsikan M sebagai banyaknya digit yang belum tertebak. Di awal, M = 6. Tentu saja kita dapat mengabaikan ke-(6-M) digit yang sudah tertebak. Asumsikan S adalah himpunan digit-digit yang muncul pada M digit tersebut tanpa pengulangan.
1. Jika banyak elemen S adalah 0, seluruh digit sudah tertebak. Outputkan solusi.
2. Jika banyak elemen S adalah 1, seluruh digit yang belum tertebak pasti adalah elemen dari S tersebut. Banyak tebakan tambahan yang diperlukan = 0.
3. Jika banyak elemen S lebih dari 1, ambil dua digit dengan frekwensi terbanyak. Sebut saja a dan b. Misal c merepresentasikan digit-digit yang sudah tertebak sejauh ini dan * merepresentasikan digit-digit yang belum tertebak.
Contoh:

c**c**

Jawaban dari pertanyaan:

? aaaaaa

adalah banyaknya digit a
Akan tetapi, jika kita mengubah digit-digit pada posisi * dengan b secara bergantian, kita mendapatkan sesuatu yang menarik (masih pada kasus c***c*):

? abaaaa

Jawaban dari pertanyaan tersebut:
1. Lebih banyak dari jawaban ? aaaaaa jika * yang pertama adalah b
2. Sama dengan jawaban ? aaaaaa jika * yang pertama bukan a maupun bukan b
3. Lebih sedikit dari jawaban ? aaaaaa jika * yang pertama adalah a
(pembuktian diserahkan kepada pembaca sebagai latihan)

Oleh karena itu, untuk mengetahui digit-digit mana saja yang ditandai dengan * yang merupakan a dan b, kita bisa buat pertanyaan berikut (masih pada kasus c***c*):

? abaaaa
? aabaaa
? aaaaba
? aaaaab

Akan tetapi, pertanyaan terakhir tidak perlu ditanyakan. Mengapa? Jika kita sudah memperoleh semua posisi a dan b pada 3 jawaban pertama, maka * yang terakhir pasti bukan a maupun b. Jika kita sudah memperoleh semua kecuali satu posisi a dari jawaban-jawaban 3 pertanyaan pertama, * terakhir pasti a. Selain itu, * terakhir pasti b. Oleh karena itu, kita hanya butuh M – 1 pertanyaan. Untuk kasus c***c* tadi:

? abaaaa
? aabaaa
? aaaaba

Setelah mendapatkan posisi-posisi a dan b, buang a dan b dari S, ubah * menjadi a atau b jika karakter tersebut sebenarnya salah satu dari mereka, solve subpermasalahan baru ini (kembali ke atas).

Dengan cara tersebut, kasus terburuk tercapai ketika digit-digit dari sandi berbeda-beda semua, yaitu 18 pertanyaan.
Secara intuitif, jika digit-digit berbeda-beda, banyaknya pertanyaan yang dibutuhkan adalah:

9 (untuk mengetahui frekwensi masing-masing digit) + 5 (di awal, M = 6) + 3 (karena tinggal M = 4) + 1 (karena M = 2).

Jika ada digit yang muncul lebih dari sekali, misalkan saja ada sebuah digit muncul dua kali. Banyaknya pertanyaan akan menjadi semakin sedikit:

9 + 5 + 2 (karena sudah ada 3 posisi yang tertebak, yaitu 2 (karena digit dengan frekwensi maksimum muncul 2 kali) + 1 (karakter satu lagi) + 0 (karena banyaknya elemen S tinggal 1, lihat kasus 2)

Advertisements