Each of 15 red balls and 15 green balls is marked with an integer between 1 and 100 inclusive; no integer appears on more than one ball. The value of a pair of balls is the sum of the numbers on the balls. Show that there are at least two pairs consisting on one red ball and one green ball, with the same value. Show that this is not true if there are 13 balls of each colour.
since each ball has a different number and if no two pairs have the same value there is going to be $15*15$ different sums. Looking at the numbers 1 through 100 the highest sum is 199 and lowest is 3, giving 197 possible sums. Since $15*15 = 225 > 197$ there must be two pairs with the same colour.
Looking at the 13 case, $13*13 = 169 < 197$ and so there is not necessarily two pairs with the same sum.
My question is; is my reasoning correct, is there a more elegant proof and what category does 14 fall under?
This question is from 'An Introduction to Combinatorics and Graph Theory' and falls under the Pigeon-Hole principle and Ramsey numbers.
For the case of 14, $14*14 = 196 < 197$ but which would indicate that there are not two pairs with the same sum, yet the question defaulted to 13 rather than 14 suggesting otherwise.
Best Answer
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.