Finding the larger number with a minimal number of questions

Question

Bob and Charlie each secretly chose a 300 decimal-digit number, possibly with leading zeroes. We want to find the value of the larger number. We may address each question to either Bob or Charlie, and ask if their number is $\ge x$ for any $x$ we pick. How can we achieve this using 1012 questions?

Answer 1

I can do it in

1043 questions

It's still a little short of the target of 1012, but it's getting closer.

First, a few simplifications to the problem. We can think of the current state, after some guesses and responses, as being a pair of intervals in which each person's number must be contained. These intervals can be summarized in 4 numbers: [b_min, b_max, c_min, c_max].

If Bob's minimum is smaller than Charlie's minimum, then Bob's minimum is irrelevant: the answer will never be below Charlie's minimum. So the only minimum that matters is the larger minimum. So we only need three numbers: [min, b_max, c_max].

The absolute value of the intervals matters doesn't really matter, only the widths of the intervals matter. The optimal solution can just be shifted accordingly. So we only need two numbers: [b_width, c_width].

Finally, it doesn't matter which of Bob and Charlie have which interval. All that matters is the size of the smaller-width interval and the larger-width interval. Let's track the two numbers: [s_width, l_width].

Note that we should only ever ask a question to the person with the larger-width interval. It will leave us in a strictly better position than asking the same question of the person with the smaller width interval.

Now, for the protocol.

Suppose the starting state is [x, x] for some large x. We will ask the question ">= x/2?" The worse answer is no, putting us in the state [x/2, x]. We now ask ">= x/4?". The worse answer is yes, putting us in the state [x/4, 3x/4]. We repeat k times, dividing our question by 2 each time. receiving the worst-case answer of yes all subsequent times. We are now in the state $[x/2^k, x/2+x/2^k]$.

We now do something different:

We now ask the question ">= $x/2^k$?", not dividing by 2. If the answer is yes, we reach the state $[0,x/2]$. If the answer is no, we are in the state $[x/2^k, x/2^k]$, and we can recurse.

Notice that in the scenario where the final answer was yes,

We have eliminated one person's number as a candidate, and we can proceed via binary search, finishing in $\log_2(x)+k$ questions.

If the final answer was no,

We have gone from $[x, x]$ to $[x/2^k, x/2^k]$ in k+1 questions, running one question behind binary search.

Let f(x) represent the difference between the number of questions we ask, and the binary search amount $\log_2(x)$.

Via this protocol, we achieve

$f(x) = \max(f(x/2^k)+1,k)$. To choose k optimally, we will select k to be smallest integer such that $k(k+1)/2>\log_2 x$. We then achieve $f(x)=k$.

For the specific scenario $x=10^{300}$,

The optimal $k$ is 46, and $\log_2 x$ is 996.57+, resulting in 1043 questions.

---

To reach the ultimate target of 1012, I think the protocol needs to be adapted to be more continuous, and less of a jump between the two different kinds of questions.

Answer 2

Sketch:

I'll try to convey the main idea without the need to go into any unwarranted detail.

We'll do a bisection with one twist.

We have two numbers from a range of about $2^{997}$ and $997+15$ questions. For ease of reference we'll assume all questions are "is your number greater than $x$" and a "yes question" is one answered with yes, such that the corresponding interval of values still possible shrinks from the left and a "no question" shrinks it from the right.

Let us call $B$ and $C$ the intervals of values still possible for either number and $I$ their intersection. We'll roughly bisect $I$ with every question, always asking the player whose interval reaches farther right (the "active player"). The bit by which the active player's interval exceeds $I$ on the right we'll call $E$. The trick will be to use what little slack we have to keep $E$ under control, i.e. the same order of magnitude as $I$.

We note that the active player stays the same upon yes questions and changes upon no questions. The effect of a yes question on $E$ and $I$ is $I$ will be replaced by its upper half and $E$ stays unchanged. A no question replaces $I$ with its lower half and, because the up to now inactive player becomes the new active player the upper half of the former $I$ becomes the new $E$.

Heuristics:

