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