There is this a simple looking and intuitive statement but I am not sure how to start approaching this problem.

Let $S=\{s_1,s_2,\ldots,s_n\}$, where $s_1,s_2,\ldots,s_n>0$ such that $s_1+s_2+\ldots+s_n=k$. We need to show that if $k\leq2n-1$, then for every $i=1,\ldots,k$, $S$ has a subset whose elements sum to $i$.

I found an example where $k>2n-1$ to the statement above:

$1+2+3+4+5=15$, where we have $s_1=1, s_2=2, s_3=3, s_4=4, s_5=5$ and $n=5$

where $2n-1=2(5)-1=9$ and $k=15>2n-1=9$.

How can we show that if $k\leq2n-1$ then we must have example above?

My idea is to model the integers as unit integer 1. Let $s_1=s_2=\ldots=s_n=2$, then $s_1+s_2+\ldots+s_n=2n$. If we take away at least 1, from one of $s_1,s_2,\ldots,s_n$, then we have at least one of $s_1,s_2,\ldots,s_n$ equals to 1. Then we can easily get any $i=1,\ldots,k$ by combination of the sum of $2$'s and $1$'s.

But my working only works if $s_1=s_2=\ldots=s_n=2$. How to show for general $\{s_1,s_2,\ldots,s_n\}$?

Can we use prove by contradiction?

Can somebody please give some light in proving the statement?



Thanks @Doug M for the hint:

Let's try by induction:

BASE CASE: $s_1=s_1$, then $i=k$ and $S$ has a subset whose elements sum to $k$.

INDUCTION HYPOTHESIS: Suppose $s_1+s_2+\ldots+s_N=K$ and if $K\leq2N-1$ then the statement be true.

Now we have $s_1+s_2+\ldots+s_N+s_{N+1}=K+s_{N+1}$ and suppose $K+s_{N+1}\leq2(N+1)-1=2N+1$

By the induction hypothesis, we have $K\leq2N-1$, then it implies $K+s_{N+1}\leq2N-1+s_{N+1}$

But then I am not sure how to show the statement is true for the set $\{s_1,s_2,\ldots,s_N+s_{N+1}\}$?

  • $\begingroup$ I would try a proof by induction. $\endgroup$ – Doug M May 17 '16 at 6:06
  • $\begingroup$ @DougM. Thanks for the hint. I have tried using induction and made some edit, would you help me give some more hints on my work? $\endgroup$ – user71346 May 17 '16 at 7:08

Suppose it holds for $<n$. We need to prove it for $n$. Let's choose an arbitrary example for $n$: $$\sum_{j=1}^n s_j=k\leq 2n-1$$

If the $s$ lot only contains ones, it's obvious. Otherwise we remove any $s_j>1$. The reduced lot of $n-1$ numbers adds up to $m=k-s_j\leq 2(n-1)-1$ (equal if k=2n-1 and we removed a 2). Note that $m\geq n-1$ and $s_j\leq n$. To construct numbers up to $m$ we can use the reduced lot (which we can because the statement holds for $n-1$). What about from $m+1$ to $k$? Let's call such a number $\ell$. We can construct $\ell-s_j$ from the reduced lot because $0\leq\ell-s_j\leq m$ (at least zero because $\ell\geq m+1\geq n$ and $s_j\leq n$; no more than $m$ because $\ell\leq k$, so $\ell-s_j\leq k-s_j=m$), and then we just add the $s_j$.

  • $\begingroup$ Can you clarify a bit more on why we cannot remove 1? Why will the sum be too big and what are the consequences? $\endgroup$ – user71346 May 17 '16 at 8:23
  • $\begingroup$ @user71346 If we remove 1 when $k=2n-1$, then the lot of $n-1$ numbers will add up to $2n-2$, so just over $2(n-1)-1$ so we can't use it to prove we can construct sums. We can remove 1 if $k<2n-1$, but then we have 2 separate cases, like my pre-edit answer. $\endgroup$ – Heimdall May 17 '16 at 8:29
  • $\begingroup$ Oh yes, you're right. Thanks. $\endgroup$ – user71346 May 18 '16 at 3:35

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.