Given $0< n \in \mathbb{N}$ and $x_1,\cdots ,x_n \in \mathbb{Z}$ such that $x_i <x_j $ for all $i<j$.
Let $y_i \in \{x_1,\cdots,x_n\}$ for all $1\leq i\leq n$ such that $y_i \leq y_j$ for all $i<j$.
So the meaning is $y_i$ (are not necessarily different) for examples : $y_1=y_2 =x_1$.
Find $x_1,\cdots,x_n$ such that :
-
$\sum \limits_{i=1}^{n} y_i = k \sum \limits_{i=1}^{n} x_i$ for $k\in \mathbb{Z}$ iff $k=1$ and $y_i=x_i$
-
$|x_i| \leq poly(n) $ or $ |x_i| \leq quasi-poly(n)$ or even $|x_i| \leq sub-exp(n)$ but not $ |x_i| \leq exp(n)$
the first condition is the main idea i am looking for, the second condition is to omit "simple" exponential solution for instance $x_i = n^{i}+ n^{n+1}$
Is there such $x_1,…,x_n$ that satisfies these $2$ conditions ?
Examples :
-
$x_1=1,x_2=2,x_3=3,x_4=4$ is not valid solution for $n=4$ because $ y_1=y_2 = 1 $ and $y_3=y_4=4$ and so $y_1+y_2+y_3+y_4 = x_1+x_2+x_3+x_4$ but for instance $y_2\not= x_2$
-
$x_1 = 5,x_2=10,x_3=15,x_4= 90$ and let $y_1=y_2=y_3 =y_4 = 90$ and so $y_1+y_2+y_3+y_4 = 3(x_1+x_2 +x_3+x_4) $ and $ y_1 \not=x_1$ so this is also not valid solution for $n=4$
-
$ x_1 = 1,x_2= 2,x_3 = 4,x_4 =8$ does satisfy the first condition but if the method for finding such numbers $x_1,…, x_n$ is of exponential order then the second condition is violated.
Edit : if we have $x_1,…,x_n \in \mathbb{N_{>0}}$ then we can make a new set of numbers $X_1,…,X_n$ such that $X_i = x_i+ x_n$ and so $n X_n > X_1+…+X_n> n X_1>0$ and that $\frac{n X_n}{n X_1} = \frac{X_n}{X_1} = \frac{2x_n}{x_n+x_1} < \frac{2x_n}{x_n+1} < \frac{2x_n}{x_n} =2$ thus the ratio between the biggest of the summation and the smallest of the summation is $>0$ and $<2$ so in this case $k$ can only be $1$.
thus the question is reduced to find $X_1,…,X_n$ such that $ Y_i \in \{X_1,…,X_N\}$ such that $X_i < X_j$ and $Y_i\leq Y_j$ for every $i<j$ and $a_i \in \{0,1,…,n\}$ and if $\sum \limits_{i} a_i Y_i = \sum \limits_{i} X_i$ and $\sum \limits_{i} a_i=n$ then $ a_i = 1$ for all $i$ and $Y_i =X_i$ ?
Best Answer
No.
The first condition can’t be satisfied by any $x_1, \dotsc, x_n$ that has two size-$\lfloor n/2\rfloor$ subsets $A, B$ with the same sum, because one can take $x_1, \dotsc, x_n$, remove the elements of $A$, insert the elements of $B$ (in sorted order), and get $y_1, \dotsc, y_n$ such that $\sum x_i = \sum y_i$. (For example, $x_1, …, x_7 = 1, 2, 3, 10, 16, 19, 22$ doesn’t work because $1 + 10 + 16 = 2 + 3 + 22$ and we can take $y_1, …, y_7 = 2, 2, 3, 3, 19, 22, 22$.)
Therefore, the $\binom{n}{\lfloor n/2\rfloor}$ sums of the size-$\lfloor n/2\rfloor$ subsets of $\{x_1, \dotsc, x_n\}$ must all be distinct integers. So at least one of these sums must have absolute value at least $\frac12\left(\binom{n}{\lfloor n/2\rfloor} - 1\right)$, which means one of the $|x_i|$ must be at least $\frac{1}{2\lfloor n/2\rfloor}\left(\binom{n}{\lfloor n/2\rfloor} - 1\right) = Θ(2^n n^{-3/2})$, which is exponential in $n$.