Creating many big sets of small numbers

Question

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.

Answer 1

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.