9
$\begingroup$

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.

  • 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)$).2010-12-01
  • 0
    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?2010-12-01
  • 0
    @Arturo You're absolutely right, I made a mistake with the ordered pairs. I have corrected it now. Thanks!2010-12-01
  • 0
    @Arturo And about your other question, yes, the family is the family of all subsets that satisfy the conditions.2010-12-01

1 Answers 1

10

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

  • 0
    Yuval, I hope you don't mind the edit; not everybody is familiar with OEIS. :)2010-12-02