Given positive integer $n$, we are looking for a set
of $n$ positive integers $a\_i$.


The following linear integer program must have only
the trivial integer solution of all ones.


* $0 \le x\_i \le \frac{n}{2}$
* $\sum x\_i = n$
* $\sum a\_i x\_i = \sum a\_i$


One exponential example is to take $a\_i=C^i$.


We experimented with an integer programming solver and
couldn't find small solutions, possibly because of
the law of small numbers.
To our surprise taking $n=30$ and random numbers in the range
$[2^{29},2^{30}]$ gave non-trivial solutions.



> 
> Q1 How small can $\max a\_i$ be in terms of $n$?
> Can we get $\exp(o(n))$?
> 
> 
> 



> 
> Q2 If $\max a\_i$ is polynomial in $n$, what bound
> can we get for the number of solutions of the integer program?
> 
> 
> 



Only trivial solution to a pair of constrained linear diophantine equations
The answer to the first question is negative.


Let $A$ denote the set of weights $\{a\_i\}$. Strengthen the first constraint to $0 \le x\_i \le 2$.


If we have two different subsets $S\_1, S\_2 \subset A$ of the same cardinality, their sums must be different, since otherwise we can assign $$x\_i = \begin{cases} 2 & \textrm{if } a\_i \in S\_1 \setminus S\_2 \\
0 & \textrm{if } a\_i \in S\_2 \setminus S\_1 \\
1 & \textrm{otherwise}\end{cases}$$ to get a second solution to the program.


Therefore the $\binom{n}{\lfloor n/2 \rfloor}$ subsets of half of the weights (rounded down) must all have different (positive integer) sums, so that one of those subsets must have weight at least the number of subsets, and the sum of all of the weights must be at least $\binom{n}{\lfloor n/2 \rfloor} + \binom{\lceil n/2 \rceil + 1}{2} = \Theta(n^{-1/2} 2^n)$.


Thus $\max a\_i \in \Omega(n^{-3/2} 2^n)$.


