Problem (Combinatorics):
The Fibonacci numbers $F_{0}, F_{1}, F_{2}, \ldots$ are defined inductively by $F_{0}=0, F_{1}=1$, and $F_{n+1}=F_{n}+F_{n-1}$ for $n \geqslant 1$. Given an integer $n \geqslant 2$, determine the smallest size of a set $S$ of integers such that for every $k=2,3, \ldots, n$ there exist some $x, y \in S$ such that $x-y=F_{k}$.

Solution:
First we show that if a set $S \subset \mathbb{Z}$ satisfies the conditions then $|S| \geqslant \frac{n}{2}+1$.

Let $d=\lceil n / 2\rceil$, so $n \leqslant 2 d \leqslant n+1$. In order to prove that $|S| \geqslant d+1$, construct a graph as follows. Let the vertices of the graph be the elements of $S$. For each $1 \leqslant k \leqslant d$, choose two elements $x, y \in S$ such that $x-y=F_{2 k-1}$, and add the pair $(x, y)$ to the graph as edge. (Note that by the problem's constraints, there must be a pair $(x, y)$ with $x-y=F_{2 k-1}$ for every $3 \leqslant 2 k-1 \leqslant 2 d-1 \leqslant n$; moreover, due to $F_{1}=F_{2}$ we have a pair with $x-y=F_{1}$ as well.) We will say that the length of the edge $(x, y)$ is $|x-y|$.

We claim that the graph contains no cycle. For the sake of contradiction, suppose that the graph contains a cycle $\left(x_{1}, \ldots, x_{\ell}\right)$, and let the longest edge in the cycle be $\left(x_{1}, x_{\ell}\right)$ with length $F_{2 m+1}$. The other edges $\left(x_{1}, x_{2}\right), \ldots,\left(x_{\ell-1}, x_{\ell}\right)$ in the cycle are shorter than $F_{2 m+1}$ and distinct, their lengths form a subset of $\left\{F_{1}, F_{3}, \ldots, F_{2 m-1}\right\}$. But this is not possible because

$$
\begin{aligned}
F_{2 m+1} & =\left|x_{\ell}-x_{1}\right| \leqslant \sum_{i=1}^{\ell-1}\left|x_{i+1}-x_{i}\right| \leqslant F_{1}+F_{3}+F_{5}+\ldots+F_{2 m-1} \\
& =F_{2}+\left(F_{4}-F_{2}\right)+\left(F_{6}-F_{4}\right)+\ldots+\left(F_{2 m}-F_{2 m-2}\right)=F_{2 m}<F_{2 m+1} .
\end{aligned}
$$

Hence, the graph has $d$ edges and cannot contain a cycle, therefore it must contain at least $d+1$ vertices, so $|S| \geqslant d+1$.

Now we show a suitable set with $d+1$ elements. Let

$$
S=\left\{F_{0}, F_{2}, F_{4}, F_{5}, \ldots, F_{2 d}\right\}
$$

For $1 \leqslant k \leqslant d$ we have $F_{0}, F_{2 k-2}, F_{2 k} \in S$ with differences $F_{2 k}-F_{2 k-2}=F_{2 k-1}$ and $F_{2 k}-F_{0}=F_{2 k}$, so each of $F_{1}, F_{2}, \ldots, F_{2 d}$ occurs as difference between two elements in $S$. So this set containing $d+1$ numbers is suitable.



This page is intentionally left blank

Final answer: $\lceil n / 2\rceil+1$