Let $x_1<x_2<\cdots<x_n$ be $n$ real numbers such that $\sum\limits_{j=1}^n x_j\ne0$. Do there always exist $n$ integers $a_1,a_2,\ldots,a_n$ such that $$ \sum_{j=1}^n a_j\cdot x_j <0 \quad\text{and such that}\quad \sum_{j=1}^n a_j\cdot x_{\pi(j)} >0 $$ for any permutation $\pi$ of $\{1,2,\ldots,n\}$ different from identity?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ The condition that $a_j$ must be an integer is unncessary because the collection $\{[a_1,\dots,a_n]:a_j\in\mathbb{Z}\,\text{ for all }\,j\}$ is dense in the real projective plane. Just first find a real solution and the approximate that real solution with rational numbers, and then multiply by a common denominator so we get integers. $\endgroup$– Joseph Van NameCommented Aug 24 at 15:05
-
3$\begingroup$ I have a solution, but this honestly feels like a convex geometry homework problem... Can you please tell us where did this problem come from? $\endgroup$– Aleksei KulikovCommented Aug 24 at 15:20
-
2$\begingroup$ @AlekseiKulikov It was posted on Aops (artofproblemsolving.com/community/q1h3248642p29807534) in the beginning of the year, but didn't receive any answer. Could you please share your solution? $\endgroup$– jackCommented Aug 24 at 15:44
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Sure, this is true. By the comment of Joseph Van Name we basically want a hyperplane passing through $0$ separating all the permutations of our numbers viewed as vectors in $\mathbb{R}^n$ from $(x_1, \ldots, x_n)$. By the classical duality this is the same as that $(x_1, \ldots , x_n)$ is not in the convex cone spanned by its permutations viewed from zero.
Assume that $x_k = \sum_{\pi \neq Id} \alpha_\pi x_{\pi(k)}$, where $\alpha_\pi \ge 0$. First of all by looking at the sum of $x_k$'s (and using the assumption that it is not zero) we get that $\sum \alpha_\pi = 1$. Let us look at $k = 1$. Since $x_1 = \sum_{\pi \neq Id} \alpha_\pi x_{\pi(1)}$, all other $x_k$ are bigger than $x_1$, $\alpha_\pi \ge 0$ and $\sum \alpha_\pi = 1$, this can only happen if $\alpha_\pi$ is not zero only for the permutations for which $x_{\pi(1)} = x_1$, that is (since $x_k$ are strictly increasing) $\pi(1) = 1$.
Repeating the same for $k = 2$, we can show that this can only happen if $\alpha_\pi$ is not zero only for permutations for which $\pi(1) = 1, \pi(2) = 2$ and so on. At the end $\alpha_\pi$ must be non-zero only for an identity permutation, but we banned this exact permutation from the very beginning!
answered Aug 24 at 16:13
$\begingroup$
$\endgroup$
0
Alternatively, you may start with $a_i=-i+t$ where $t$ is chosen so that $\sum a_ix_i=0$. By rearrangement inequality, we have $\sum a_i x_{\pi_i}>0$ for every not-identity permutation $\pi$. Then you may slightly change $a_i$'s so that $\sum a_ix_i<0$ but still other sums remain positive. It remains to apply Joseph Van Name's observation that you may approximate $a_i$'s by rationals and multiply by their common denominator so that they become integers.
answered Aug 25 at 13:22
$\begingroup$
$\endgroup$
Geometrically: All permutations of x have the same dot product with (1, 1, 1, 1...) and we have assumed that this dot product is not zero. Thus, all the permutations lie on a cone with axis (1, 1, 1, ...). Since the values are distinct, the permutations are distinct. A plane tangent to the cone and containing the tip and a given vector can be perturbed slightly to seperate that vector from the rest
The shape formed is a Permutohedron
