6
$\begingroup$

There are $n$ numbers $a_1,\ldots,a_n\in [0,1]$.

Their sum is $\sum_{i=1}^n a_i = s$, where $s$ is some integer.

We want to group them into sets so that the sum of each set is at least $t$, where $t$ is some integer.

Let $F(n,s,t)$ be the largest number of sets that we can always create (for any $a_i$).

What is $F(n,s,t)$?

Example. $F(n=8,s=7,t=1)=4$:

  • Proof that $F(8,7,1)\geq 4$: We can always create 4 sets by dividing the $8$ numbers arbitrarily into $4$ pairs. The sum of each pair is at most $2$, and the sum of all pairs is $7$, so the sum of each pair is at least $1$.
  • Proof that $F(8,7,1)\leq 4$: We cannot always create 5 sets. Suppose for all $i$, $a_i=7/8$. In any $5$ sets, at least one set is a singleton so its sum is less than $1$.

Similarly, whenever $n$ is even, $F(n,n-1,1)=n/2$.

What else is known on the function $F$?

Currently I am particularly interested in the case $t=2$, but I will be happy for any more general references.

UPPER BOUND: $F(n,s,t)\leq \lfloor {s+1\over t+1}\rfloor$. Proof. Suppose that $s+1$ numbers equal $s/(s+1)$ and the other $n-s-1$ numbers equal $0$. To create a set with sum at least $t$, we need $t+1$ nonzeros. So we can create at most $\lfloor {s+1\over t+1}\rfloor$ such sets.

$\endgroup$
  • $\begingroup$ @bof I added the upper bound that I had in mind. It is similar but not identical to yours. I am not sure about the lower bound. $\endgroup$ – Erel Segal-Halevi Jun 24 at 19:51
5
$\begingroup$

For $n\in\mathbb N$ and $s,t\in\mathbb R$ with $0\lt t\le s\le n$, let $F(n,s,t)$ be the greatest integer $m$ such that any family of $n$ numbers $a_1,\dots,a_n\in[0,1]$ with $a_1+\cdots+a_n=s$ can be partitioned into $m$ subfamilies, each with sum $\ge t$.


Lemma 1. If $k\in\mathbb N$ and $s\le k\le n$, then $F(n,s,t)\le\left\lfloor\frac k{\lceil kt/s\rceil}\right\rfloor$.


Lemma 2. If $n\gt s$ then $F(n,s,t)\le\left\lfloor\frac{\lfloor s+1\rfloor}{\lfloor t+1\rfloor}\right\rfloor$.

Proof. Put $k=\lfloor s+1\rfloor$ in Lemma 1.


Lemma 3. $F(n,s,t)\ge\left\lfloor\frac{s+1}{t+1}\right\rfloor$.

Proof. Let $m=\left\lfloor\frac{s+1}{t+1}\right\rfloor\lt s+1$, so that $t\le\frac{s+1}m-1=\frac sm-\frac{m-1}m$. We may assume that $m\ge2$.

Lat $a_1,\dots,a_n\in[0,1]$ be given, $a_1+\cdots+a_n=s$. For notational convenience we assume that $a_1,\dots,a_p\gt0$ while $a_{p+1}=\cdots=a_n=0$.

Partition the interval $[0,s]$ into $m$ equal subintervals $J_1,\dots,J_m$, indexed from left to right; that is, $J_i=[c_{i-1},c_i]$ where $c_i=\frac{is}m$. Then $|J_i|=\frac sm\gt1-\frac1m$.

Also partition $[0,s]$ into subintervals $A_1,\dots,A_p$ of respective lengths $|A_i|=a_i$. Let $\mathcal A=\{A_1,\dots,A_p\}$.

Each interval $A\in\mathcal A$ will be assigned to at most one of the intervals $J_1,\dots,J_m$, and (some of) the numbers $a_1,\dots,a_p$ will be assigned correspondingly to $m$ groups. Namely, an interval $A\in\mathcal A$ is assigned to the interval $J_i=[c_{i-1},c_i]$ if it satisfies one of the following three conditions: $$A\subseteq J_i;$$ $$i\gt1,\ \ c_{i-1}\in A,\ \ \frac{|A\cap J_i|}{|A|}\gt\frac{i-1}m;$$ $$i\lt m,\ \ c_i\in A,\ \ \frac{|A\cap J_i|}{|A|}\gt\frac{m-i}m.$$ It is important to note that no interval $A\in\mathcal A$ is assigned to more than one $J_i$.

Now the set of intervals assigned to $J_i$ covers $J_i$, except possibly for an interval at the left of length $\le\frac{i-1}m|A|\le\frac{i-1}m$, and an interval at the right of length $\le\frac{m-i}m|A|\le\frac{m-i}m$. Therefore, the sum of the lengths of intervals assigned to $J_i$ is $\ge\frac sm-\frac{i-1}m-\frac{m-i}m=\frac sm-\frac{m-1}m\ge t$.


Theorem. If $t\in\mathbb N$ and $n\gt s$, then $F(n,s,t)=\left\lfloor\frac{s+1}{t+1}\right\rfloor$.

Proof. Lemmas 2 and 3.

$\endgroup$
  • $\begingroup$ Yes, for some applications it may be interesting to evaluate $F(n,s,t)$ for $s,t$ rational numbers. Alternatively we can scale the numbers up to integers. We need to add just one more parameter: each number $a_i$ is in $[0,q]$, for some integer $q\geq 1$. I think that in this case your technique leads to a lower bound of $\lfloor{s+q\over t+q}\rfloor$, but I have to verify $\endgroup$ – Erel Segal-Halevi Jun 27 at 18:10
  • $\begingroup$ Instead of separating lemmas 1 and 2, can you have just one lemma in which the number of nonzero terms is $\lfloor s+1 \rfloor$? It seems to cover both cases: when $s$ is an integer, $\lfloor s+1 \rfloor = \lceil s+1 \rceil = s+1 $, and when $s$ is not an integer, $\lfloor s+1 \rfloor =\lceil s\rceil$. $\endgroup$ – Erel Segal-Halevi Jun 30 at 10:09
  • $\begingroup$ $F \leq \lfloor s+1 \rfloor / \lfloor t+1 \rfloor$. Since you have $\lfloor s+1 \rfloor$ nonzero terms, and each term equals $s / \lfloor s+1 \rfloor < 1$. So in each subfamily with sum $t$, there must be at least $\lfloor t+1 \rfloor$ such elements. $\endgroup$ – Erel Segal-Halevi Jun 30 at 13:50
  • $\begingroup$ Looks good, thanks! Now the only gap that remains is when $t$ is not an integer - the upper bound has $\lfloor t+1\rfloor$ in the denominator and the lower bound has $t+1$. $\endgroup$ – Erel Segal-Halevi Jul 3 at 15:57
  • $\begingroup$ The upper bound in Lemma 2 is the result of setting $k=\lfloor s+1\rfloor$ in Lemma 1, but this is not necessarily the optimal value of $k$. For instance, $F(n,1,0.4)\le2$ by Lemma 2, but (assuming $n\ge3$) by setting $k=3$ in Lemma 1 we get $F(n,1,0.4)\le1$. $\endgroup$ – bof Jul 3 at 18:19

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.