0
$\begingroup$

For example, with k = 2 and n = 4, in [1,4] there are sums 1+2=3, 1+3=4, 1+4=5 (or 2+3=5),2+4=6, and 3+4=7 Thus, the answer is 5.

$\endgroup$
5
  • 1
    $\begingroup$ what have you tried for larger values of k,n? $\endgroup$
    – cineel
    Feb 3, 2022 at 23:03
  • 2
    $\begingroup$ Hint: Figure out the smallest and largest sums, call them $m$ and $M$. By looking at more examples for various small $k$ and $n$, try to find a pattern describing which sums in the range $[m,M]$ are not attainable. Then prove your pattern holds in general, and count the number of numbers fitting that pattern. $\endgroup$ Feb 3, 2022 at 23:17
  • 2
    $\begingroup$ What about $3+4 (=7)$ ? $\endgroup$ Feb 3, 2022 at 23:29
  • $\begingroup$ Thank you, Adam, for spotting that mistake. Edited. $\endgroup$
    – John
    Feb 4, 2022 at 10:58
  • $\begingroup$ The body of the Question should be used to give a complete problem statement. Splitting the problem between title and body makes it hard to follow, so try to make the body text stand on its own. Also merely stating a problem is not enough to ask a suitable Question. You should put the problem in some sort of context: where it comes from, what you tried, or what about it interests you. $\endgroup$
    – hardmath
    Feb 20, 2022 at 0:01

1 Answer 1

2
$\begingroup$

For simplicity, lets consider the range $[1,100]$ and $k=3$. My smalliest number would be $1+2+3 = 6$ and my largest would be $98+99+100 = 297$. Notice that I can create any number between 297 and 6 just my taking my smallest number $1+2+3=6$ and adding an integer to the $3$. So lets say I want to create the number $50$ then, $1+2+(3+44)=50$. Therefore, the total number of valid creations is $297-6+1=294$.

Now let us generalize this:

The easiest way to get the smallest sum is by simply adding the smallest numbers together: $$1+2 +...+k = \sum_{i=1}^ki = \frac{k(k+1)}{2}$$

The easiest way to get the largest sum is pretty much the same, but instead we want to add the largest numbers: $$n+(n-1)+(n-2)+...+(n-k+1) = \sum_{i=0}^{k-1}(n-i)$$ Thus the total amount of possible numbers is: $$\sum_{i=0}^{k-1}n-\sum_{i=0}^{k-1}i -\frac{k(k+1)}{2}+1 =kn-\frac{k(k-1)}{2}-\frac{k(k+1)}{2}+1=k(n-k)+1$$

$\endgroup$
5
  • 1
    $\begingroup$ Hello :) it's only a typo, we have $1+2+3=6\neq 5$. $\endgroup$
    – Jochen
    Feb 4, 2022 at 9:35
  • $\begingroup$ @Jochen Good catch. Will fix. $\endgroup$
    – WaterDrop
    Feb 4, 2022 at 13:35
  • $\begingroup$ @Stan: Assuming the $k$ numbers are elements in $[1,n]$ we also have to consider multiple occurrences of elements to form valid sums. $\endgroup$ Feb 5, 2022 at 18:26
  • $\begingroup$ @epi163sqrt Based on the wording of the question "How many different sums of $k$ elements are in the range", I do not think we need to account for that. The sum of $2+5$ is the same as the sum of $6+1$ and so on. $\endgroup$
    – WaterDrop
    Feb 6, 2022 at 13:25
  • $\begingroup$ @sStand: I think we should also consider in your example $k=3$ sums as $1+1+1=3$ and $100+100+100=300$ since we do not necessarily have to select pairwise different elements from $[1,100]$. $\endgroup$ Feb 6, 2022 at 14:52

Not the answer you're looking for? Browse other questions tagged .