Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $p_n$ be a pairwise partition of $\{1,2,...,2n\}, n\in \bf N$ where $(a,b)\in p \implies a<b$, and $P_n$ the set of all such pairwise partition. $d(n) := \min_{p_n\in P_n}\big[\max\big(\big|\frac{a}{b}-\frac{c}{d}\big|, (a,b),(c,d)\in p_n\big)\big]$.

Conjecture: The fraction set from the pairwise partition that achieves $d(n)$ for $n=\frac{3^{i+1}-1}{2}, \,i\in \bf N$ is $\big\{\frac{1}{2},\frac{3}{6},\frac{4}{7},\frac{5}{8}...,\frac{3^i}{2\times3^i},\frac{3^i+1}{2\times 3^i+1},\frac{3^i+2}{2\times3^i+2},...,\frac{2\times3^i-1}{3\times 3^i-1}\big\}$. The other $n$ are constructed similarly.

share|improve this question
    
You do not require $\gcd(a,b)=1$? –  Hagen von Eitzen Nov 12 '13 at 20:58
    
@HagenvonEitzen, no. The fraction is for all pairwise partition so that the fraction is less than $1$. –  Hans Nov 12 '13 at 21:14
    
I am confused by your question. There are a lot of subscripts $n$ around. It sounds like you partition $\{1,2,\dots,2n\}$ into $n$ pairs, call them $p_i$. Then for each partition you look for the greatest difference in the fractions created from two of the pairs. Finally you take the minimum of that over all the partitions. Is that what you mean? –  Ross Millikan Nov 12 '13 at 23:40
    
To make sure I am following you, let us take the partition $(1,2),(3,4),(5,6),\dots,(2n-1,2n)$ Then the max for this partition is $\frac {2n-1}{2n}-\frac 12=\frac {n-1}{2n}$ and we are looking to reduce this with a more clever partition. For $n=4$ we could have $(1,2),(3,6),(4,7),(5,8)$ with max $\frac 47- \frac 12 = \frac 1{14}$ –  Ross Millikan Nov 12 '13 at 23:53
    
@RossMillikan: You are exactly right, both in your general reformulation and example. –  Hans Nov 13 '13 at 0:16

1 Answer 1

I believe $(1,2)$ will always be one of the pairs unless $n=2$ when the optimum is $(1,3),(2,4)$ with $d(2)=\frac 16$. There will always be a fraction at least $\frac 12$, because one of the numerators is at least $n$. If $1$ is paired with something else, the diameter is at least $\frac 16$ When $2$ or $3$ is used as a denominator, one numerator is at least $n+1$ and that fraction will be strictly greater than $\frac 12$. It seems easy to keep all the fractions large enough that you would rather have the $\frac 12$ than $\frac 13$

For $n=6$, the best I can do is $(1,2),(3,6),(4,9),(5,10),(7,11),(8,12)$, though you can swap $5,6$ with diameter $\frac 8{12}-\frac 49=\frac 29$

I think the normal structure of the optimum will be about this: $(1,2$), some number of fractions that are equal to $\frac 12$, and the rest with all the small numbers in the first position in order and the large ones in the second position in order. For $n=12$ I get $(1,2),(3,6),(4,8),(5,10),(7,14),(9,18),(10,19),(12,20),(13,21),(15,22),(16,23),(17,24)$ with $d(12)=\frac 5{24}$ This is by hand search-there may be something better out there.

Following this strategy, assume there are $k$ pairs that equal exactly $\frac 12$. The numerators will be all the odd numbers, four times the odds, sixteen times the odds, etc. As $n$ gets large, this is $\frac 23$ of the numbers, so the largest numerator will be about $\frac 32k$. We then have $n-k$ more pairs, and have used about $\frac k2$ numbers greater than $\frac 32k$, so the last numerator will be about $n+k$. The first denominator after the halves will be $n+k + 1$ To make sure this fraction is at least $\frac 12$, we need $2(\frac 32k+2)=n+k +1$ or $k=\frac 12(n-3)$. In the limit of large $n$, we have the final fraction is then $\frac {\frac 32n}{2n}=\frac 34$ and the diameter is $\frac 1{4}$

Definitely not proven, but I hope some useful thoughts. An interesting problem. There could be some improvement by letting the first (few) fractions after the halves drop below. We saw that in the $n=4$ solution.

share|improve this answer
    
In your sentence "The numerators will be all the odd numbers, four times the odds, sixteen times the odds, etc.", is the progression in the factor of the odd number $2^{2i}, i\in \bar{{\bf Z}^-}$? Why is that? Also can you explain "As $n$ gets large, this is $\frac 23$ of the numbers"? –  Hans Nov 14 '13 at 4:30
    
@Hansen: If you look at the pattern, all the odd numbers are numerators. We then have twice the odd numbers as denominators. The four times the odd numbers are available as numerators again. For the $\frac 23$, it is because $\frac 12$ (the odds) + $\frac 18$ (the multiples of four but not eight) + $\frac 1{32}$ (the multiples of 16 but not 32)+...=$\frac 23$ –  Ross Millikan Nov 14 '13 at 4:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.