Welcome to NRICH.

 
Euler Problem
By Isabelle Soh on Friday, September 07, 2001 - 10:17 am:

Hi guys,
I have a question for you to solve.

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.

Please help me and solve this problem.

Thanks,
Isy

By Michael Doré on Friday, September 07, 2001 - 11:38 am:

Write down your 34 numbers like so:

1
4,100
7,97
10,94
...
46,58
49,55
52

So in other words if you ignore the 1 and the 52, then your 34 numbers are made up of 16 separate pairs (starting with (4,100) ending with (49,55)).

The sum of the two numbers in each pair is 104. So if two numbers out of the 19 selected are going to add to 104, all we need is for two of the selected numbers to be in the same pair.

Well let's look at it the other way - if no two of the 19 selected add to 104 then no two can be chosen from the same pair. In other words we can select at most one from each pair.

We are allowed to select 1 and 52 because they aren't part of a pair. We must now choose another 17 from the pairs, but we're only allowed one from each pair. Well that quite simply isn't possible since there are only 16 pairs and we want at least 17 numbers from the pairs. Hence there is no way we can pick 19 numbers from your given numbers such that no two of them add to 104. In other words, however we pick 19 numbers out of the ones you've given, two of them will always add to 104.

By Isabelle Soh on Sunday, September 09, 2001 - 06:33 am:

Thanks for the help.... much appreciated