3
$\begingroup$

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

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

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

  3. 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?

$\endgroup$
6
  • $\begingroup$ I am having a really hard time parsing this formulation of the problem for some reason. What was your motivation again? $\endgroup$ Jan 7, 2010 at 3:05
  • $\begingroup$ Qiaochu, sorry about that. In a moment I'll add such a motivation section to the question statement. $\endgroup$
    – Richard
    Jan 7, 2010 at 5:12
  • $\begingroup$ I don't know what it is about this problem, but I cannot understand what you are asking for! What's the relationship between T and the x_i? $\endgroup$ Jan 9, 2010 at 8:33
  • $\begingroup$ Qiaochu, again, I apologize for not being clear enough. 'T' is supposed to be some maximum number of a certain type of ball you're allowed to add to the box. The actual copy number you add is the $x_i$ for ball type 'i'. I can allow a different threshold for each type of ball, though I restricted it to a universal threshold for all ball types to hopefully make the problem easier (I no longer believe that helps). $\endgroup$
    – Richard
    Jan 9, 2010 at 10:18
  • $\begingroup$ Basically, I want linear expressions of the form $a_1$*$x_1$ + ... + $a_1$*$x_1$ = 'S' where 'S' is going to let you uniquely determine the copy numbers (i.e. $x_1$) the largest number of times for a given set of masses (i.e. $a_i$). By 'largest number of times' I'm talking about the total number of integer sums, not just over the largest range of the possible sums. Does that make any sense to you? $\endgroup$
    – Richard
    Jan 9, 2010 at 10:23

1 Answer 1

2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Boris, a sincere thank you! However, I should have specified that I was looking for a solution where one suffers a penalty for spreading out the values of the masses, i.e. values of [$a_1$, ..., $a_n$] in this manner... $\endgroup$
    – Richard
    Jan 7, 2010 at 15:41
  • $\begingroup$ The integers have to be large, since if you want to allow $T$ copies, you want all $T^n$ sums be distinct. Each of these sums is at most $Tn$ times the largest mass. Thus, the largest mass needs to be at least $T^{n-1}/n$. $\endgroup$
    – Boris Bukh
    Jan 7, 2010 at 15:43
  • $\begingroup$ My previous comments were not as clear as I would have liked. Boris Bukh added his edit after I responded: "I updated the question to put an upper bound on [a_1, ..., a_n]..." However, my point was not that I'm interested in small masses, but that I'm interested in how well one can do when their range is restricted. $\endgroup$
    – Richard
    Jan 7, 2010 at 16:17
  • $\begingroup$ Apologies for the bad question formulation, and thanks for your time. $\endgroup$
    – Richard
    Jan 7, 2010 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.