3
$\begingroup$

How can I show that if 19 distinct integers are chosen from the sequence 1, 4, 7, 10, 13, 16, 19 . . ., 97, 100, there must be two of them whose sum is 104. What evidence is there? I am having a bit of trouble solving this. It would be appreciated if you could help. Thanks :)

$\endgroup$
5
$\begingroup$

Now there are $16$ such pairs which sum to $104$, from $4+100$ to $49+55$, which means that there are a total of $32$ integers in this pairs. In total, there are $\frac{100-1}{3}+1=34$ integers in the sequence, meaning that there are $34-32=2$ integers not in such pairs. This means that if you choose $2+16+1=19$ integers, even assuming that each integer is chosen from each separate pair or not in a pair at all, there still must be at least two of them which sum to $104$.

$\endgroup$
  • $\begingroup$ Actually there are 16 pairs, none of which includes starting number 1 and 52. So you can draw 18 numbers without summing to 104. But on the 19th draw you will definitely have drawn from the "other" set. $\endgroup$ – Mandar Kulkarni Jul 1 '17 at 4:49
  • 2
    $\begingroup$ It should be $4+100$ and I find $(49-4)/3+1=16$ pairs plus $1,52$ $\endgroup$ – Ross Millikan Jul 1 '17 at 4:49
  • $\begingroup$ Is it correct now? $\endgroup$ – user459244 Jul 1 '17 at 4:51
  • 1
    $\begingroup$ Yes, that is correct. $\endgroup$ – Ross Millikan Jul 1 '17 at 4:51
  • $\begingroup$ Thank you so much for helping guys! $\endgroup$ – Julie Jul 1 '17 at 10:15
4
$\begingroup$

Find pairs that sum to $104$. You can only have one of each of those pairs. How many pairs are there? How many numbers that are not part of a pair?

$\endgroup$
  • $\begingroup$ Good answer! Seems like it would work even if 18 distinct numbers were chosen in place of 19. $\endgroup$ – Mandar Kulkarni Jul 1 '17 at 4:45
  • $\begingroup$ @MandarKulkarni: No, there are $16$ pairs plus $1$ and $52$, so you can choose $18$ different numbers. $\endgroup$ – Ross Millikan Jul 1 '17 at 4:50
  • $\begingroup$ Ah yes...overlooked 52. Thanks for pointing it out. $\endgroup$ – Mandar Kulkarni Jul 1 '17 at 4:52

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.