# Finding the larger number with a minimal number of questions

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?

• is this 1012 on average or in worst case? Jul 18 at 23:58
• could your possible 300 digit numbers include leading zeros or not? Is the assumption that the numbers are different or could they also be equal? Jul 19 at 6:45
• So is this even possible? Finding just a single number takes 999 guesses in the worst case. So now we have just 13 guesses left to find the second number. The second number can one away or far away. I feel that we need to ask questions comparing the two numbers. Jul 21 at 4:18
• Yet another clarifying question. Is it true that literally the only two questions we can ask are: 1) Bob - is your number greater or equal to <some numerical value>? 2) Charlie - is your number greater or equal to <some numerical value>? Based on all the other questions and the question text itself, it seems like the answer has to be yes, but ..... Jul 21 at 15:45
• Optimal strategy should be to turn to other person each time when the answer is "no". And the number asked for other person should be calculated in some clever way e.g. to equaly split the last binary search interval.
– z100
Jul 21 at 22:04

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.

• Is the worst case for both selected 1?
– z100
Jul 23 at 12:03
• @z100 The numbers that I'm writing are the internal widths, not the intervals themselves. The worst case scenario is that both secret numbers are just under x/2 relative to the original intervals, leading to the "no, yes, yes, yes, ..." sequence of answers. Jul 23 at 15:38
• Brilliant reduction process to just two ordered numbers of interval length and asking just the larger one. Jul 24 at 5:42
• Very nice attempt. I share your intuition that a more continuous set of protocol rules must exist. But it is tricky, as you already switch between 3 regimes (the ‘protocol’ the ‘something different’ and the ‘regular binary search’) Jul 27 at 22:20
• I think your approach actually works with 1042 moves. Maybe good to emphasize that (and explain why) k goes down by 1 as you repeat the cycle. Jul 28 at 10:31

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 = 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()
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:
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


• @z100 FYI I've posted a simple python implementation. It very consistently (almost suspiciously so) comes out at 1006 or 1007 questions. Jul 28 at 1:31
• Very similar to isaacg idea, but does something specific with the E part instead of just trying to bisect I all the time. Doesn't look suspicious to me. :+1: Jul 28 at 2:35
• @JaapScherphuis I have now, see updated post. Thanks for the suggestion. Jul 28 at 16:03
• Great solution! About finite size issues, here's a way of thinking I've found helpful in problems like this. Imagine a continuous variant of the game, where the players' numbers and your guesses are real numbers in the range. You win if your interval shrinks below length 1. Then, a winning strategy in this game translates to the original game within the same number of guesses -- translate each question to a discrete one, and finish by guessing the unique number in the interval. This may waste a couple questions though since the interval can contain a unique integer but have length above 1.
– xnor
Jul 28 at 22:51
• @xnor That looks like a good way to get some intuition and perhaps estimates. Thanks. Also, you have been outgolfed ;-) I'll post in a minute. (Probably just a comment.) Jul 29 at 19:05

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.

• I think you can improve the fraction of remaining value per question to $1/\phi$ (where $\phi$ is the golden ratio) by setting the cutoff point that fraction away from the upper end of the range. That way either one question shrinks the range to $1/ \phi$ its previous length, or two questions shrink to $1-1/\phi$, which equals $(1/ \phi)^2$ and so is like you shrank by a ratio of $1/ \phi$ twice in succession. This lets you improve to about $\log_ \phi (10^{300}) \approx 1435$ questions.
– xnor
Jul 22 at 7:13
• I think a significant flaw is saying that $10^{300}$ possibilities for Bob and $10^{300}$ for Charlie make $2*10^{300}$ total possibilities. I believe it makes $10^{600}$, and that this changes all your math. Jul 22 at 14:56
• @xnor : the same conclusion (1436 rounded up) if using graphic representation using square of $10^{300} * 10^{300}$ possibilities when pivot point is chosen so that "no" and "yes" reduces the solution equally. Of course this is equivalent to your and Tim C's explanation.
– z100
Jul 22 at 19:10
• @DavidG., the possibilities mentioned in the answer is not about what both numbers are, but about the final answer: what the maximum number is (100^300 possibilities), and from whom (2 possibilities: aB and aC). So if the number range is 1-4, the possibilities are 1B, 2B, 3B, 4B, 1C, 2C, 3C, 4C, 4x2=8 possibilities, and not referring to the possibilities of their number combinations (1-1, 1-2, 1-3, 1-4, 2-1, 2-2, 2-3, 2-4, 3-1, 3-2, 3-3, 3-4, 4-1, 4-2, 4-3, 4-4, a total of 4x4 combinations) Jul 23 at 0:12
• This is the same idea I came up with. But still don't see how it can be extended to solve the puzzle. Certainly a nice improvement. Thanks for the write up. Jul 23 at 0:13

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$$.

• Doesn't $\ell_b$ always equals $\ell_c$? I think you can also just work with $u_b - \ell_b$ and $u_c - \ell_c$ to narrow down to two variables. And, moreover it's always better to ask the question of the person whose have the largest upper bound.
– xnor
Jul 23 at 6:39
• No, $\ell_b$ and $\ell_c$ are generally different. For example, if the first question is to Bob and the reply is yes, then $\ell_b=x$ and $\ell_c=1$. The new answer from @isaacg uses the other ideas you mentioned. Jul 23 at 13:22
• I should have said that we can treat the two lower bounds as equal since any values one player has that are below the other player's lower bound are irrelevant, but it looks like @isaacg is already doing that too.
– xnor
Jul 23 at 21:37

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.

• The numbers are 300 digit decimals. It can be done :)
– jowd
Jul 21 at 12:55

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.

• Cool! But "We want to find the value of the larger number" (a quotation from the question) — not merely who picked it. Can you edit to explain how we know that'll be done within the requisite number of turns? Jul 18 at 4:40
• A binary search will take up to 999 questions for one person, but you could need twice that if Bob and Charlie's numbers are close together.
– fljx
Jul 18 at 7:40
• To put the other comments in plain English: there are (several) cases where this approach hits the question limit without finding the larger number, and thus fails the given task. Also, it will often hit the question limit without finding even the person with the larger number. To condense even further: "This doesn't work. At all."
– Bass
Jul 19 at 16:07
• Not to mention a 300-digit number can only range from $10^{299}$ to $10^{300}-1$, not $10^{300}$ to $10^{301}-1$. Jul 20 at 13:47
• @Nautilus according to OP's comment on my comment, leading zeros are allowed. So, the range is from $0$ to $10^{300}-1$. Jul 21 at 13:57

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.

• We is not Bob or Charlie. We is the third person, asking them questions.
– jowd
Jul 21 at 14:10