# Finding the least element of the greatest elements of certain subsets of the natural numbers

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.

-
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

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$).