You can bound it, but can you construct it?

Let S S be a set of 13 13 distinct, pairwise relatively prime, positive integers. What is the smallest possible value of max s S min s S \max \limits_{s\in S} - \min \limits_{s \in S} ?


The answer is 32.

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.

1 solution

Mark Hennings
Nov 10, 2017

The set S = { 17 , 19 , 23 , 25 , 27 , 29 , 31 , 32 , 37 , 41 , 43 , 47 , 49 } S = \{ 17,19,23,25,27,29,31,32,37,41,43,47,49\} shows that it is possible to find a set of 13 13 mutually coprime positive integers with range 32 32 .

Suppose that it were possible to find a set of 13 13 mutually coprime positive integers with range less than 32 32 . At most one of these integers can be even, and so we would have to be able to find a set T T of 12 12 mutually coprime odd positive integers with range less than 32 32 . This set T T would be a subset of T 0 = { n , n + 2 , n + 4 , n + 6 , n + 8 , n + 10 , n + 12 , n + 14 , n + 16 , n + 18 , n + 20 , n + 22 , n + 24 , n + 26 , n + 28 , n + 30 } T_0 = \{n,n+2,n+4,n+6,n+8,n+10,n+12,n+14,n+16,n+18,n+20,n+22,n+24,n+26,n+28,n+30\} for some odd n T n \in T . Note that T 0 T_0 has 16 16 elements. Now all the members of one of the three sets { n , n + 6 , n + 12 , n + 18 , n + 24 , n + 30 } { n + 2 , n + 8 , n + 14 , n + 20 , n + 26 } { n + 4 , n + 10 , n + 16 , n + 22 , n + 28 } \{n,n+6,n+12,n+18,n+24,n+30\} \hspace{1cm} \{n+2,n+8,n+14,n+20,n+26\} \hspace{1cm} \{n+4,n+10,n+16,n+22,n+28\} are multiples of 3 3 . Whichever of the three sets it is, T T can only contain one element from that set, and so 4 4 or 5 5 elements of T 0 T_0 will not belong to T T . Since T T is meant to contain 12 12 elements, we must have only discarded 4 4 elements from T 0 T_0 . Thus we deduce that n n is not a multiple of 3 3 , and hence we one of the two sets A = { n + 2 , n + 8 , n + 14 , n + 20 , n + 26 } B = { n + 4 , n + 10 , n + 16 , n + 22 , n + 28 } A = \{n+2,n+8,n+14,n+20,n+26\} \hspace{1cm} B = \{n+4,n+10,n+16,n+22,n+28\} consists of multiples of 3 3 , and we must discard four elements of the relevant set ( A A or B B ) to ensure that no two elements of T T are multiples of 3 3 . Having discarded these four elements, we have obtained the set T T . Now consider the sets { n , n + 10 , n + 20 , n + 30 } { n + 2 , n + 12 , n + 22 } { n + 4 , n + 14 , n + 24 } { n + 6 , n + 16 , n + 26 } { n + 8 , n + 18 , n + 28 } \{n,n+10,n+20,n+30\} \hspace{1cm} \{n+2,n+12,n+22\} \hspace{1cm} \{n+4,n+14,n+24\} \hspace{1cm} \{n+6,n+16,n+26\} \hspace{1cm} \{n+8,n+18,n+28\} No two elements of A A differ by 10 10 , and so no two elements of A A belong to the same one these five sets. Similarly no two elements of B B belong to the same one of these five sets. Thus, whichever four elements have been removed from T 0 T_0 , and whichever of the above five sets contains the multiples of 5 5 , we see that T T will contain two multiples of 5 5 , which is not possible.

Thus the least possible range is 32 \boxed{32} .

In fact, { 11 , 13 , 17 , 19 , 23 , 27 , 29 , 31 , 35 , 37 , 41 , 43 } \{11, 13, 17, 19, 23, 27, 29, 31, 35, 37, 41, 43\} suffices as being the thirteen with the smallest total sum (I think).

Sharky Kesa - 3 years, 7 months ago

Log in to reply

Triplet? Your example is fine, since you can add 16 16 or 32 32 to make the thirteenth number. Your question did not ask to minimize m a x S \mathrm{max}\, S , though - just the range.

Mark Hennings - 3 years, 7 months ago

Log in to reply

Oops, typo, but yeah, the question didn't ask to minimise max S \max S . It would be an extension of the problem.

Sharky Kesa - 3 years, 7 months ago

Where exactly did you use the fact that T < 32 |T| < 32 ?

Jason Martin - 3 years, 7 months ago

Log in to reply

Oh nevermind, I figured it out. It was in the definition of T 0 T_0

Jason Martin - 3 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...