Majorization form for a given set of integers in some interval.

68 Views Asked by At

Given a set of $n$ positive integers $X=\{x_1,x_2,\ldots,x_n\}$ such that $x_i\in[a,b]$ for all $i$ and some positve integers $a$, $b$, $\sum_{i=1}^n x_i =S$ and $x_i\geq x_{i+1}$ for all $1\leq i\leq n-1$. Is there exist a set of integers $X^*=\{x^*_1,\ldots,x^*_n\}$, which can always majorize other set of integers under the same constraint? $X^*$ majorizes $X$ means that $\sum_{i=1}^jx^*_i \geq \sum_{i=1}^jx_i$ for all $1\leq j< n$, and be denoted as $X^*\succ X$. The problem formulation can be given as the following.

Let $${\cal{X}}\triangleq\Bigg\{X=\{x_1,x_2,\ldots,x_n\}\Bigg|x_i\in[a,b], \sum_{i=1}^nx_i=S \mbox{ and } x_i\geq x_{i+1}\Bigg\},$$ where $a,b\in Z_+$. Does it exist an $X^*\in{\cal X}$, such that $X^*\succ X$ for all $X\in{\cal X}$ ?

Remark: This problem is inspired by the Left Concave-Right Convex inequality from LCRCF Theorem in Section 3.3. It can be solved when $x_i\in[a,\infty)$, and the solution is $X^*=\{x^*_1=S-(n-1)a, x^*_2=a, x^*_3=a, \ldots, x^*_n=a\}$. However, when $x_i$ is drawn from $[a,b]$, I have no clue to find $X^*$.

1

There are 1 best solutions below

0
On BEST ANSWER

If $b\geq S-(n-1)a$, you take the $x^*$ you mention in your answer.

If $b<S-(n-1)a$, put $$ x^*=(\overbrace{b,\ldots,b}^{m\ \text{ times}},r,\underbrace{a,\ldots,a}_{k\ \text{ times}}) $$ where $$ m=\left\lfloor\frac{S-na}{b-a}\right\rfloor,\ \ \ k=\left\lfloor\frac{nb-S}{b-a}\right\rfloor,\ \ \ r=S-mb-ka. $$ This will be the maximum, because it maximizes the size of the number to the left, so any $x$ with entries between $a$ and $b$ and sum $S$ will be majorized by $x^*$.