  Alice holds an random variable $X$, and Bob is trying to guess its value by
asking questions of the form "is $X=x$?". Alice answers truthfully and the game
terminates once Bob guesses correctly. Before the game begins, Bob is allowed
to reach out to an oracle, Carole, and ask her any yes/no question, i.e., a
question of the form "is $X\in A$?". Carole is known to lie with a given
probability $p$. What should Bob ask Carole if he would like to minimize his
expected guessing time? When Carole is always truthful ($p=0$), it is not
difficult to check that Bob should order the symbol probabilities in descending
order, and ask Carole whether the index of $X$ w.r.t this order is even or odd.
We show that this strategy is almost optimal for any lying probability $p$, up
to a small additive constant upper bounded by a $1/4$. We discuss a connection
to the cutoff rate of the BSC with feedback.
