A variant of the Guessing secrets game
Guy Louchard, Cristina Marini, F. Montagna, Giulia Simi · 2005
Abstract In [2], Chung et al. introduced the Guessing Secrets game. In [4] the authors introduce a variant of this game in which for each question the reference secret is chosen at random (with uniform distribution) by Responder. In this paper we investigate another variant in which Responder is required to answer truthfully to questions of the form How many secrets are there in X?, where X is a subset of the search space chosen by Questioner. We investigate the cost (number of questions needed) in the worst case, in the best case and in the average case. Key words and phrases: Guessing secrets, strategies, probabilistic analysis. 1