Every possible length

Let S S be a subset of [ 0 , 1 ] [0,1] consisting of a union of 10 10 disjoint closed intervals I 1 , I 2 , , I 10 . I_1, I_2, \ldots, I_{10}.

Suppose S S has the property that for every d [ 0 , 1 ] , d \in [0,1], there are two points x , y S x,y \in S such that x y = d . |x-y|=d.

Letting s = n = 1 10 length ( I n ) , s = \sum\limits_{n=1}^{10} \text{length}(I_n), what is the minimum possible value of s ? s?

Your answer should be a rational number p q , \frac{p}{q}, where p p and q q are coprime positive integers.

Find p + q . p+q.


Bonus: Describe the sets S S for which the minimum is attained.


The answer is 11.

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

Patrick Corn
Nov 15, 2017

Let i \ell_i be the length of I i . I_i. Let D i j = { x y : x I i , y I j } . D_{ij} = \{ x-y : x \in I_i, y \in I_j\}. Then it should be clear that D i j D_{ij} is a closed interval inside [ 1 , 1 ] [-1,1] of length i + j . \ell_i + \ell_j.

The condition on distances implies that the union of the D i j , D_{ij}, for 1 i , j 10 , 1\le i,j \le 10, is the entire interval [ 1 , 1 ] . [-1,1]. So then 2 i = 1 10 j = 1 10 length ( D i j ) = i = 1 10 j = 1 10 ( i + j ) = i = 1 10 ( 10 i + s ) = 10 s + 10 s = 20 s . \begin{aligned} 2 \le \sum\limits_{i=1}^{10} \sum\limits_{j=1}^{10} \text{length}(D_{ij}) &= \sum\limits_{i=1}^{10} \sum\limits_{j=1}^{10} (\ell_i + \ell_j) \\ &= \sum\limits_{i=1}^{10} (10\ell_i + s) \\ &= 10s + 10s = 20s. \end{aligned} So we get s 1 / 10. s \ge 1/10.

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 D_{ij} is zero. But if the lengths of I i I_i and I j I_j are nonzero, it's immediately clear that D i i D_{ii} and D j j D_{jj} 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 / 10 ] { 2 / 10 } { 3 / 10 } { 9 / 10 } { 1 } S = [0,1/10] \cup \{2/10\} \cup \{3/10\} \cup \cdots \cup \{9/10\} \cup \{1\} has the all-distances property, with s = 1 / 10. s=1/10. So the answer is 1 + 10 = 11 . 1+10 = \fbox{11}.

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 / 10 , 1 ] [9/10,1] ).

Also, there was nothing special about 10 10 ; the same argument shows that if S S consists of k k disjoint intervals, the minimum possible value of the sum of the lengths of the intervals is 1 / k . 1/k.

According to this equation here we sustain the geometrical value stating that the underlying theory is not true...

Royce Arockiasamy - 3 years, 6 months ago

This is a really cool problem!! However, I discovered that the smaller value s = 10 1023 s =\frac{10}{1023} is possible (but perhaps still not optimal, I'm not sure). Let the interval be [ 0 , 1023 ] [0,1023] instead of [ 0 , 1 ] [0,1] for convenience. Then the ten intervals are [ 0 , 1 ] , [ 2 , 3 ] , [ 6 , 7 ] , [ 14 , 15 ] , [ 30 , 31 ] , [ 62 , 63 ] , [ 126 , 127 ] , [ 254 , 255 ] , [ 510 , 511 ] , [ 1022 , 1023 ] [0,1],[2,3],[6,7],[14,15],[30,31],[62,63],[126,127],[254,255],[510,511],[1022,1023] .

James Wilson - 3 years, 5 months ago

Log in to reply

This doesn't have the property you want. For instance, there are not two points x , y x,y in this set satisfying x y = 1000. |x-y| = 1000.

Patrick Corn - 3 years, 5 months ago

Log in to reply

Oh yes, you're right! I see where my mistake was now.

James Wilson - 3 years, 5 months ago

I'm a little confused by your proof though because D i j D_{ij} only considers distances between two points in opposite intervals, but not within the same interval.

James Wilson - 3 years, 5 months ago

Log in to reply

@James Wilson We're allowing i = j i=j in the sum, so that will take care of your intra-interval differences.

Patrick Corn - 3 years, 5 months ago

Log in to reply

@Patrick Corn Oh, duh. I went through your proof more carefully this time. Very nicely done.

James Wilson - 3 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...