Taiwan IMO Selection Camp, 2021

The lower bound is $|S| \ge d+1$, where $d$ is the smallest integer greater than or equal to $\frac{n}{2}$.

1. Estimation: Let us construct a graph $G$ using the elements of $S$ as vertices, with edges drawn as follows: for each $1 \le k \le d$, find a pair $x, y \in S$ satisfying $|x - y| = F_{2k-1}$, and draw an edge between $x$ and $y$; if there is more than one pair $(x, y)$ satisfying $|x - y| = F_{2k-1}$, take only one such pair to draw the edge. At the same time, define the length of the edge $(x, y)$ to be $|x - y|$.

We now prove that $G$ contains no cycle. Suppose $G$ has a cycle $(x_1, x_2, \dots, x_\ell)$, and without loss of generality assume that the longest edge in this cycle is $|x_1 - x_\ell| = F_{2m+1}$. Note that the lengths of the other edges in this cycle belong to $\{F_1, F_3, \dots, F_{2m-1}\}$ and are all distinct. But this implies
$$\begin{aligned} F_{2m+1} &= |x_{\ell} - x_{1}| \le \sum_{i=1}^{\ell-1} |x_{i+1} - x_{i}| \\ &= F_1 + F_3 + \dots + F_{2m-1} \\ &= F_2 + (F_4 - F_2) + \dots + (F_{2m} - F_{2m-2}) = F_{2m} < F_{2m+1}, \end{aligned}$$
which is a contradiction! Therefore, $G$ has at least $d$ edges and contains no cycle, so $G$ must have at least $d+1$ vertices, that is, $|S| \ge d+1$.

2. Construction: Consider $S = \{F_0, F_2, \dots, F_{2d}\}$, then we have $F_{2k} - F_{2k-2} = F_{2k-1}$ and $F_{2k} - F_0 = F_{2k}$.