Minimum number of guesses on sum and product required to find two numbers.

Question

I have a series of numbers 1 to N. A system randomly picks up two numbers and computes their sum and product. I have to guess the sum and product, The system will tell if the sum and product are larger or smaller. What is the optimal strategy to find the numbers in minimal number of guesses.

Answer 1

I assume that we are looking for a minimax strategy that limits the number of guesses required in the worst case. Otherwise, if we are looking to minimise the expected number of guesses, we will need to adapt the solution so that it can get a higher payoff in the average case, e.g. by choosing more likely combinations.

The product will give you a lot more information than the sum does (in cases where one of the numbers is a prime $\ge \sqrt{N}$ it will immediately tell you both numbers). It will be more efficient if you use the product and sum guesses in a complementary fashion, guessing, say, products on the high side and sums on the low side. So I would suggest a binary search over all possible values of the product, using the sum to exclude other possible combinations. For example:

• for N=4: possible products are $\{2,3,4,6,8,12\}$ so you might start with initial guesses of $p=6, s=5$. If one or both of these is correct, you will know the two numbers straight away; otherwise, a second guess should enable you to determine the numbers.

The diagram below highlights that what we are actually doing is a two-dimensional search. You may want to adopt some heuristic for guessing $p,s$ at each stage: e.g. minimising the maximum number of points over all quadrants (assuming both guesses are wrong). If this is two or three, the next guess will always determine the numbers; if four, the next guess will succeed only if there are two or three (but not four) numbers with the same sum or product.

Answer 2

The following strategy reduces the number of options by a factor of at least three at each stage.
I refer to a possible (sum,product) as a $point$.
Let $P$ be a product where at most 1/3 of the possible points have product greater than $P$ and at most 2/3 of the possible points have product less than $P$.
Of those points with product less than $P$, let $S$ be the median of the sums.
The system will compare the true sum and product to S and P, and will reduce the set of possible points to a set no more than 1/3 what it was.
This method takes at most $\log_3{N\choose2}$ guesses.