We study a guessing game where Alice holds a discrete random variable X, and Bob tries to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is however unreliable, and is incorrect with probability ϵ. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities - this question simultaneously minimizes all the guessing moments for any value of ϵ. In particular, this result settles a conjecture of Burin and Shayevitz. We further consider a more general setup where Bob can ask a multiple-choice M-ary question, and then observe Carole's answer through a noisy channel. When the channel is completely symmetric, i.e., when Carole decides whether to lie regardless of Bob's question and has no preference when she lies, a similar question about the ordered index of X (modulo M) is optimal. Interestingly however, the problem of testing whether a given question is optimal appears to be generally difficult in other symmetric channels. We provide supporting evidence for this difficulty, by showing that a core property required in our proofs becomes NP-hard to test in the general M-ary case. We establish this hardness result via a reduction from the problem of testing whether a system of modular difference disequations has a solution, which we prove to be NP-hard for M ≥ 3.

We study a guessing game where Alice holds a discrete random variable X, and Bob is trying to sequentially guess its value. Before the game begins, Bob can obtain side-information about X by asking an oracle, Carole, any binary question of his choosing. Carole's answer is unreliable, and is incorrect with probability ε. We show that Bob should always ask Carole whether the index of X is odd or even with respect to a descending order of probabilities - this question minimizes all the guessing moments for any value of ε. This in particular settles a conjecture of Burin and Shayevitz. We further count the number of optimal questions, and discuss some extensions including asymmetric channels from Carole to Bob and to multiple-choice questions.