2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ disjoint subsets ? The answer will depend on this. $\endgroup$ – Roddy MacPhee Apr 10 '19 at 19:52
  • $\begingroup$ Not necessarily. If they are required to be disjoint wouldn't the bound just be $\lceil{n/k}\rceil$? $\endgroup$ – Clostridium Tetani Apr 10 '19 at 19:56
  • $\begingroup$ 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. $\endgroup$ – Roddy MacPhee Apr 10 '19 at 19:58
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Clostridium Tetani Apr 10 '19 at 20:02
  • 1
    $\begingroup$ Just to be clear: you're asking for an upperbound, in the case subsets need not be disjoint? $\endgroup$ – antkam Apr 11 '19 at 4:32
1
$\begingroup$

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} $$

$\endgroup$

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.