Analiz ve Çözüm Yolu

Çarkı iki kere döndürünce her biri \(\frac{1}{\mathbf{N}^2}\) olasılıkla denk gelebilecek \(N^2\) tane çift oluşuyor. Her çift bir kelimeye karşılık geliyor. Tüm farklı kelimelere bakalım. Bir kelimenin seçilmesi olasılığı, X o kelimeyi üreten çiftlerin sayısı olmak üzere \(\frac{X}{\mathbf{N}^2}\) dir.

Her soru sorduğumuzda olası gizli kelimeler kümesi iki kümeye bölünüyor. Sonra cevaba göre (evet ya da hayır) bu kümelerden biriyle devam ediyoruz. Kümede sadece bir kelime kalıncaya dek bölünme devam ediyor. Kelime kümeleri, yaprakları çarkın ürettiği olasılıklarla farklı kelimeler olan bir ikili ağaç oluşturuyor. yapmamız gereken yaprak uzaklığını (soru sayısı) minimize eden bir ağaç bulmak. Bu Huffman algoritmasına benziyor. Yani yapmamız gereken tek şey olasıklarıyla birlikte bir kelime kümesi ile Huffman algoritmasını uygulamak.

Analysis and Guide for Solution

Spinning the wheel twice leads to \(\mathbf{N}^2\) pairs of the first and the second sections with \(\frac{1}{\mathbf{N}^2}\) probability each. Every pair has a corresponding word it generates. Let's consider all distinct words. A probability for a word to be chosen is \(\frac{X}{\mathbf{N}^2}\), where X is the number of pairs that generate this word.

Every time you ask a question a set of possible secret words is split into two sets. Then depending on an answer you continue with one of those sets (either yes or no). You keep splitting until there is the only word in a set. The word sets form a binary tree which leaves are distinct words with probabilities generated by the wheel. Your task is to find a tree which minimizes the expected leaf path length (number of questions you ask). This resembles the Huffman coding algorithm. Thus all you have to do is to implement it having a set of words with probabilities.