1

Given a set $S$ of size $n$, there is a maximum number of disjoint subsets where the size of each of the subsets is larger than zero and different for each of the subsets. Which is obtained by counting the number of times $(k)$ we must add up the sequence of integers starting at 1, where at each addition we increase the number by which we add with one, until the our sum is larger than $n$, and then taking $k-1$.

For example, if $n = 11$ we find that the maximum number of subsets is obtained by summing 1 + 2 + 3 + 4 + 5 = 15 > 11, e.g. k = 5, and the maximum number of subsets with different sizes for $n = 11$ is 4.

My question is if there exists a simple expression for this number that does not require to iteratively sum until some condition is reached?

A more elegant representation of the problem (thanks ab123) is which expression gives back the the maximum value for $i$ in under the constraint that:

$$ i(i+1) \leq 2n $$

This function should for $n$ is 1:15 return the following answers:

$1,1,2,2,2,3,3,3,3,4,4,4,4,4,5$

Joost
  • 43
  • 1
    you need largest $i$ such that $\dfrac{i(i + 1)}{2} \leq n$? – ab123 Jul 02 '20 at 10:43
  • That is indeed a more elegant representation of the problem! – Joost Jul 02 '20 at 10:45
  • 1
    It seems to me the problem statement is missing a very important detail: The subsets must be disjoint! Otherwise, you can of course have $n$ such subsets, one for each size $1,2,\ldots, n$. – Ingix Jul 02 '20 at 11:55

1 Answers1

1

If you need largest $i$ such that $\dfrac{i(i + 1)}{2} \leq n$, then

$\implies i^2 < 2n$

$i = \lfloor\sqrt{2n}\rfloor - 1$

Edit: I think the other (now deleted) answer posted by Giorgio was correct, the above is an incorrect simplification.

As worked out by Giorgio, solving $k^2 + k - 2n \leq 0$ gives the correct solution $i = \left\lfloor \dfrac{\sqrt{1+ 8n} - 1}{2}\right\rfloor$.

ab123
  • 2,521
  • I was indeed to quick with assuming your answer was correct, as your answer would give the sequence 0 1 1 1 2 2 2 3 3 3 3 3 4 4 4 for $n = 1:15$. – Joost Jul 02 '20 at 11:12
  • @JoostKruis yes, sorry about that. Giorgio deserves the credit for this :) – ab123 Jul 02 '20 at 11:21
  • 1
    Thanks Giorgio! And no problem of course! The solution you posted now is indeed right, I had just found it also with wolfram alpha for the input: "maximise k where k(k+1) <= 2n" – Joost Jul 02 '20 at 11:23