For the $14$ case, we show that there exist at least one number from set $\{3,4,5,...,17\}$ is not obtainable and at least one number from set $\{199,198,...,185\}$ is not obtainable.
First consider the set $\{3,4,5,...,17\}$.
Suppose all numbers in this set are obtainable.
Then since $3$ is obtainable, $1$ and $2$ are of different color. Then since $4$ is obtainable, $1$ and $3$ are of different color. Now suppose $1$ is of one color and $2,3,...,n-1$ where $n-1<17$ are of the same color that is different from $1$'s color, then if $n<17$ in order for $n+1$ to be obtainable $n$ and $1$ must be of different color so $2,3,...,n$ are of same color. Hence by induction for all $n<17$, $2,3,...,n$ must be of same color. However this means there are $16-2+1=15$ balls of the color contradiction.
Hence there exist at least one number in the set not obtainable.
We can use a similar argument to show if all elements in $\{199,198,...,185\}$ are obtainable then $99,98,...,85$ must all be of the same color which means there are $15$ balls of the color contradiction so there are at least one number not obtainable as well.
Now we have only $195$ choices left and $196>195$ so $14$ case is the same as the $15$ case where identical sum must appear.
As to the comment, I constructed a counter-example list for the $13$ case as follows. The idea of constructing this list is similar to the proof for the $14$ case.
Red: $(1,9,16,23,30,37,44,51,58,65,72,79,86)$
Green: $(2,3,4,5,6,7,8;94,95,96,97,98,99)$
Note that $86+8=94$ and $1+94=95$ so there are no duplicated sum.
It's hard to think about questions such as these because there's lots of quantifiers. So here's a special case of question 1:
Show that the set $S = \{1, 3, 4, 7, 9, 10, 11, 13, 16, 19\}$ must have two three-element subsets with the same sum.
Now that the question is this specific, we can of course solve the problem by inspection: $\{1,10,19\}$ and $\{9,10,11\}$ have the same sum, for example. But we also want to generalize this to other sets eventually.
So here's an argument that generalizes: there are $\binom{10}{3} = \frac{10\cdot 9\cdot 8}{6} = 120$ different three-element subsets of $S$. The smallest possible sum is $1+3+4 = 8$ and the largest possible sum is $13+16+19=48$, so all three-element subsets have a sum between $8$ and $48$. Since this leaves only $41$ possibilities for the sum, and there's $120$ three-element subsets, some two of those subsets must have the same sum.
So now, to find answers to your questions, we need to:
- Show that the same argument holds when $S$ is any ten-element subset of $\{1, 2, 3, \dots, 40\}$. We don't know what the smallest and largest possible sum are in $S$ without knowing $S$; but how small and how big can they get?
- Once you've figured out the answer to question 1, for what values of $m$ in place of $40$ would the same argument work? (How does the range of possible sums depend on the value of $40$?)
- Can you make the same argument work with two-element subsets instead of three-element subsets?
Best Answer
First off, your method of choosing some numbers is incorrect. $50$ and $51$ do add to $101$, but if $k=2$, then the question would say that whatever two numbers we pick, they would sum to $101$. But if we say, chose $1$ and $2$, these clearly don't add to $101$. What we want is no matter which $k$ numbers we pick, we can find two that sum to $101$.
The best way to think about this is to think not of individual numbers, but of pairs.
What I mean by this, is instead of $100$ numbers from $1$ to $100$, we now have $50$ pairs $$\{(1,100), (2,99), (3,98), ..., (50,51) \}$$ And now, it should become apparent that in order to choose no pairs that sum to $101$, we must choose a number from each pair at most once. Thus, when we choose numbers from $51$ pairs, by pidgeonhole principle, we will have chosen both numbers from some pair, and thus have two numbers adding to $101$. Hope that helps!