Let S be a subset of [ 0 , 1 ] consisting of a union of 1 0 disjoint closed intervals I 1 , I 2 , … , I 1 0 .
Suppose S has the property that for every d ∈ [ 0 , 1 ] , there are two points x , y ∈ S such that ∣ x − y ∣ = d .
Letting s = n = 1 ∑ 1 0 length ( I n ) , what is the minimum possible value of s ?
Your answer should be a rational number q p , where p and q are coprime positive integers.
Find p + q .
Bonus: Describe the sets S for which the minimum is attained.
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.
According to this equation here we sustain the geometrical value stating that the underlying theory is not true...
This is a really cool problem!! However, I discovered that the smaller value s = 1 0 2 3 1 0 is possible (but perhaps still not optimal, I'm not sure). Let the interval be [ 0 , 1 0 2 3 ] instead of [ 0 , 1 ] for convenience. Then the ten intervals are [ 0 , 1 ] , [ 2 , 3 ] , [ 6 , 7 ] , [ 1 4 , 1 5 ] , [ 3 0 , 3 1 ] , [ 6 2 , 6 3 ] , [ 1 2 6 , 1 2 7 ] , [ 2 5 4 , 2 5 5 ] , [ 5 1 0 , 5 1 1 ] , [ 1 0 2 2 , 1 0 2 3 ] .
Log in to reply
This doesn't have the property you want. For instance, there are not two points x , y in this set satisfying ∣ x − y ∣ = 1 0 0 0 .
Log in to reply
Oh yes, you're right! I see where my mistake was now.
I'm a little confused by your proof though because D i j only considers distances between two points in opposite intervals, but not within the same interval.
Log in to reply
@James Wilson – We're allowing i = j in the sum, so that will take care of your intra-interval differences.
Log in to reply
@Patrick Corn – Oh, duh. I went through your proof more carefully this time. Very nicely done.
Problem Loading...
Note Loading...
Set Loading...
Let ℓ i be the length of I i . Let D i j = { x − y : x ∈ I i , y ∈ I j } . Then it should be clear that D i j is a closed interval inside [ − 1 , 1 ] of length ℓ i + ℓ j .
The condition on distances implies that the union of the D i j , for 1 ≤ i , j ≤ 1 0 , is the entire interval [ − 1 , 1 ] . So then 2 ≤ i = 1 ∑ 1 0 j = 1 ∑ 1 0 length ( D i j ) = i = 1 ∑ 1 0 j = 1 ∑ 1 0 ( ℓ i + ℓ j ) = i = 1 ∑ 1 0 ( 1 0 ℓ i + s ) = 1 0 s + 1 0 s = 2 0 s . So we get s ≥ 1 / 1 0 .
Is this in fact the minimum? Well, the inequality is an equality if and only if the length of the overlap between any two D i j is zero. But if the lengths of I i and I j are nonzero, it's immediately clear that D i i and D j j have an overlap of nonzero length. So equality can hold only if at most one of the intervals has nonzero length. And in fact, S = [ 0 , 1 / 1 0 ] ∪ { 2 / 1 0 } ∪ { 3 / 1 0 } ∪ ⋯ ∪ { 9 / 1 0 } ∪ { 1 } has the all-distances property, with s = 1 / 1 0 . So the answer is 1 + 1 0 = 1 1 .
This argument shows, I believe, that the only sets where the minimum is attained are the one above and its mirror image (nine points plus [ 9 / 1 0 , 1 ] ).
Also, there was nothing special about 1 0 ; the same argument shows that if S consists of k disjoint intervals, the minimum possible value of the sum of the lengths of the intervals is 1 / k .