# Subsets of equal size and equal sum

Given a set of $$n$$ distinct (real) numbers and an integer $$k$$, what is the maximum number of subsets of size $$k$$ such that they all have the same sum?

Note that we are not specifying the sum.

For example, if we have $$\{1,2,...,2n+1\}$$, and $$k=2$$, we can do $$1+(2n+1)=2+2n=...$$. And the maximum is $$n$$ since we can pair up those who sum to a specific number and get at most $$(2n+1-1)/2$$ pairs.

What happens when $$k>2$$? Can we get a bound? I saw similar questions asked but they are about getting an algorithm to find such subsets, and not the maximum.

• disjoint subsets ? The answer will depend on this. – Roddy MacPhee Apr 10 '19 at 19:52
• Not necessarily. If they are required to be disjoint wouldn't the bound just be $\lceil{n/k}\rceil$? – Clostridium Tetani Apr 10 '19 at 19:56
• That's a hard upper bound if not disjoint. Possibly even a least upper bound. It would be floor of the fraction not ceil though. – Roddy MacPhee Apr 10 '19 at 19:58
• Yes it should be floor. In the case that the subsets are disjoint, since the set of number is arbitrary I think we could just choose them so that each k-tuple sum to the same. For example, $n=6,k=3$ we can have $1+2+3=0+7+(-1)$. – Clostridium Tetani Apr 10 '19 at 20:02
• Just to be clear: you're asking for an upperbound, in the case subsets need not be disjoint? – antkam Apr 11 '19 at 4:32

I interpret the question to mean: allowing overlapping subsets, and given free choice of the $$n$$ distinct numbers, what is the maximum number of $$k$$-subsets that have the same sum?

The following construction achieves asymptotically $${n/2 \choose k/2}$$ such subsets. It is probably not the maximum, and is still quite far from $${n \choose k}$$, but it is a lot of subsets for large $$n,k$$.

Construction: Use $$\{1, 2, ..., n\}$$ and pair up the numbers so each pair sums to the same value $$1+n$$. There are $$m = \lfloor n/2 \rfloor$$ such pairs, plus an extra number (the middle one) if $$n$$ is odd. A $$k$$-subset will be made of $$p=\lfloor k/2 \rfloor$$ such pairs, plus an extra (fixed) number if $$k$$ is odd. All such subsets obviously have the same sum. The number of such $$k$$-subsets is:

• $${m-1 \choose p}$$ if $$n$$ is even and $$k$$ is odd (because in this case we need to "break" one of the $$m$$ pairs to provide the extra number for $$k$$)

• $${m \choose p}$$ otherwise

BTW, for small numbers we can do better. E.g. for $$n=9, k=3$$, the above construction would give $${4 \choose 1} = 4$$ subsets, but a magic square can give $$8$$ subsets, since every row sum $$=$$ every column sum $$=$$ each of the two diagonal sums $$=15$$.

\begin{align} 8 && 1 && 6\\ 3 && 5 && 7\\ 4 && 9 && 2 \end{align}