1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you @saulspatz. This solved my problem. Apologies for getting to this with such a delay. $\endgroup$ – Jan Aug 8 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.