(This posting became very long, so I should note that there are two alternative but nearly equivalent formulations of the same question being given. The first one asks for the optimal strategy for playing a game, the second is a more formally stated optimization problem. There is also a proposed solution for the n = 2 case, and an answer by Boris Bukh (below) for the unbounded case of [$a_1$, …, $a_n$].)
You and I play a game:
I hand you an empty box and 'n' > 1 canisters of balls, where 'n' is agreed upon beforehand. The balls in each canister have a unique integer mass to my specification, 'L' < [$a_1$, …, $a_n$] < 'M' (where 'L' and 'M' are some fixed, lowest and largest possible integer masses, respectively), and no two canisters will have balls with the same mass.
Now, after blindfolding myself, I ask you to fill the empty box with somewhere between zero or a finite integer number of copies, 'T', of each type of ball: [$x_1$, …, $x_n$]. Here, 'T' is the same for all ball types.
When finished, you fully seal the box, hand it back to me, and ask for the copy numbers of each ball type. To accomplish this, all I am allowed to do is place the box on a scale to 'weigh' its total mass.
The reward system works as follows – the higher I can set the copy number threshold, 'T', the more money I win. However, if I set 'T' too high to properly guess the exact copy numbers, I lose an infinite amount of money and the game is over. Assuming I love money and hate risk, how do I choose the masses of the balls, [$a_1$, …, $a_n$], such that I make the most money at no risk of financial ruin?
Interestingly, for the n = 2 case (though not for n > 2), the answer seems to be: Pick 'L' < [$a_1$, $a_2$] < 'M' such that the Lowest Common Multiple, LCM[$a_1$, $a_2$], is maximized over the allowed interval. Depending on 'L' and 'M', [$a_1$, $a_2$] are not necessarily prime.
LCM[$a_1$, $a_2$] also seems to always equal the maximum measured mass of the box for which unique copy numbers can be determined ($S_{max}$ from the below optimization formulation where 'T' can be different for the different masses/balls).
Intuitively this seems right, but is it true for all values of 'L' and 'M'?
(For finding 'T' in polynomial-time given masses [$a_1$, …, $a_n$], please see note at bottom of page. Is there a better solution?)
We can also state this question as the following optimization problem –
I provide you with the number of terms, 'n', for a monomial sum (or linear Diophantine equation) of the form: $a_1$$x_1$ + … + $a_n$$x_n$ = S, where 'L' < [$a_1$, …, $a_n$] < 'M', and 'S' belong to the set of positive real integers while [$x_1$, …, $x_n$] belongs to the set of integers $\ge$ 0.
We now define a function #NonDegenerate([$a_1$, …, $a_n$]) that outputs [k, $S_{max}$] where 'k' is the cardinality (i.e. number of elements) in the set [$S_1$, …, $S_{max}$] which:
-
For the provided set [$a_1$, …, $a_n$], must contain all possible sums, $a_1$$x_1$ + … + $a_n$$x_n$ = $S_k$, for all sets of integers [$x_1$, …, $x_n$] s.t. 0 < $S_k$ $\le$ $S_{max}$.
-
Where all elements of the set [$S_1$, …, $S_{max}$], i.e. all $S_k$, must have a single or unique solution [$x_1$, …, $x_n$] for the given set of [$a_1$, …, $a_n$].
-
Where $S_{max}$ is the largest possible sum satisfying conditions (1) & (2).
Now, for a given number of monomial terms 'n' (or if you are allowed to select 'n'), what is the most efficient strategy for selecting [$a_1$, …, $a_n$] to maximize the output 'k' of the '#NonDegenerate' function?
Note on relationship to game that was described earlier – Here we're talking about maximizing the number of sums, $S_k$ < $S_{max}$, that have unique solutions. This should be equivalent to maximizing the threshold 'T' for the maximum possible copy numbers of balls in the first formulation of the problem under the condition that you won't allow yourself to lose the game.
(For finding $S_{max}$ in polynomial-time given [$a_1$, …, $a_n$], please see note at bottom of page. Is there a better solution?)
Some computational results:
For expression $a_1$$x_1$ + $a_2$$x_2$ = S, over the range $x_1$, $x_2$ = (1, 100) and $a_1$, $a_2$ = (1, 100), max(#NonDegenerate) = 5049 for [$a_1$, $a_2$] = [99, 100] and $S_{max}$ = 9899.
(Mistake before where I used a result that set a minimum copy number min($a_k$) = '1' rather than the correct min($a_k$) = '0')
Note on counting solutions for the expression – $a_1$$x_1$ + … + $a_n$$x_n$ = $S_k$, and a possible polynomial time algorithm to find $S_{max}$ or 'T' given the set [$a_1$, …, $a_n$]:
As fleshed out in a previous post of mine (with help from Sam Nead) – "Counting Lattice Points on an N-simplex" (Counting lattice points on an n-simplex) – the problem of finding solutions to expressions of the form:
$a_1$$x_1$ + … + $a_n$$x_n$ = S
Is equivalent to counting the number of integer lattice-points on (but NOT in the bounded area) the N-simplex being defined (i.e the real-number solution set to the expression). Since polynomial time algorithms exist for exactly enumerating integer points for rational polyhedron of fixed-dimension (due to Barvinok et al), there should also exist a straightforward polynomial-time algorithm for this optimization problem (via testing and incrementing $S_{max}$ or the corresponding value 'T' in the game description). But does a nicer strategy or solution exist?
Best Answer
Choose the masses to be powers of a given integer $M$. Then you can guess correctly as long as the number of copies is at most $M-1$ by writing the total mass in base $M$ and reading off the digits. As $M$ can be chosen arbitrarily large, you can reap arbitrarily large reward.
EDIT 1: The problem was edited after this answer was given. The problem now imposes an upper bound on the masses. However, the masses have to be large, since if one wants to allow $T$ copies, then all $(T+1)^n$ sums be distinct. Thus the largest of them is at least $(T+1)^n/n-1$, and it is at most $Tn$ times the largest mass. Thus, the largest mass needs to be at least $(T+1)^{n-1}/n$.
EDIT 2: The question was edited again, this time requiring a lower bound for the masses as well. For this problem let $X=M^n$ and let $i$'th mass be $M^i+X$ for $i=0,\dots,n-1$. This increases the largest mass by only a factor of $M$.