2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The $13$ case has not really been done. You have shown that a particular argument fails to give a contradiction. But that does not necessarily show that there are no two pairs with the same sum. One has to exhibit an example where there are not. $\endgroup$ – André Nicolas Nov 19 '15 at 1:50
  • $\begingroup$ For the 9 case a naive algorithm produced red 1,3,7,13,22,24,47,70,76, green 2,5,10,18,32,40,60,82,90, pairwise sums 3,5,6,8,9,11,12,13,15,17,18,19,21,23,24,25,26,27,29,31,32,33,34,35, 39,40,41,42,43,45,47,49,52,53,54,56,57,61,62,63,64,65,67,72,73,75, 78,79,80,81,82,83,84,85,86,87,88,89,91,93,94,95,97,102,103,104,106, 107,108,110,112,114,116,129,130,136,137,152,158,160,166. For the 10 case this algorithm failed, producing partial red list 1,3,7,13,22,24,47,70,76 (missing 10th element, cannot be extended) and green 2,5,10,18,32,40,60,82,90,98. For case 13 a better algorithm is needed. $\endgroup$ – Mirko Nov 19 '15 at 5:14
  • $\begingroup$ If the inclusive includes the end points, there's actually sums as low as 2 ,and as high as 200, making 199 sums. It still holds, that with 15*15 matchups, that at least 2 have to have the same sum. But, your math is imprecise. $\endgroup$ – user451844 Jun 27 '17 at 12:36
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I may figure what you are saying if I keep reading, but you (1) do not define "obtainable" and (2) isn't it possible that $n+1$ is obtainable in some different way than $1+n$, e.g. $5+(n-4)$ ? $\endgroup$ – Mirko Nov 19 '15 at 5:22
  • $\begingroup$ (1) A number $x$ is obtainable means "there exist two balls of different color such that there sum is $x$". (2) By our induction hypothesis all balls of $2,3,4,...,n-1$ are of the same color so $1+n$ is the only possibility left. $\endgroup$ – cr001 Nov 19 '15 at 5:25
  • $\begingroup$ Got it, thank you, looks right. I wonder which numbers might work for case 13: My naive attempt to come up with specific numbers failed already at case 10 as commented after the question, so I need a better algorithm, assuming that case 13 is doable, as it appears from the statement. Thank you for the case 14 answer, nicely done. $\endgroup$ – Mirko Nov 19 '15 at 5:40
  • $\begingroup$ I have edited the answer to add a counter-example for the $13$ case. $\endgroup$ – cr001 Nov 19 '15 at 6:06
  • $\begingroup$ one may generalize (optional :) allowing $x$ red balls and $y$ green balls, calling this the $(x,y)$ case. You may add the number $100$ to the list of green balls in your case $13$ example, producing a $(13,14)$ example. Whenever $x\cdot y\le197$ one may ask if there is a $(x,y)$ example, in particular if there is a $(13,15)$ example. But I may look at this myself, using the ideas in your answer. At any rate, concerning the question if there is a more elegant proof, I personally cannot think of something better than what is already described in the question and this answer. $\endgroup$ – Mirko Nov 19 '15 at 7:06

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.