# Pigeonhole principle problem 104

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 :)

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$.

• 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. – Mandar Kulkarni Jul 1 '17 at 4:49
• It should be $4+100$ and I find $(49-4)/3+1=16$ pairs plus $1,52$ – Ross Millikan Jul 1 '17 at 4:49
• Is it correct now? – user459244 Jul 1 '17 at 4:51
• Yes, that is correct. – Ross Millikan Jul 1 '17 at 4:51
• Thank you so much for helping guys! – Julie Jul 1 '17 at 10:15

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?

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