先從一個貌似不相乾的西方曾經流行的遊戲“二十個問題”說起。遊戲是這樣的:俺心裡想一樣東西，你可以問俺二十個問題，然後猜俺心裡想的東西。你的問題必須是“是不是”這種形式的。比如，這個東西是不是可以放進冰箱裡?這個東西是不是活的?這個東西是不是能吃?諸如此類。對於你問的每一個問題，俺必須如實地回答“是”或者“不是”。你在二十個問題之內猜到了我想的東西就算贏。

　　這個遊戲的關鍵是在於如何有效地問你的問題。如果你問“明天是不是下雨”，那你肯定腦子進水了，可以不用往下看了。如果你第一個問題問的是“這東西是不是 iPhone 6”，這樣的問法顯然也效率不高，因為俺一旦說“NO”，你隻從大量的可能性中排除了一種可能，還是要面對剩下巨大的猜測空間。

　　這個遊戲可以大致等價於這樣一個數字遊戲。假設M是個大於1的正整數，俺倆在玩遊戲之前就商議確定好。俺在1到M之間任意想一個整數，你的任務是用最少的“是不是”形式的問題問出這個數是多少。

　　對於這個數字版的“二十個問題”遊戲，聰明的寶寶都會發現類似這樣的結論:M的數值越大，需要的問題越多。但愛鑽研的同學可能會想到另一個問題:對於一個給定的問問題策略，所需問題的“多”或“少”又是用什麽來衡量的呢?比方說，M=8，而你的問法是依次問如下問題:“這個數是不是1”，“這個數是不是2”，“這個數是不是3”，一直到“這個數是不是7”(如果問完“這個數是不是7”你覺得還需要問“這個數是不是8”的話，那請你去看韓劇吧)。在這種情況下，如果俺想的數字是1，你只需要一個問題就可以知道答案;而如果俺想的數字是8，你必須在問完7個問題之後才能知道答案。換句話說，即使問問題的策略確定，因為俺心裡那個神秘數字的不確定性，你所需要的問題數目也是不確定的。因此我們需要把這個數字版“二十個問題”遊戲更準確地描述出來，或者說，把在什麽意義上“最少”定義出來。