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.

This is a problem that a professor proposed for the highschool mathematical olympiad in Costa Rica that we haven't been able to solve. Therefore it cannot be asked since we don't have a solution yet in general.

Let $\mathcal{F}_{k}$ for a fixed $k \in \mathbb{N}$ be the family of subsets $A_i \subset \mathbb{N}$ that satisfy the following conditions:

1) The cardinality of $A_i$ is $k$ for every index $i$.

2) For every $A_i$ it holds that given any two different subsets of two elements $ \{ x, y \} \neq \{ z, w \}$, the absolute value of the differences between the elements of each subset are different

$$ |x - y| \neq |z - w|$$

Now we define a function $f: \mathcal{F}_k \rightarrow \mathbb{N}$ given by $$f(A_i) = \max{A_i}$$

The problem is to find the minimum of the image of $f$, that is to find

$$\min{f(\mathcal{F}_k)}$$

For instance, we know that for $k = 4$ the answer is $\min{f(\mathcal{F}_4)} = 7$ and for $k = 3 $ the answer is $\min{f(\mathcal{F}_3)} = 4$ but we don't have a general pattern for the solution, basically these were done by "brute force".

We would very much appreciate any help with this problem. Thanks a lot in advance.

share|improve this question
1  
Condition 2 is impossible if $k\gt 1$: pick $x\neq y$ in $A_i$, and consider $(x,x)$ and $(y,y)$ (or $(x,y)$ and $(y,x)$). –  Arturo Magidin Dec 1 '10 at 19:34
    
Could it be that condition 2 is meant to be "two-element subsets of $A_i$", rather than "two different ordered pairs"? Also, is the family the family of all subsets that satisfy the condition? –  Arturo Magidin Dec 1 '10 at 19:43
    
@Arturo You're absolutely right, I made a mistake with the ordered pairs. I have corrected it now. Thanks! –  Adrián Barquero Dec 1 '10 at 20:56
    
@Arturo And about your other question, yes, the family is the family of all subsets that satisfy the conditions. –  Adrián Barquero Dec 1 '10 at 21:02

1 Answer 1

up vote 10 down vote accepted

Here are some more values, starting from $\mathcal{F}_1$: $$1,2,4,7,12,18,26,35,45,56,73,86,107,128,152,178,200,217,247,284,334,357,373,426,481,493,\ldots$$ You're trying to find the shortest Golomb ruler of given size. I believe that the exact optimal values are unknown in general.

EDIT: This is A003022 (in which all numbers are $1$ less, e.g. $(0,)1,3,6,\ldots$).

share|improve this answer
    
+1 This is really interesting. Thanks! –  Adrián Barquero Dec 1 '10 at 21:19
    
Yuval, I hope you don't mind the edit; not everybody is familiar with OEIS. :) –  J. M. Dec 2 '10 at 12:08

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.