No questions are useful because they keep $E$ under control for free. Indeed, upon a no question $E$ is reduced to approximately the same size as $I$. The worst case is, then, a string of yes questions.

The trick:

We can hedge against strings of yes questions using the following arrangement that can be described in two equivalent ways. We start with the less convenient but more intuitive of the two:

We group questions into lots of $n$ where $n$ will be a good chunk of the slack we have; e.g. $10$ should work; the bisection will ultimately select one of $2^n$ equal size subdivisions of $I$. Now we take these bins and scale them by a factor of $f:=\frac {2^n} {2^n-1}$ such that the last bin is shifted just out of $I$ (on the right).

If there is a no question we reset and start over. The effect in what used to be the worst case is that $I$ is prematurely extinguished and we can use all the leftover questions in "single user mode" on $E$. As the last reset $|I|=|E|$ happened precisely $10$ questions ago, the overall schedule will be a complete bisection with a 10 cycle hiatus. During the hiatus we switch from $I$ to $E$ which will be the same size we left $I$ at. The overall cost is therefore 997 + 10 + premium for modified bisection. The last term is very small as we'll establish in the next section.

This scheme very modestly slows down our bisection because our target interval shrinks a teeny bit slower. This happens after each no question; the total cost is therefore bounded by a factor of about $f^{1000}$ (in the new worst case of continual resets by no questions) which translates to a grand total of a question or two.

Alternatively, the same scheme can be implemented with minimal administrative overhead by adding to the midpoint $M$ of $I$ the offset $\frac{|E|}{2^n-2}$. Note that we needn't separately keep a record of when the last reset was because that information is encoded in the ratio $|E|/|I|$

Obviously, this write up glosses over many details like finite size losses; but I hope to have convinced you of the principle.

Python implementation

Note: This employs an "endgame database" to smooth over finite size issues. Computing the database takes a few minutes (only first run).

Sample output:

Normal operation

Counter({1007: 607, 1006: 360, 1005: 30, 1000: 1, 998: 1, 997: 1})

Edge/diagnostic cases

without endgame database:
secret=(0, 1),cnt=1000
secret=(1, 2),cnt=1000
secret=(999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999, 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998),cnt=997
N=1024 Counter({19: 257, 18: 125, 17: 124, 11: 121, 16: 102, 14: 77, 15: 73, 13: 69, 12: 50, 10: 2})
with endgame database:
secret=(0, 1),cnt=998
secret=(1, 2),cnt=999
secret=(999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999, 999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998),cnt=999
N=1024 Counter({13: 962, 12: 27, 11: 11})

Code:

import numpy as np
import random

N = 10**300
SC = 10
NQ = 1012
nt = 12
NT = 1 << nt

class oracle:
    def __init__(self,secret=None):
        self.secret = secret or (*(random.randrange(0,N) for _ in "xx"),)
        self.cnt = 0
    def __call__(self,who,bnd):
        self.cnt += 1
        return self.secret[who] < bnd
    def check(self,guess):
        return guess == max(self.secret)
    
def mk_tbl():
    nrsk = np.zeros((NT,NT+1),np.int32)
    bmsk = np.zeros((NT,NT+1),np.int32)
    nr = nrsk.reshape((NT+1,NT))[:-1]
    bm = bmsk.reshape((NT+1,NT))[:-1]
    r = np.arange(nt)
    R = np.arange(NT)
    nr[2:,0] = nr[0,2:] = ((1+r).repeat(2**r))[:-1]
    bm[:,0] = bm[0] = R >> 1
    nr[2:,1] = nr[1,2:] = ((1+r).repeat(2**r))[:-1]
    bm[1:,1] = bm[1,1:] = R[1:] >> 1
    for j in range(2,NT):
        nr[j,j:] = 1 + np.min(np.maximum(nr[1:j,j,None],nrsk[j-1:0:-1,:~j]),axis=0)
        bm[j,j:] = 1 + np.argmin(np.maximum(nr[1:j,j,None],nrsk[j-1:0:-1,:~j]),axis=0)
        J = j
        l = nr[j,j]
        while J < NT:
            K = J
            J += nr[j,J:].searchsorted(l+1)
            m = (nr[j,J:J+2**l] > l+1).nonzero()[0]
            bm[j,J+m] = np.maximum(K,J-2**l+m)
