  `Twenty questions' is a guessing game played by two players: Bob thinks of an
integer between $1$ and $n$, and Alice's goal is to recover it using a minimal
number of Yes/No questions. Shannon's entropy has a natural interpretation in
this context. It characterizes the average number of questions used by an
optimal strategy in the distributional variant of the game: let $\mu$ be a
distribution over $[n]$, then the average number of questions used by an
optimal strategy that recovers $x\sim \mu$ is between $H(\mu)$ and $H(\mu)+1$.
We consider an extension of this game where at most $k$ questions can be
answered falsely. We extend the classical result by showing that an optimal
strategy uses roughly $H(\mu) + k H_2(\mu)$ questions, where $H_2(\mu) = \sum_x
\mu(x)\log\log\frac{1}{\mu(x)}$. This also generalizes a result by Rivest et
al. for the uniform distribution. Moreover, we design near optimal strategies
that only use comparison queries of the form `$x \leq c$?' for $c\in[n]$. The
usage of comparison queries lends itself naturally to the context of sorting,
where we derive sorting algorithms in the presence of adversarial noise.

Data Structures and Algorithms;Discrete Mathematics;Combinatorics