0

Question was too long to fit on title.

Fifteen different integers from 100 to 199 are given. Show that it is always possible to select from these 15 integers at least two different sets $\{a_1, b_1\}$ and $\{a_2, b_2\}$ such that the last two digits of $a_1 + b_1$ are the same as the last two digits of $a_2 + b_2$.

I know (blasted) pigeons are involved somehow, and I know in some way, if you choose 14 integers, then the 15th will overfill the "pigeonholes" and hence at least two different sets. But I don't have any idea how 14 could come out - any clues will be nice! Thanks.

user73229
  • 333
  • 3
  • 10

1 Answers1

3

Hint: Note that there are ${15 \choose 2}=105$ pairs. You are correct about pigeonholes.

Ross Millikan
  • 374,822
  • Ahh okay, I see where this proof is leading. But if the number 15 wasn't given to us, how would we formalize arriving at that number? Keep Guessing $C(n, 2)$'s? – user73229 Jun 11 '13 at 12:39
  • if you were interested in this flavour of problem, you might generate some code to pick a large amount of random pairs and see how many you need before you start to meet the condition – citedcorpse Jun 11 '13 at 12:41
  • 2
    You don't have to guess. If there is a range of $N$ numbers (in this case N=100) and you are asked to find two with equal sum $\pmod N$, you need (roughly-see the last sentence) $\frac 12n(n-1)\gt N$, so $n^2-n \gt 2N, n=\frac 12 + \frac 12 \sqrt{1+8N}$ – Ross Millikan Jun 11 '13 at 12:42
  • thanks! final question (sorry for asking so much) - what do we have to worry about if $a_1 = a_2$? – user73229 Jun 11 '13 at 12:58
  • @user73229: I missed the condition that they were all different, so you don't have to worry about that. But it is trivial, anyway. I have deleted that line – Ross Millikan Jun 11 '13 at 13:01