Pairwise Distinct Sums

Let S S be a set containing 10 distinct, positive integers, with the property that no two pairwise sums of S S are the same. What is the least possible value of the greatest element of S S ?

Image credit: Washington Post


The answer is 89.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Aditya Raut
Feb 8, 2014

Starting from the smallest element a 1 a_1 to the largest a 10 a_{10} -

Clearly, smallest one i.e. a 1 a_1 will be 1.

Next, we can have smallest possible a 2 = 2 a_2=2

Thus Further we need to have 8 numbers such that all possible pairs of other 8 must be having their difference more than 1...

Thus a 3 a_3 can be 3 but a 4 a_4 can't be 4 as then 4 + 1 = 2 + 3 4+1=2+3

Now a 4 a_4 has to be chosen such that it's difference should be more than 1 1 from a 3 a_3 as a 2 a 1 = 1 a_2-a_1=1

So a 4 a_4 has smallest possible value 5 5 due to this condition (because 5 3 > 1 5-3>1 )

because now we have a 3 = 3 a_3=3 and a 1 = 1 a_1=1 with difference 2 2 , a 5 a_5 must be greater than a 4 a_4 by at least 3 ... Hence smallest possible a 5 = a 4 + 3 = 8 a_5=a_4+3=8

Now a 4 a 1 = 4 a_4-a_1=4 hence difference of a 5 a_5 and a 6 a_6 must be greater than 4....i.e. 5 so a 6 = a 5 + 5 = 13 a_6=a_5+5=13

According to this logic, resulting sequence is the famous FIBONACCI SEQUENCE and we need to find a 10 a_{10} where a n = a n 1 + a n 2 a_n=a_{n-1}+a_{n-2} And a 1 = 1 , a 2 = 2 a_1=1,a_2=2 hence the sequence is

1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 1,2,3,5,8,13,21,34,55,89 thus a 10 = 89 a_{10}=89

What's wrong with S = {1, 2, 3, 5, 8, 13, 21, 30, 39, 53} making 53 as the least possible integer with the given constraints.

All the C(10, 2) = 45 pairwise sums are listed below in a sorted order with no two the same. {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 18, 21, 22, 23, 24, 26, 29, 31, 32, 33, 34, 35, 38, 40, 41, 42, 43, 44, 47, 51, 52, 54, 55, 56, 58, 60, 61, 66, 69, 74, 83, 92}

The answer, therefore, is 53.

Shamik Banerjee - 7 years, 4 months ago

Log in to reply

This has been an AMC problem from 2011 or 2012. It was 53.

Trevor B. - 7 years, 4 months ago

well, then it could also be {1,2,4,7,10,13,16,19,22,25} making the least possible of value of the greatest element 25

viswajit sasi - 7 years, 4 months ago

Log in to reply

No, that's not the case. The elements of your set are not meeting the requirements as many pairwise sums are the same viz. 1 + 16 = 4 + 13 = 7 + 10 = 17.

Shamik Banerjee - 7 years, 4 months ago
Awantika Rajput
Feb 10, 2014

The problem has the application of fibonacci series. It is a series or set of positive integers such that the sum or the difference of no two pair of numbers is same. S={ 1, 2, 3, 5, 8, 13, 21, 34...} The first and second term of the series is 1 and 2. Each term starting from 3 is the sum of its previous two terms. For Eg. 1+2=3; 2+3=5; 3+5=8; 5+8=13 and so on.. The terms so formed have unique sum and difference pairwise.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...