#            bm[j,J:J+2**l] = np.maximum(K,np.arange(J-2**l,min(J,NT-2**l)))
            nr[j,J:J+2**l] = l+1
            l += 1
        nr[j:,j] = nr[j,j:]
        bm[j:,j] = bm[j,j:]
    return nr,bm

import pickle
try:
    nr,bm = pickle.load(open("tbl%d.dmp"%nt,"rb"))
except:
    nr,bm = mk_tbl()
    pickle.dump((nr,bm),open("tbl%d.dmp"%nt,"wb"),pickle.HIGHEST_PROTOCOL)
    
class strategy:
    def __init__(self,secret=None):
        self.swapped = 0
        self.state = N,N,0
        self.oracle = secret or oracle()
    def generate_move(self):
        A,O,S = self.state
        if A<NT:
            return bm[O,A]
        elif O < 2:
            return A // 2
        else:
            return O // 2 + (A-O) // (2**SC - 2)
    def make_move(self,mv):
        A,O,S = self.state
        if self.oracle(self.swapped,mv+S):
            A = mv
            if A < O:
                A,O = O,A
                self.swapped ^= 1
        else:
            A -= mv
            O = max(0,O-mv)
            S += mv
        self.state = A,O,S
    def run(self):
        while self.oracle.cnt <= NQ:
            A,O,S = self.state
            if A == 1:
                assert self.oracle.check(S)
                return self.oracle.cnt
            self.make_move(self.generate_move())


from collections import Counter

print("Normal operation\n")
sample = Counter(strategy().run() for i in range(1000))
print(sample)

