Problem 1466I - Загадка сфинкса, authored by gawry and Anadi, raised some interesting questions. The problem asks to find the maximum among $$$n$$$ $$$b$$$-bit numbers using $$$3n+3b$$$ questions of the form "is this number at least $$$x$$$"? ecnerwala described a solution using only $$$2n+2b-2$$$ questions. Here I will describe a solution using only $$$2n + 1.45b$$$ questions, using Fibonacci numbers instead of powers of two. In a sense this solution looks near-optimal, but there are better solutions when one of $$$n, b$$$ is much smaller than the other. In the other direction, a fairly simple argument shows that $$$n + b - 1$$$ questions are always needed in the worst case. I'll also sketch a proof that $$$n + b + 0.3 \min(n, b)$$$ questions are needed. This shows that no solution can hope to achieve e.g $$$1.1 n + 1.1 b$$$, but still leaves a wide gap to $$$2n + 1.45b$$$. The ideas here all arose in discussion with noncomlp. If you any ideas on how to improve the bounds in this post, please feel free to share them!
Terminology
Throughout this post, I will be using a straightforward reformulation of the original problem. In this reformulation, the state of the game is described by a multiset $$$P$$$ of integers all at least $$$2$$$. The game ends when $$$P$$$ is empty. In one move, we may name an integer $$$r$$$. Then one of two things happen: either (one occurrence of) $$$\max P$$$ is replaced by $$$r$$$, or $$$P$$$ is replaced by $$$[ p - r \mid p \in P, p - r \ge 2]$$$. The connection with the original problem comes from the observation that instead of remembering upper / lower bounds $$$u_i$$$ / $$$l_i$$$ on $$$a_i$$$ for each $$$1 \le i \le n$$$, it suffices to remember upper bounds $$$u_i$$$ and the greatest lower bound $$$L$$$ we've seen so far. We then consider the multiset $$$[ u_i - L + 1 \mid u_i > L]$$$, and observe that asking if $$$a_i \stackrel{?} \le x$$$ is like naming $$$r = x - L + 1$$$ in the reformulation. (This relies on the observation that we can always pick the $$$i$$$ which maximises $$$u_i$$$.) Thus the number of questions needed for $$$n, b$$$ is the number of moves needed to win the game starting from the multiset of size $$$n$$$ containing just the number $$$2^b$$$.
Fibonacci strategy
The problem hints to use powers of two, but let's instead Fibonacci numbers. Basically this is motivated by the observation that if $$$\min P = F_i$$$ and we name $$$F_{i-1}$$$, then if we end up subtracting $$$F_{i-1}$$$, $$$F_i$$$ becomes $$$F_{i-2}$$$, where I write $$$F_i$$$ for the $$$i$$$th Fibonacci number starting from $$$F_0 = 0$$$, $$$F_1 = 1$$$. Instead of starting from $$$P = [2^b, \ldots, 2^b]$$$, let's suppose we start from $$$P = [F_c, \ldots, F_{c+n-1}]$$$. I'll describe a solution which uses only $$$2n + c$$$ questions. This solve the original problem in $$$2n + 1.45b$$$ questions, where $$$1.45 = \log_2 \phi$$$, since $$$F_{n+1} \ge \phi^n$$$.
It is necessary to consider a more general class of multisets than the one above, since we might end subtracting Fibonacci numbers from much larger Fibonacci numbers. We'll assume we have some $$$c \ge 3$$$ and a string $$$S$$$ containing characters 1 and x, where every x is followed by a 1. The multiset $$$P = P(c, S)$$$ is then read off as $$$P(c, "") = \emptyset$$$
