Yalancının sayısını tahmin etme oyunu, $A$ ve $B$ oyuncuları arasında oynanan bir oyundur. Oyun, her iki oyuncuya da önceden bildirilen $k$ ve $n$ pozitif tam sayılarına göre oynanıyor.
Oyunun başında $A$ oyuncusu $1 \leq x \leq N$ olacak şekilde $x$ ve $N$ tam sayılarını seçer ve $N$ sayısının ne olduğunu $B$ oyuncusuna dürüstçe söyler, fakat $x$ sayısını gizli tutar. Daha sonra $B$ oyuncusu $A$ oyuncusuna sorular sorarak $x$ sayısı hakkında bilgi edinmeye çalışır. Her defasında $B$ oyuncusu pozitif tam sayılardan oluşan bir $S$ kümesi belirler (bu küme daha önceki bir soruda geçen küme de olabilir) ve $A$ oyuncusuna ``$x$ sayısı $S$ kümesinin elemanı mıdır?'' diye sorar. $B$ oyuncusu istediği kadar soru sorabilir. $A$ oyuncusu istediği kadar yalan söyleyebilir, fakat herhangi ardışık $k+1$ cevabından en az biri doğru olmak zorundadır.
$B$ oyuncusu istediği kadar soru sorduktan sonra en fazla $n$ pozitif tam sayıdan oluşan bir $X$ kümesi belirlemelidir. Eğer $x$ sayısı $X$ kümesinin elemanı ise $B$ oyunu kazanır, aksi durumda kaybeder.
- $n \geq 2^k$ ise, $B$ oyuncusunun oyunu kazanmayı garantileyebileceğini kanıtlayınız.
- Yeterince, büyük her $k$ tam sayısı için, $B$ oyuncusunun oyunu kazanmayı garantilemesinin mümkün olmadığı bir $n \geq 1,99^k$ tam sayısının bulunduğunu kanıtlayınız.
