Partition of numbers into two subsets with some properties

75 Views Asked by At

I am trying to prove the following. Fix $n\geq2$ weakly positive numbers $x_{1},\ldots,x_{n}$ that sum to some constant $c>0$ and integer $r\in\{1,\ldots,n-1\}$. Suppose the numbers are weakly increasing (i.e., $x_{i}\leq x_{i+1}$ $\forall i\in\{1,\ldots,n-1\}$). Then, I am trying to prove, one can partition $\{1,\ldots,n-1\}$ into two subsets $A$ and $B$ such that $\sum_{i\in A}x_{i}\leq\frac{1}{n-r+1}c$ and $\sum_{i\in B}x_{i}\leq\frac{n-r}{n-r+1}c$.

Context: I am trying to prove this property as part of a research project I am working on. The nature of the project will not be informative for thinking about what I am trying to prove. However, the partition problem (with weakly positive numbers that are not integers), keeps appearing in what I am trying to do.

So far: A possible first step seems to be the following observation. Suppose that the largest of the original $n$ numbers, $x_{n}$, satisfies $x_{n}\geq\frac{1}{n-r+1}c$. Then the sum of the $n-1$ remaining numbers is weakly less than $c-\frac{1}{n-r+1}c=\frac{n-r}{n-r+1}c$, and hence the postulated partition is $A=\emptyset$ and $B=\{1,\ldots,n-1\}$. The problem is I am not sure how to proceed for the $x_{n}<\frac{1}{n-r+1}c$ case.

Any ideas, pointers to related problems, papers, etc. will be greatly appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

Let $s$ be the largest positive integer less than $n$ such that $$\sum_{i=1}^sx_i\leq {c\over n-r+1}.$$ (Clearly $1$ is such an integer.) If $s=n-1$ we are done for we can take $B=\emptyset.$ I claim $A =\{1,2,\dots,s\}, B=\{s+1,s+2,\dots,n-1\}$ is an acceptable partition. Suppose not, that is, suppose $$\sum_{i=s+1}^{n-1}x_i>{n-r\over n-r+1}c\tag{1}$$ By definition of $s$ $$\sum_{i=1}^{s+1}x_i>{c\over n-r+1}\tag{2}$$ Adding $(1)$ and $(2)$ gives $$ x_{s+1}+\sum_{i=1}^{n-1}x_i>c=x_n+\sum_{i=1}^{n-1}x_i\implies x_{s+1}>x_n$$ which is a contradiction.