# Creating many big sets of small numbers

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.

• @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. – Erel Segal-Halevi Jun 24 at 19:51

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.

• 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 – Erel Segal-Halevi Jun 27 at 18:10
• 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$. – Erel Segal-Halevi Jun 30 at 10:09
• $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. – Erel Segal-Halevi Jun 30 at 13:50
• 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$. – Erel Segal-Halevi Jul 3 at 15:57
• 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$. – bof Jul 3 at 18:19