  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 $\epsilon$. 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 $\epsilon$. 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\geq
3$.
