All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
18 is not enough (Posted on 2017-06-06) Difficulty: 1 of 5
Let A be any set of 19 distinct integers chosen from the arithmetic progression 1, 4, 7,..., 100.

Prove that there must be two distinct integers in A whose sum is 104.

No Solution Yet Submitted by Ady TZIDON    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution Comment 2 of 2 |
Sets of 2 distinct integers that sum to 104 are:

 4 + 100
 7 +  97
46 +  58
49 +  55
but 52 + 52 are not distinct.

The sets that do consist of distinct integers have cardinality  16.

How many numbers can you choose, while avoiding both members of some pair? You can choose one member of each of the above pairs, amounting to 16 such numbers, but you can also include 1 and 52. That makes 18 without including both members of any pair.

But the choices left for the 19th number include only numbers that pair with one of the original set of 16 out of the 18 already chosen.

Of course this is the worst possible case; obviously some smaller sets may include pairs that add to 104.

  Posted by Charlie on 2017-06-06 11:22:53
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (2)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2020 by Animus Pactum Consulting. All rights reserved. Privacy Information