print("\nEdge/diagnostic cases\n")
for NT in 0,1<<nt:
    print("without"[:3-4//~NT],"endgame database:")
    for secret in [(0,1),(1,2),(N-1,N-2)]:
        cnt = strategy(oracle(secret)).run()
        print(f"{secret=},{cnt=}")
    N=1024
    small = Counter(strategy().run()for i in range(1000))
    print(f"{N=}",small)
    N=10**300
 

Answer 3

Partial answer

The best I can manage is

1704 questions

This is better than we'd be able to get by binary searching for each person's number individually, but still well short of the 1012 the problem asks for.

As a lower bound, I don't believe we can do any better than:

1257 questions.

Consider the following notation restating the problem.

Let's define the answer as $aB$ if $a$ is the final answer and it was Bob's number, and $aC$ if $a$ is the final answer if $a$ is the final answer and it was Charlie's number. There are a total of $10^{300}$ $B$ cases and $10^{300}$ $C$ cases, for a total of $10^{300} * 2$ cases.

When we ask a question of Bob about the number $x$:

If he says no (his number is lower), we can eliminate either all $xB$ cases at or above $x$.
If he says yes (his number is higher), we can eliminate all $xB$ cases below $x$ because they'd contradict his answer, and also all $xC$ answers below $x$ because they must be lower than Bob's number.

This means

If we consider $L$ and $U$ to be our current upper and lower bounds, then if we ask Bob about $x$
On a Yes, we can update $L$ and eliminate $2 * (x - L)$ cases, for the cost of 1 question.
On a No, we cannot update $U$ until we also ask Charlie the same question, eliminating $2 * (U - x)$ cases for the cost o 2 questions.
If we get a No from Bob and a Yes from Charlie, we know that Charlie's number is higher and can ignore Bob from that point onward.
Since hearing "No" costs us twice as much as hearing "Yes," we should choose our pivots so that hearing "Yes" allows us to eliminate twice as many cases as "No."
Therefore we can choose $x = L + \frac{U - L}{3}$
If we do this, we guarantee that we will either remove 1/3 of the remaining cases for one question, or 2/3 of the remaining cases for 2 questions.

This takes $\log_{3/2}(10^{300})$ questions, or 1704 questions in the worst case (where we get only yes answers) and $\log_{3}(10^{300}) * 2 = 1258$ questions in the best case (where we get only no answers). The difference between the two happens because if we get a yes, the answer to the second question is eliminating 1/3 of the number cases before the previous question, instead of before itself.

It may be possible to choose a better value for the pivot which will get more consistent results, but I don't believe it's possible for any strategy to be guarantee better results than eliminating 2/3 of possibilities for every 2 questions.

It is certainly possible to do better on average, assuming that Bob's and Charlie's numbers are randomly generated, but not if we assume that Bob and Charlie are secretly cooperating to choose numbers that frustrate our strategy (which in this case means choosing numbers that are close together so that they're not split across our pivots).

A worked example

$10^{300}$ is a big number, so I'll work an example of this method assuming that Bob and Charlie are limited to numbers in $\{1,2,\dots,90\}$.

For our first question, we ask Bob about $\frac{90 - 1 + 1}{3} + 1 = 31$.
If he tells us his number is not lower, we know that the true final answer is one of the 60 numbers not lower than 31. (1 questions asked, search space reduced by 1/3). We next ask about $\frac{90 - 31 + 1}{3} + 1 = 51$ and repeat the process.
If he tells us his number is lower, we ask Charlie.
If Charlie's number is not lower, we binary search the remaining 6 numbers.
If Charlie's number is lower, we know that the true final answer is one of the 30 numbers below 31. (2 questions asked, search space reduced by 2/3). We next ask about $\frac{30 - 1 + 1}{3} + 1 = 11$ and repeat the process.

Answer 4

Here's a dynamic programming approach. Let value function $V(\ell_b,u_b,\ell_c,u_c)$ denote the minimum worst-case number of questions needed to determine the larger of Bob's and Charlie's numbers, given current bounds $[\ell_b,u_b]$ and $[\ell_c,u_c]$. The boundary condition is $$V(\ell_b,u_b,\ell_c,u_c)=0 \quad \text{if $\max(\ell_b, \ell_c) \ge \max(u_b, u_c)$}.$$ Otherwise, $$V(\ell_b,u_b,\ell_c,u_c) = 1 + \min\left( \min_{x=\ell_b+1}^{u_b} \max(V(x,u_b,\ell_c,u_c), V(\ell_b,x-1,\ell_c,u_c)), \min_{x=\ell_c+1}^{u_c} \max(V(\ell_b,u_b,x,u_c), V(\ell_b,u_b,\ell_c,x-1)) \right). $$

We want to compute $V(1,10^{300}-1,1,10^{300}-1)$. The values of $V(1,n,1,n)$ for $n \in \{1,\dots,90\}$ are as follows:

0 2 3 4 4 4 5 5 5 5 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9

As in usual binary search, these appear to grow logarithmically, approximately $1.8315 \ln n + 0.9922$, which for $n=10^{300}-1$ would yield

$1266$.

Answer 5

Determining the value of a single 300 digit decimal number takes 997 questions via a binary search. With this additional requirement, I don't believe it can be reliably done. But...

If we stipulate that Bob and Charlie must choose 300 digit binary numbers, then it will take 300 questions to each to determine his number, for a total of 600 questions.

Answer 6

Do a binary search for the 300 digit number. The 300 digit number is between 1X10^300 and 1X10^301. Pick a value in the middle and ask Both Bob and Charlie if their number is higher or lower. If both say higher, pick the middle value in the top half and repeat. If both say lower, pick a number in the bottom half and repeat. Keep going until one says higher and one says lower. There you will know who picked the higher number.

Answer 7

If the plural "we" includes Bob and Charlie themselves, then Bob can ask Charlie whether Charlie's number is ≥ his own. If not, Bob will know the value of the larger number. Then Charlie can ask Bob whether Bob's number is ≥ his own. If not, Charlie will know the value of the larger number. Thus, after at most two questions, "we" (our collective knowledge) will know the value of the larger number, as required.