We consider a variant of the classical 20 question game with lies (also known as
the Ulam-R\' enyi game).
There are two players: Paul (the Questioner) and Carole (the Oracle).
Carole selects a number $x\in U=\{0,1,\dots,2^m-1\}$ without revealing it to Paul.
Paul asks membership questions of the form "Is $x\in S$?", where $S\subseteq U$.
Carole's aim is to maximize the number of questions Paul must ask.
She is allowed to lie up to $e$ times.
Paul wins if, after $q$ questions, exactly one value of $x$ remains possible; otherwise, Carole wins.
It is known [1] that Carole can win whenever $q<Q_{min}(2^m,e)$, where
$Q_{min}(2^m,e)=\min\{q~|~ 2^{q-m}\ge \sum_{i=0}^e {q\choose i}\}$.
We study the $k$-interval Ulam-R\' enyi game where each query set $S$ is the union of at most $k$ intervals.

Recently it was shown [2] that Paul can win the game with $e=3$ lies and $k=4$ intervals,
using $Q_{min}(2^m,e)$ questions for sufficiently large $m$.
In this paper, we show that three intervals suffice for Paul to win when $m=O(1)$.
It remains an open problem whether Paul can win using three-interval sets for all values of $m$.

References.

[1] E.~R. Berlekamp. Block coding for the binary symmetric channel with noiseless,
delayless feedback. In {\em Error-Correcting Codes}, pp. 61--68. Wiley, 1968.

[2] F.~Cicalese and M.~Rossi. On the multi-interval {U}lam-{R}{\'{e}}nyi game: For 3 lies 4
intervals suffice. {\em Theor. Comput. Sci.}, 809:339--356, 2020.