# Not sure how to prove this statement by contradiction?

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$
$i=1:1$
$i=2:2$
$i=3:3$
$i=4:4$
$i=5:5$
$i=6:1+5=2+4$
$i=7:2+5=3+4$
$i=8:3+5$
$i=9:4+5$
$i=10:1+4+5$
$i=11:2+4+5$
$i=12:3+4+5$
$i=13:1+3+4+5$
$i=14:2+3+4+5$
$i=15:1+2+3+4+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.

EDITED

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

• I would try a proof by induction. – Doug M May 17 '16 at 6:06
• @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? – 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$.
• @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. – Heimdall May 17 '16 at 8:29