Let S be a set of 1 3 distinct, pairwise relatively prime, positive integers. What is the smallest possible value of s ∈ S max − s ∈ S min ?
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.
In fact, { 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 7 , 2 9 , 3 1 , 3 5 , 3 7 , 4 1 , 4 3 } suffices as being the thirteen with the smallest total sum (I think).
Log in to reply
Triplet? Your example is fine, since you can add 1 6 or 3 2 to make the thirteenth number. Your question did not ask to minimize m a x S , though - just the range.
Log in to reply
Oops, typo, but yeah, the question didn't ask to minimise max S . It would be an extension of the problem.
Where exactly did you use the fact that ∣ T ∣ < 3 2 ?
Log in to reply
Oh nevermind, I figured it out. It was in the definition of T 0
Problem Loading...
Note Loading...
Set Loading...
The set S = { 1 7 , 1 9 , 2 3 , 2 5 , 2 7 , 2 9 , 3 1 , 3 2 , 3 7 , 4 1 , 4 3 , 4 7 , 4 9 } shows that it is possible to find a set of 1 3 mutually coprime positive integers with range 3 2 .
Suppose that it were possible to find a set of 1 3 mutually coprime positive integers with range less than 3 2 . At most one of these integers can be even, and so we would have to be able to find a set T of 1 2 mutually coprime odd positive integers with range less than 3 2 . This set T would be a subset of T 0 = { n , n + 2 , n + 4 , n + 6 , n + 8 , n + 1 0 , n + 1 2 , n + 1 4 , n + 1 6 , n + 1 8 , n + 2 0 , n + 2 2 , n + 2 4 , n + 2 6 , n + 2 8 , n + 3 0 } for some odd n ∈ T . Note that T 0 has 1 6 elements. Now all the members of one of the three sets { n , n + 6 , n + 1 2 , n + 1 8 , n + 2 4 , n + 3 0 } { n + 2 , n + 8 , n + 1 4 , n + 2 0 , n + 2 6 } { n + 4 , n + 1 0 , n + 1 6 , n + 2 2 , n + 2 8 } are multiples of 3 . Whichever of the three sets it is, T can only contain one element from that set, and so 4 or 5 elements of T 0 will not belong to T . Since T is meant to contain 1 2 elements, we must have only discarded 4 elements from T 0 . Thus we deduce that n is not a multiple of 3 , and hence we one of the two sets A = { n + 2 , n + 8 , n + 1 4 , n + 2 0 , n + 2 6 } B = { n + 4 , n + 1 0 , n + 1 6 , n + 2 2 , n + 2 8 } consists of multiples of 3 , and we must discard four elements of the relevant set ( A or B ) to ensure that no two elements of T are multiples of 3 . Having discarded these four elements, we have obtained the set T . Now consider the sets { n , n + 1 0 , n + 2 0 , n + 3 0 } { n + 2 , n + 1 2 , n + 2 2 } { n + 4 , n + 1 4 , n + 2 4 } { n + 6 , n + 1 6 , n + 2 6 } { n + 8 , n + 1 8 , n + 2 8 } No two elements of A differ by 1 0 , and so no two elements of A belong to the same one these five sets. Similarly no two elements of B belong to the same one of these five sets. Thus, whichever four elements have been removed from T 0 , and whichever of the above five sets contains the multiples of 5 , we see that T will contain two multiples of 5 , which is not possible.
Thus the least possible range is 3 2 .