The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$. Proposed by Croatia
Problem
Source: ISL 2020 C4
Tags: Fibonacci, combinatorics, IMO Shortlist, IMO Shortlist 2020, additive representation
Davsch
21.07.2021 02:13
The answer is $\left\lceil\frac n2\right\rceil+1$. Obviously, the set $S=\{F_0,F_2,\hdots,F_{2d}\}$ works. Now consider a graph whose vertices are the elements of $S$. If for $x,y\in S$, the number $x-y=F_{2k-1}$ is a Fibonacci number with odd index, join them by an edge with colour $k$. Also, remove duplicate edges with the same colour. By the problem statement, every edge appears exactly once.
The resulting graph cannot have cycles, since $F_{2k+1}>\sum\limits_{i=0}^{k-1}F_{2i+1}$. Thus, $|S|=|V|\geq |E|+1=\left\lceil\frac n2\right\rceil+1$.
IndoMathXdZ
21.07.2021 02:18
The answer is $\left \lceil \frac{n}{2} \right \rceil + 1$, which is achievable by the following construction: \[ \{ F_0, F_2, \dots, F_{2 \cdot \lceil n/2 \rceil} \} \]Now, to prove the bound, construct a graph $G$ with elements of $S$ as its vertices, and for each $1 \le k \le \lceil n/2 \rceil$, connect two pair of unique vertices $(x,y)$ with an edge if $x - y = F_{2k - 1}$, using the fact that $F_1 = F_2$ and the condition of the problem. Claim. $G$ has no cycle. Proof. Suppose otherwise, that it contains a cycle with elements $(x_1, x_2, \dots, x_{m})$. Consider the largest difference in this cycle (WLOG it is $(x_1,x_m)$ with $|x_1 - x_m| = F_{2i + 1}$.) Therefore, by assumption, since $(x_1, x_2), (x_2, x_3), \dots, (x_{m - 1}, x_m)$ are all an edge, then $|x_{j + 1} - x_j|$ are the elements of $\{ F_1, F_3, \dots, F_{2i - 1} \}$ and are all distinct. However, notice that by Triangle Inequality, \begin{align*} F_{2i + 1} &= |x_{m} - x_1| \\ &\le \sum_{j = 1}^{m - 1} |x_{j + 1} - x_j| \\ &\le F_1 + F_3 + \dots + F_{2i - 1} \\ &= F_{2i} \end{align*}from which this gives us a contradiction. Therefore, this graph $G$ is a tree; and since $G$ needs to have $\lceil n/2 \rceil $ edge, then it must have at least $\lceil n/2 \rceil + 1$ vertices.
sn6dh
21.07.2021 02:34
Lemma: $\forall n\geq 2,\ F_n>\sum_{i=1}^{\lceil\frac{n-2}2\rceil}F_{n-2i}$. proof: induction on $n$. For the base case $n=2$ and $n=3$, $F_2, F_3>0$ is trivial. Assume that for $n=k-2$, the lemma holds. For $n=k$, $F_k=F_{k-1}+F_{k-2}>2F_{k-2}>F_{k-2}+\sum_{i=2}^{\lceil\frac{k-2}2\rceil}F_{k-2i}=\sum_{i=1}^{\lceil\frac{k-2}2\rceil}F_{k-2i}$. $\therefore$ by induction, the lemma holds for all $n\geq 2$. Let $S_n$ denote the set $S$ with the smallest size that satisfies the given condition. Let's have an induction on $n$ to prove that $|S_n|\geq\lceil\frac{n+2}2\rceil$. For the base case $n=2$ and $n=3$, $|S_2|\geq 2$ and $|S_3|\geq 3$ is trivial. Assume that for $n=k-2$, $|S_{k-2}|\geq\lceil\frac k2\rceil$. For $n=k$, if $|S_{k-2}|\geq\lceil\frac{k+2}2\rceil$ then by $|S_k|\geq |S_{k-2}|$ we are done. Otherwise, $|S_{k-2}|=\lceil\frac k2\rceil$. Construct a graph $G$, where $V(G)=S_{k-2}$, and edge $ab$ exists $\iff\exists 1\leq i\leq \lceil\frac k2\rceil-1$ s.t. $|a-b|=F_{k-2i}$. By lemma, there is no cycle in this graph; by the assumption of the induction, edge $ab$ with $|a-b|=F_{k-2i}$ exists $\forall 1\leq i\leq \lceil\frac k2\rceil-1$, and there are at least $\lceil\frac k2\rceil-1$ edges in total. $\therefore G$ is a tree, and the max element $-$ the min element of $S_{k-2}\leq\sum_{i=1}^{\lceil\frac k2\rceil-1}F_i<F_k$ $\therefore |S_k|>|S_{k-2}|$ $\therefore |S_k|\geq\lceil\frac{k+2}2\rceil$ $\therefore$ by induction, $\forall n\geq 2,\ |S_n|\geq\lceil\frac{n+2}2\rceil$ Construction of $S_n$: $\{F_{2i}|0\leq i\leq\lceil\frac n2\rceil\}$.
TheUltimate123
21.07.2021 02:44
The answer is \(k=\lceil\frac n2\rceil+1\), achieved by \(S=\{F_0,F_2,F_4,\ldots,F_{2k-2}\}\). I will show for each \(k\ge2\), if \(|S|=k\), then \(S-S\) contains at most \(2k-3\) distinct Fibonacci numbers. (If \(k=1\), then at most 0.) To this end, we strong induct on \(k\), with base cases \(k=1\) and \(k=2\) trivial. Draw a graph \(G\) with \(k\) vertices representing the \(k\) elements of \(S\). For each (distinct) Fibonacci number \(f\), draw an edge between one pair of nodes \((u,v)\) with \(|u-v|=f\). (If multiple \((u,v)\) exist, choose one.) It is equivalent to show at most \(2k-3\) edges are drawn for \(k\ge2\) and none for \(k=1\). Let \(F_t\) be the longest edge drawn. I contend that upon deleting the edge \(F_t\) and the edge \(F_{t-1}\) (if it exists), the graph is disconnected. Indeed, if a path exists between the two original endpoints of the \(F_t\) edge, then the sum of the lengths of the edges in this path is at most \[\sum\text{edge length}\le F_2+F_3+\cdots+F_{t-2}<F_t,\]contradiction. Now split \(G\) into \(G_1\sqcup G_2\) with \(k_1\) and \(k_2\) vertices. Since \(k\ge3\) we assume without loss of generality \(k_1\ge2\). Then \(G_1\) has at most \(2k_1-3\) edges by inductive hypothesis, and \(G_2\) has at most \(2k_2-2\) edges (taking the case \(k_2=1\) into consideration), so the number of edges in \(G\) is \[\#\text{edges in }G\le2+(2k_1-3)+(2k_2-2)=2k-3.\]
alexiaslexia
22.07.2021 08:38
\[ \begin{tabular}{p{12cm}} The answer is $\boxed{\left\lceil \dfrac{n}{2} \right\rceil+1}$. Bound and construction will be established later. \end{tabular}\]An inequality problem which appears like an induction-combi on the surface. That said, the ineq (finally) worked after going in circles to chase the right induction. $\color{green} \rule{5.8cm}{2pt}$ $\color{green} \clubsuit$ $ \boxed{\textbf{An Ineq Everyone Knows.}}$ $\color{green} \clubsuit$ $\color{green} \rule{5.8cm}{2pt}$ This whole proof hangs on these two statements: 1. $F_k > F_{k-2}+F_{k-3}+\ldots+F_2$ (more specifically, the LHS and RHS differ by $2$); 2. $F_2+F_3+F_5+\ldots+F_{2k-1} = F_{2k}$. $\color{green} \rule{25cm}{0.3pt}$ The $\boxed{\textbf{Proof}}$ is relatively simple. Note that by $F_{a+1} = F_a+F_{a-1}$ applied to $a = k$ and $a = 2k+1$ respectively implies the induction step on $n = k$ to $n = k+1$. $\color{green} \rule{25cm}{0.3pt}$ We now consider the elements of $S$ to be $s_1 < s_2 < \ldots < s_{k+1}$, and let $d_i = s_{i+1} - s_i$ for $1 \leq i \leq k$ (so there are exactly $k$ $\textsf{consecutive}$ differences). This will imply that for any $2 \leq k \leq n$, $F_k$ is $\textit{representable}$ as $d_i+d_{i+1}+\ldots+d_j$ for some $1 \leq i \leq j \leq n$. $\color{green} \rule{25cm}{0.3pt}$ We will first prove that $n \leq 2k$, and there exists a construction for each $n \leq 2k$. If this is true, then $|S|-1 = k \leq \dfrac{n}{2}$; and for $|S| = k+1 \leq \dfrac{n}{2}+1$, there exists a configuration where $F_2,F_3,\ldots,F_n$ all show up. Then, for each $d_i$, let its $\color{green} \textit{\textbf{ID}}$ to be the smallest $D_i$ so that $F_{D_i}$ $\color{green} \textit{\textbf{passes through}}$ $d_i$. That is, $F_{D_i}$'s representation above contains $d_i$. If no such number exists, let $D_i = 0$.
The $\color{green} \textit{\textbf{smallest}}$ part might (and is) a very counterintuitive step; and plus, why should we bother with $d_i$'s first interaction with $F_{D_i}$? It might seem better to pick a random set, or stronger, $\textbf{all}$ the $F_i$s containing it, right?
In short, it is done to group the certainly-smaller-sized differences in the $\textit{small set}$, and then forcing the not-yet-appearing to surface up. Hopefully the Claim after this illustrates why.
$\color{magenta} \rule{6.2cm}{2pt}$ $\color{magenta} \clubsuit$ $\color{red} \boxed{\textbf{A Bold Claim on Size Only.}}$ $\color{magenta} \clubsuit$ $\color{magenta} \rule{6.2cm}{2pt}$ If $\{R_1,R_2,\ldots,R_l\} = \{D_1,D_2,\ldots,D_k\} - \{0\}$, where $R_1 < R_2 < \ldots < R_l$, then $R_2 \leq R_1 + 1$ and $R_{a+1} \leq R_a+2$ for $2 \leq a \leq l-1$. $\color{red} \rule{25cm}{0.3pt}$ $\color{red} \spadesuit$ $\color{red} \boxed{\textbf{Proof.}}$ $\color{red} \spadesuit$ Let there exists an index $a$ so that $R_{a+1} \geq R_a+3$. Consider the $d_i$s with ID at most $R_a$ as follows:
So, $F_{R_a+1}$ and $F_{R_a+2}$ must only pass through/cover those $d_i$s with ID at most $R_a$. In establishing the above bound, we will discard and throw $F_{R_a+1}$ outside the equation; we'll only establish that $F_{R_a+2}$ is too big a number to fit only within those $d_i$s (hence implying that some other number will have ID $R_{a}+2$, at most). Now consider the sum of $F_2$ up to $F_{R_a}$ in their $\color{red} \textit{\textbf{representations}}$; this implies that a sum of $F_2 + F_3 + \ldots + F_{R_a}$ includes one (if not more) addition of each $d_{i_1},d_{i_2},\ldots,d_{i_m}$ since each of them must be covered at least once. However, if $F_{R_a+2}$ is only exclusive to them, then their total will be $\textbf{at least}$ $F_{R_a+2}$, which is more than $F_2 + F_3 + \ldots + F_{R_a}$, an addition of each of them (if not more). So, we have a contradiction. $\blacksquare$ $\blacksquare$ Note that here we rely on $F_{R_a+2}$'s superiority, established at $\color{green} \clubsuit$ $ \boxed{\textbf{An Ineq Everyone Knows}}$ $\color{green} \clubsuit$. $\color{cyan} \rule{10.5cm}{2pt}$ $\color{cyan} \clubsuit$ $ \boxed{\textbf{Semi-Finishing: Mechanically Repeating the Process.}}$ $\color{cyan} \clubsuit$ $\color{cyan} \rule{10.5cm}{2pt}$ We claim that $\max_{i=1}^k(D_i) \leq 2k-1$, and $n \leq 2k$. $\color{cyan} \rule{25cm}{0.3pt}$ The first one is straightforward: \[ \max_{i=1}^k(D_i) = R_l \leq \dots \leq R_2+(2l-4) \leq R_1+(2l-3) = 2l-1 \leq 2k-1 \]as $l \leq k$. The second one is done by summing similarly to $\color{red} \clubsuit$ $\color{red} \boxed{\textbf{A Bold Claim on Size Only}}$ $\color{red} \clubsuit$: \begin{align*} \sum_{\delta = 1}^k d_{\delta} &\leq F_2+F_3+\ldots+F_{R_l} \\ &\leq F_2+F_3+\ldots+F_{2k-1} \\ &< F_{2k+1} \end{align*}which implies that $F_{2k+1}$ cannot exist given that there are only $k$ $d_i$s. $\color{blue} \rule{4.8cm}{2pt}$ $\color{blue} \diamondsuit$ $\color{blue} \boxed{\textbf{Construction Finish.}}$ $\color{blue} \diamondsuit$ $\color{blue} \rule{4.8cm}{2pt}$ We will prove that we can form $F_2$ up to $F_{2k}$ by only using $k$ $d_i$s. Set $d_1 = F_2$, $d_2 = F_3$, $d_3 = F_5$, and so on, until $d_k = F_{2k-1}$. Here, we can obtain the values of $F_{2i}$, $2 \leq i \leq k$ by letting \[ s_{i+1}-s_1 = F_2+F_3+\ldots+F_{2i-1} = F_{2i} \]by $\color{green} \clubsuit$ $ \boxed{\textbf{An Ineq Everyone Knows}}$ $\color{green} \clubsuit$. We are done. $\blacksquare$ $\blacksquare$ $\blacksquare$
Note: By a combination of above statements, we can see that $\color{blue} \textit{\textbf{all configurations or equalities}}$ when $n = 2k$ are formed by the expressions in the form of
\[ (d_1,d_2,d_3,d_4,d_5,d_6,d_7) = (F_{13},F_5,F_2,F_3,F_7,F_9,F_{11}) \]for example. (Try to find the general categorization of this!)
Where Fibonacci is (almost) equivalent to the binary base where
\[ 2^n \geq 2^{n-1}+\ldots+2^0 \]but with the weaker and non-obvious Zeckendorf base
\[ F_n \geq F_{n-2} + F_{n-3}+\ldots+F_3+F_2 \]$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 1: Perfect System with an Imperfect Interpretation.}$ As with all non-obvious problems, I first tried to note the only given $\textsf{constraint}$ in the problem; that is, the values of $F_k$. When trying to make
\[ x-y \in \{1,2,3,5,8,13,21,34\} \]as much as possible, an immediate $\textit{chain reasoning}$ came to mind: what if $x-y = F_i$ and $y-z = F_{i+1}$? This could save a lot of space for $F_{i+2}$, as it can appear $\textit{between the lines}$. However, it seemed that no more improvements can be made (so early on!) to make more sense of the equation $x-y = F_k$.
Seeing this, as with the case with most addition problems, modulo and difference classes will always be a good thing to consider. As this obviously won't help here, I changed
\[ x-y=F_k \Rightarrow |x-y| = F_k \]in a more $\textbf{equivalent and symmetric}$ way. Unfortunately (with or without the directed) the resulting graph of the config $(n,|S|) = (6,4)$ doesn't seem very good:
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.4]
\definecolor{uuuuuu}{rgb}{0.26666666666666666,0.26666666666666666,0.26666666666666666}
\definecolor{ududff}{rgb}{0.30196078431372547,0.30196078431372547,1}
\draw [line width=0.7pt,blue] (-8.17,0.45)-- (-3.97,2.35);
\draw [line width=0.7pt,blue] (-3.97,2.35)-- (1.51,0.45);
\draw [line width=0.7pt,blue] (1.51,0.45)-- (-8.17,0.45);
\draw [line width=0.7pt,blue] (1.51,0.45)-- (4.45,4.75);
\draw [shift={(-0.42676313951825295,-1.606383530065035)},line width=0.7pt,blue] plot[domain=0.9163633612787566:2.882012938266847,variable=\t]({1*8.011643420687541*cos(\t r)+0*8.011643420687541*sin(\t r)},{0*8.011643420687541*cos(\t r)+1*8.011643420687541*sin(\t r)});
\draw[fill = magenta, xshift = -2.85 cm, yshift=6.03 cm, rotate = 20] (8pt,0pt)--(-10pt,6pt)--(-6pt,0pt)--(-10pt,-6pt)--cycle;
\draw (-2.85,6.03+0.75) node {$8$};
\draw[fill = magenta, xshift = -6.07 cm, yshift= 1.4 cm, rotate = 25] (8pt,0pt)--(-10pt,6pt)--(-6pt,0pt)--(-10pt,-6pt)--cycle;
\draw (-6.07-0.25,1.4+0.55) node {$1$};
\draw[fill = magenta, xshift = -1.23 cm, yshift= 1.4 cm, rotate = 345] (8pt,0pt)--(-10pt,6pt)--(-6pt,0pt)--(-10pt,-6pt)--cycle;
\draw (-1.23+0.25,1.4+0.55) node {$2$};
\draw[fill = magenta, xshift = -3.33 cm, yshift= 0.45 cm, rotate = 0] (8pt,0pt)--(-10pt,6pt)--(-6pt,0pt)--(-10pt,-6pt)--cycle;
\draw (-3.33,0.45-0.75) node {$3$};
\draw[fill = magenta, xshift = 2.98 cm, yshift= 2.6 cm, rotate = 60] (8pt,0pt)--(-10pt,6pt)--(-6pt,0pt)--(-10pt,-6pt)--cycle;
\draw (2.98-0.55,2.6+0.3) node {$5$};
\begin{small}
\node at (-2,-1.5) {Fig 2: Temporary Graph.};
\end{small}
\end{tikzpicture}");[/asy][/asy]
Since cycles seem to play a crucial role here, I tried to eliminate cycles of certain length (or certain orientation) but I couldn't gather any meaningful info.
$\color{cyan} \rule{25cm}{2pt}$
$\color{blue} \text{Sec 1.1: A Relatively Better Model.}$ As all transactions seem to be in $F_i$ (out of any sequence, ever) the Zeckendorf representation of $n$ or $F_k$ seem to be of importance here; but it's a bigger predicament to know $\textbf{what}$ to consider rather than $\textbf{how things are likely to go}$ here.
Probably, since the directions are largely uncontrollable here (hence the imperfect representation, since an arrow of size $8$ and $3$ might as well yield a $11$ or $5$ when $\textit{combined}$), I tried to sort out the minimal differences we could ever bound for:
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.8]
\draw[blue,<-] (0,0)--(1,0); \draw[blue,<-] (1.4,0)--(2.4,0); \draw[blue,<-] (2.8,0)--(3.8,0); \draw[blue,<-] (4.2,0)--(5.2,0);
\draw[blue,<-] (0,-0.8)--(2.4,-0.8); \draw[blue,<-] (0,-1.6)--(3.8,-1.6);
\node at (0.5,-0.4) {$2$}; \node at (1.9,-0.4) {$5$}; \node at (3.3,-0.4) {$1$}; \node at (4.7,-0.4) {?};
\node at (1.2,-1.2) {$7$}; \node at (1.9,-2) {$8$};
\begin{scope}[xshift = 5.8cm,yshift = 0cm]
\draw[blue,<-] (0,0)--(1,0); \draw[blue,<-] (1.4,0)--(2.4,0); \draw[blue,<-] (2.8,0)--(3.8,0); \draw[blue,<-] (4.2,0)--(5.2,0);
\draw[blue,<-] (1.4,-0.8)--(3.8,-0.8); \draw[blue,<-] (0,-1.6)--(3.8,-1.6);
\node at (0.5,-0.4) {$5$}; \node at (1.9,-0.4) {$2$}; \node at (3.3,-0.4) {$1$}; \node at (4.7,-0.4) {$13$};
\node at (2.6,-1.2) {$3$}; \node at (1.9,-2) {$8$};
\end{scope}
\draw[green!33!white,dashed] (5.5,0.3)--(5.5,-2.3);
\node at (5.5,-2.7) {Fig 3: Ordering of $d_i$.};
\end{tikzpicture}");[/asy][/asy]
and I tried to utilize $1$ must occuring as a $\textbf{minimal difference}$ (i.e. there exists a $d_i = F_2$; or $R_1 = 2$, by the notation @Solution) and induct in some way (possibly reduce $F_i$ to $F_{i-1}$?) but to no avail.
(note that in Fig 3, the missing ? could be filled with anything and it won't fill wholly from $F_2 = 1$ to $F_7 = 13$, in contrast, a slightly rearranged pattern will fill $F_2$ to $F_8 = 21$.)
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 2: Individual Steps and Upsize?}$ Next, after throwing all the $s_i$ ($1 \leq i \leq k+1$) into $d_i$ ($1 \leq i \leq k$), I tried to find a more-or-less unique representation of $F_k$ in smaller $F_i$s --- that's the natural thing to do, given that the smalls must appear within some $d_i+d_{i+1}+\ldots+d_j$, what could the next bigger thing be?
This isn't as easy as the Solution make it up to be; looking at it very simply, a $34$ could of course be formed by its two previous terms $21,13$, but $21$ might as well be a sum of another $13$ and $8$. Granted, this will eliminate the variance of $F_k$ a bit, but we can't directly say that a $F_k$ is $\textit{rarely formed}$, especially with the observation that
$\color{magenta} \rule{25cm}{0.3pt}$
There are two times as many Fibonaccis as there are degrees of freedom!
$\color{magenta} \rule{25cm}{0.3pt}$
However, given that $\textbf{some are already in play}$, as the next Figure demonstrates:
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\node at (0,0) {$1$}; \node at (1,0) {$2$}; \node at (2,0) {$3$}; \node at (3,0) {$4$}; \node at (4,0) {$5$};
\draw[blue,<-] (0.1,-0.3)--(0.9,-0.3); \draw[blue,<-] (1.1,-0.3)--(1.9,-0.3); \draw[blue,<-] (2.1,-0.3)--(2.9,-0.3); \draw[blue,<-] (3.1,-0.3)--(3.9,-0.3);
\draw[blue,<-] (0.1,-0.9)--(1.9,-0.9); \draw[blue,<-] (1.1,-1.1)--(2.9,-1.1); \draw[blue,<-] (2.1,-1.3)--(3.9,-1.3);
\begin{footnotesize}
\node[purple] at (0.9,-0.9) {$21$};
\end{footnotesize}
\draw[blue,<-] (0.1,-1.7)--(2.9,-1.7); \draw[blue,<-] (1.1,-1.9)--(3.9,-1.9);
\begin{footnotesize}
\node[purple] at (2.5,-1.9) {$34$}; \node[orange] at (2.5,-2.2) {21 or 13}; \node[orange] at (0.5,-1.9) {13 or 21};
\end{footnotesize}
\draw[blue,<-] (0.1,-2.5)--(3.9,-2.5);
\begin{footnotesize}
\node[orange] at (2,-2.7) {$34$};
\end{footnotesize}
\draw[green!33!white, dashed] (-0.2,-3)--(4.2,-3);
\node at (2, -3.4) {Fig 4.};
\end{tikzpicture}");[/asy][/asy]
Now say we'd like to prove a contradiction with $k = 4,n = 9$. So,
\[ \{(1 = F_2,F_3); (F_4,F_5); (F_6,F_7); (F_8,F_9 = 34)\} \]First, (in the orange part) if a $34$ is present as the biggest arrow, it would be a $\textit{good}$ (read: rational) choice to place both $21$ and $13$ in the bigger arrows, as any placement in the second row will make the upmost and third upmost row suffer (note here that a $21$ in the upmost row is optimal!)
Seeing the flipside of this method, (in the purple part) assume that we have a $21$ and $34$ in the second and third row (where we considered $13$'s placement w.r.t. $34$ before.) Interestingly, this implies that we can't place a $55$ anywhere (not that we are required to); but there is a $\textbf{very}$ limited space into $\textbf{what to put}$ in $d_2$.
For instance, if we put a number as small as $13$ there (!and there are much smaller numbers to put) we'd have $d_3+d_4 = 21$, and this further makes small numbers appear less there (while we only need small numbers; from $F_2 = 1$ to $F_6 = 8$, to complete the eight Fibonaccis.)
$\color{cyan} \rule{25cm}{2pt}$
$\color{blue} \text{Sec 2.1: Provoking the already-dominating Big Numbers to be Bigger.}$ This further strengthen the $\color{magenta} \textbf{\textit{strict dominance of the large numbers}}$ akin to the bases of $2^k$. Furthermore, it's very unnatural to have $2n$ constraints when we can freely twist $n$ of them. After-contest reflection shows that this is exactly the case with $2^k$ bases; we can make at most $n$ varieties of them with $n$ degrees of freedom!
While that is an interesting thought to consider, this only prompted me to try more pair-related stuff, but this also yielded an interesting result: note that the $d_i$s in the optimal config are $F_2,F_3,F_5,F_7$ and so on. This creates perfect sense with the degree-of-freedom-thing, as the indices skip in pairs from $3$ to $5$ and so on.
Later, this two-step increase idea forms the basis of selecting small numbers and forcing them to duel against the mighty $F_{R_a+2}$.
For now, I was more enthusiastic on loosing the bound of $F_i$s. Since the pairs $(F_{2k-1},F_{2k})$ attracted my attention, I wondered if $F_{2k} = F_{2k-1}+F_{2k-2}$ can be modified in a way that won't violate the size argument, but also being easy to generalize. I came up with considering $B_{i+1} \geq B_i+B_{i-1}$, and I tried to show that whatever
\[ B_1,B_2,\ldots,B_{2k}; \ B_{i+1} \geq B_i+B_{i-1} \]are, they cannot fit within the bounds of $d_i+d_{i+1}+\ldots+d_j$. (This will turn up as an alternative Solution after the test)
By this point, the argument has turned purely into a size argument (and all traces of combi have been lost.)
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 3: Micro-zooming for a good Size-rounding.}$ After freeing myself from the weird nudge to start at $F_2 = 1$, I nullified the Fibonacci-specific differences and instead focus on $\textit{the indices of B}$. This offered no new perspective on the indices at face-value observation: when $k = 4$,
\[ (d_1,d_2,d_3,d_4,d_1+d_2,d_1+d_2+d_3,d_1+\ldots+d_4) = (B_{1,2,4,6,3,5,7}) \]and $2k-1$ terms come up, at best. Now, seeing that whether or not $B_7$ is exactly $B_6+B_5$ doesn't matter, I switched $B_6$ to $B_5$ and this happens:
[asy][asy]usepackage("tikz");label("\begin{tikzpicture}
\draw[blue] (0.1,0.1)--(0.1,0.9)--(0.9,0.9)--(0.9,0.1)--cycle;
\begin{scope}[xshift = 1 cm, yshift = 0 cm] \draw[blue] (0.1,0.1)--(0.1,0.9)--(0.9,0.9)--(0.9,0.1)--cycle; \end{scope}
\begin{scope}[xshift = 2 cm, yshift = 0 cm] \draw[blue] (0.1,0.1)--(0.1,0.9)--(0.9,0.9)--(0.9,0.1)--cycle; \end{scope}
\begin{scope}[xshift = 3 cm, yshift = 0 cm] \draw[blue] (0.1,0.1)--(0.1,0.9)--(0.9,0.9)--(0.9,0.1)--cycle; \end{scope}
\begin{small}
\node at (0.5,0.5) {$B_1$}; \node at (1.5,0.5) {$B_2$}; \node at (2.5,0.5) {$B_4$}; \node at (3.5,0.5) {$B_5$}; \node at (1,-0.25) {$B_3$}; \node at (3,-0.25) {$B_6$};
\end{small}
\draw[green!33!white,dashed] (-0.2,-0.6)--(4.2,-0.6);
\node at (2,-1) {Fig 5.};
\begin{footnotesize}
\node at (2,-1.4) {$\textbf{note}$: $B_7$ doesn't fit anywhere as $B_3+B_6 < B_7$.};
\end{footnotesize}
\end{tikzpicture}");[/asy][/asy]
Moreover, doing this in a similar way with $k = 3$, setting $d_1 = 1, d_2 = 2$ and $d_3 = 6$ makes a $3$ and an $8$ appear easily, but this config is just underwhelming compared to the full $(1,2,3,5,8)$ (and we can't put a $13$ in the modified config, either.)
A final attempt in recording numbers $\textsf{arbitrarily}$ to the config is to assign
\[ d_1 = B_1, d_2 \leq_{\text{?}} B_2, d_1+d_2 = B_3, d_2+d_3 = B_4, \{d_4 \ \text{or} \ d_3+d_4\} = B_5\]Here, I tried to $\textsf{reconcile}$ the random $k = 3$ earlier with a placement of $B_5$ somewhere in the $\textit{still secluded area}$ of $d_4$. This will somewhat guarantee $B_6$, but after trying so hard as to switch and rearrange some $B_i$s, it's very difficult to include $B_7$ in there.
I tried to find out a reason why, but I just stumbled across $\textit{easily inducted}$ ineqs such as
\[ B_7 \geq B_5+B_4+B_3 \ \text{or} \ B_7 \geq B_6 + B_4 + B_3 \]which was kinda close to the ineq in $\color{green} \clubsuit$ $ \boxed{\textbf{An Ineq Everyone Knows}}$ $\color{green} \clubsuit$.
Now, what's this got to do with the name of the Section? The crucial thing I observed here is that the $\textit{corner cells}$ or previously secluded cells play an important role in advancing a $B_5$-sized (total) summation to a sum which size is compatible with $B_7$.
Another problem comes up with this observation: how can we be sure that there $\textbf{is}$ something to advance? Luckily, this is a question guaranteed by completeness; $B_1$ to $B_5$ must exist somewhere in the grid (of $d_i$s) --- but where they lie is the problem.
$\color{cyan} \rule{25cm}{2pt}$
$\color{blue} \text{Sec 3.01: Spreading Out.}$ Then, a final resort would be to put them in $\textit{totally spread-out positions}$; and see how the big numbers crush them. If
\[ (d_1,d_2,d_3,d_4) = (B_1,B_2,B_3,B_5) \]we can either put $B_4 = d_1+d_2+d_3$ or $d_2+d_3$. This also puts us in an edge as $B_6$ can encompass the whole lot of them, sufficing on $k = 4$.
While we could do better (obviously) by changing $d_3 = B_3, d_4 = B_5$ to $B_4$ and $B_6$ respectively, that's besides the point here; what created my intuition here was that the size of the largest $B$ (i.e. $B_6$) jumps only one from the highest $B_i$ the $d_i$s have.
Daring myself to decrease the variance of $d_i$s even more, I tried the $\textsf{ultimate}$ combination
\[ (d_1,d_2,d_3,d_4) = (B_1,B_2,B_3,B_4) \]and saw that we can't jump even to $B_6$ here. To prove this, let $B_6 \leq d_1+d_2+d_3+d_4$. Then, a $B_5$ will (kinda) have to rely on $B_1,B_2,B_3$ alone, and this just seems like straight-up Fibonacci induction on $F_n > F_{n-2}+\ldots+F_2$, is it not?
From here, I gathered that whenever considering from $B_1$ up to $B_l$ in some particular collection of $d_1$ to $d_m$ (later-to-be $d_{i_1}$ to $d_{i_m}$), the jump from the largest $B_i$-covering of those must not be $3$ or larger to the next larger one.
Formulated more efficiently, this just means that the $\color{green} \textbf{\textit{ID}}$ from a collection to a newer and larger connection differs by at most $2$, if they are indeed consecutive. A little bit of micro-zooming now yields the hard Claim of $\color{magenta} \clubsuit$ $\color{red} \boxed{\textbf{Size Only}}$ $\color{magenta} \clubsuit$.
(So, to put it shortly, I came around the construction first, then the ineq, then the semi-finishing of $\textit{bounding the largest possible}$ $B_i$s in relative to the largest $d_i$s; then the red Proof, before being certain about the IDs not skipping by $3$ or greater in the $\color{magenta} \clubsuit$ $\color{red} \boxed{\textbf{Size Only}}$ $\color{magenta} \clubsuit$ Claim.)
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 3.1: The Inclusion of All Differences.}$ To motivate some parts of why the Solution and summation is as it is, I did more explorations in a bigger scale of $k = 5$. Particularly, when all the $d_{i_a}$s ($1 \leq a \leq m$) have different $\textit{ID}$s, this seems very trivial; as in setting
\[ d_1 \sim B_1, \ldots, d_4 \sim B_4, d_5 \sim B_6 \]where we could easily deduce that $B_8$ cannot cover only those numbers. While this is pretty strong in and of itself, note how the process becomes a bit easier when their IDs are $(1,2,4,4,6)$ instead of the $(1,2,3,4,6)$ we have above.
This means that we don't have to consider the $3$-block at all, and just include $d_3$ in the $B_4$-representation we have already summed.
$\color{green} \rule{25cm}{2pt}$
$\color{red} \text{Sec 3.2: Sketch of Alternative Path.}$ In the test, a friend of mine (@Sugiyem) came up with a Claim about $F_a -F_b \ne F_c-F_d$ and attempted to pull out a contradiction by using the directed graph method I (almost) discarded immediately in $\color{red} \text{Sec 1}$ due to its ineffective representation.
However, this seems to be an intriguing idea to work on, as the statement is purely-graph like; with $\textit{elements of a set}$ having pairwise variative difference (and a sum-constructed Fibonacci sequence, at that.) The problem with this is that it only eliminates $4$-cycles in a freely-constructed graph; and I thought it'd be a nice alternative to see $\textsf{all cycles}$ and link them with the ineq (if it's possible).
Here's a sketch of that attempt:
Just a Sketch.Let graph $G$ be a graph with vertices representing elements of $S$ and (undirected) edges labeled $e_a$ for some $a$ represent the difference of two elements of $S$ (a.k.a. the vertices that carry that edge) equalling to $B_a$.
We will prove a stronger statement that I conjured at the end of $\color{blue} \text{Sec 2.1}$, that $B_1, \ldots, B_{2k}$ cannot fit within $k+1$ numbers where $k \geq 1$. This is, of course, with the convention that every number $B_i$ must exceed the sum of the largest two numbers smaller than it.
Since this statement is $\textbf{very tricky}$, I'd rephrase it to be
\[\begin{tabular}{p{12cm}}
If a graph $G$ has one element, it must have zero numbers of that form. If a graph $G$ has $k \geq 2$ elements, then it can have at most $2k-3$ of them.
\end{tabular} \\ \]We prove that statement by strong induction on $|V_G|$. Let $e_n$ directly connects $v_i$ and $v_j$.
$\color{green} \rule{25cm}{2pt}$
$\color{magenta} \text{Case 1.}$ Consider the edge $e_n$. If there is no cycle containing it, then removing it will form two connected components $C$ and $D$, each of which edges $C_1,C_2,\ldots,C_c$ and $D_1,D_2,\ldots,D_d$ satisfying $C_{i+1} \geq C_i + C_{i-1}$ (and its equivalent statement for $D$s).
By induction, the amount of edges which exist is less than $(2c-3)+(2d-3)+1 = 2(c+d)-5$ if $|C|,|D| \ne 1$; or $0 + (2d-3) +1 = 2(d+1) - 4$ if $|C| = 1$.
$\color{green} \rule{25cm}{2pt}$
$\color{magenta} \text{Case 2.}$ If $e_n$ is part of a cycle, then any cycle containing it must also contain $e_{n-1}$, for inequality reasons. Now we remove both $e_n$ and $e_{n-1}$. Note that the resulting graph cannot be connected, as if $v_i,v_j$ is connected, then a cycle with $e_n$ but not with $e_{n-1}$ can be formed.
The computation here can be replicated exactly as in the first case, with one more edge in them (yielding an upper bound of $2(c+d)-4$ or $2(d+1)-3$. $\blacksquare$ $\blacksquare$ $\blacksquare$
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]
SnowPanda
25.07.2021 09:59
The answer is $\lfloor{\tfrac{n}{2}}\rfloor + 1$. It suffices to construct this when $n$ is even (then the same construction works for $n - 1$). Let $n = 2k$, and take \[S = \{0, F_2, F_4, F_6, \ldots, F_{2k}\},\]which has $k + 1$ elements. Then $F_{2i} = F_{2i} - F_0$ and $F_{2i - 1} = F_{2i} - F_{2i - 2}$, so all such $F_i$ are in the set.
Now to prove this is a lower bound, we'll show that a set of $k \geq 2$ integers has at most $2k - 3$ distinct Fibonacci numbers $F_i$ (for $i \geq 2$) as differences $x - y$. Draw a graph with the $k$ numbers as vertices. For each $F_i$ which appears as a difference $x - y$, pick exactly one occurrence of it and draw the edge between $x$ and $y$, labeled with $F_i$. So we want to show this graph has at most $2k - 3$ edges.
Now induct; clearly this is true for $k = 2$.
Let $u$ and $v$ be the vertices whose edge corresponds to the largest Fibonacci number $F_n$, with $u > v$.
Claim: If $P_1$ and $P_2$ are two paths from $u$ to $v$, other than the edge $uv$ itself, then there must be an edge which $P_1$ and $P_2$ both contain, in the same direction.
Proof. Assume not. Then add all the differences $x - y$ where one of the paths contains $y \to x$. This equals $2(u - v) = 2F_n$. On the other hand, the sum of $x - y$ is at most the sum of all the other Fibonacci numbers -- any edge $F_i$ in exactly one path contributes $\pm F_i$ to the sum, while any edge in both must be traversed in opposite directions and contributes $0$. So the sum is at most \[F_2 + F_3 + \cdots + F_{n - 1} = F_{n + 1} - 2\](we can show this by induction), which is less than $F_n + F_{n - 1} \leq 2F_n$, contradiction. $\blacksquare$
First suppose there is no path $P$ from $u$ to $v$, other than $uv$. Then if we delete the edge $uv$, then $u$ and $v$ are no longer connected. If the connected component $u$ is in has $a$ vertices, then it has at most $2a - 2$ edges (we have $-2$ instead of $-3$ for the $a = 1$ case), and the remainder of the graph has at most $2(k - a) - 2$ edges, by the inductive hypothesis. So the graph has at most \[2a - 2 + 2(k - a) - 2 + 1 = 2k - 3\]edges.
Now assume there is a path $P$ from $u$ to $v$ other than $uv$. In particular $k \geq 3$. Call this path $w_0 \to w_1 \to \cdots \to w_m$, where $w_0 = u$ and $w_m = v$, and delete the edge $uv$.
Claim: There is some $0 \leq i < m$ for which if we delete the edge $w_iw_{i + 1}$, then the graph becomes disconnected.
Proof. Assume not. Call the edges $w_iw_{i + 1}$ blue. If we can delete $w_iw_{i + 1}$ without disconnecting the graph, there is a path from some $w_j$ with $j \leq i$ to some $w_\ell$ with $\ell \geq i + 1$, which does not use any blue edges. So such a path must exist for each $0 \leq i < m$; call this path $i$-good.
However, we'll use this to get a second path that contradicts the first claim. First, taking an $0$-good path gives us a path $w_0 \to w_{a_1}$ for some $a_1 \geq 1$. Now taking an $a_1$-good path gives a path $w_{b_1} \to w_{a_2}$ for some $b_1 \leq a_1$ and $a_2 \geq a_1 + 1$. Then taking an $a_2$-good path gives a path $w_{b_2} \to w_{a_3}$ for some $b_1 \leq a_2$ and $a_3 \geq a_2 + 1$. Keep doing this until we get a path $w_{b_{t - 1}} \to w_{a_t}$ where $a_t = m$.
Then consider the sequence of moves \[w_0 \to w_{a_1} \to w_{b_1} \to w_{a_2} \to w_{b_2} \to w_{a_3} \to \cdots \to w_{b_{t - 1}} \to w_{a_t}\]where we go from $w_{b_{i - 1}} \to w_{a_i}$ using the paths from above, and $w_{a_i} \to w_{b_i}$ by walking backwards on blue edges. So this sequence never goes forwards on a blue edge.
Finally, if this sequence repeats any vertex, we can delete the cycle between its first and last occurrence. So we can turn this into a path from $w_0$ to $w_m$ which never uses a blue edge in the correct direction (meaning $w_i \to w_{i + 1}$), contradicting the first claim. $\blacksquare$
Now delete both $uv$ and $w_iw_{i + 1}$, and suppose the connected component of $u$ has $a$ vertices and the rest of the graph has $b$ vertices, with $a + b = k$. Then one of $a$ and $b$ must be at least $2$ (since $k \geq 3$), so by the inductive hypothesis there are at most \[2a + 2b - 2 - 3 + 2 = 2k - 3\]edges in the original graph.
508669
24.08.2021 15:49
MathLuis wrote: The Fibonacci numbers $F_0, F_1, F_2, . . .$ are defined inductively by $F_0=0, F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for $n \ge 1$. Given an integer $n \ge 2$, determine the smallest size of a set $S$ of integers such that for every $k=2, 3, . . . , n$ there exist some $x, y \in S$ such that $x-y=F_k$. $Proposed \; by \; Croatia$ Killed when you realize the answer. We claim that the answer is $|S| \geq \lceil \frac{n}{2} \rceil + 1$. For a given natural number $n \geq 2$, consider $S = \{ 0, F_0, F_2, \dots F_{2 \lceil \frac{n}{2} \rceil }$. We see that $F_{2i} = F_{2i} - 0$ and $F_{2i+1} = F_{2i+2} - F_{2i}$ according to the recursion. To prove that $|S| = k \geq \lceil \frac{n}{2} \rceil + 1$, we draw a graph $G$ whose vertices are the distinct elements in $S$, such that the vertices $v_1, v_2 \dots v_k$ of $G$ represent elements $s_1, s_2 \dots s_k$ of $G$. Draw an edge between two vertices $v_i, v_j$ if the pair $(i, j)$ minimizes $i + j$ while $|s_i - s_j| = F_t$ for some odd number $t \in 2, 3, \dots $. We observe that the graph cannot have a cycle since $F_{2t+1} \geq \sum\limits_{i=0}^{t-1} F_{2i+1} = F_{2t}$ and this means that $G$ is a forest .This means that $V(G) = E(G) + c(G)$, but we see that $E(G) = \left \lceil \frac{n}{2} \right \rceil$ and this means that $|S| \geq V(G) = E(G) + c(G) \geq \left \lceil \frac{n}{2} \right \rceil + 1$ as desired.
Number1048576
22.04.2022 14:22
Try to prove that given a set of $n$ integers, you can get at most up to $F_{2n-2}$, by bounding the value of the largest number (WLOG the smallest number is $0$).
Consider how many consecutive differences ($a_i - a_{i-1}$, where $a_1$ is the smallest number in the set and $a_i > a_{i-1}$) have to be smaller than a certain fibonacci number.
We claim that the solution is $\lceil \frac{n}{2} \rceil + 1$. This is achievable by the construction $\{0,F_2,F_4,...,F_{2\lceil \frac{n}{2} \rceil}\}$.
We will instead prove that given a set of $n$ integers, the most fibonacci numbers (consecutive, starting from $F_2$) which can be the differences of a pair of the integers is $2n-3$, which amounts to the same thing.
Let $a_i$ be the $i$th smallest number in the set, and let $b_i = a_{i+1} - a_i$. Then we claim that there exist at least $k$ $b_i$s smaller than $F_{2k-1}$.
We will prove this by induction.
$Base: k=1$
Note that since there exist two numbers $a_x$ and $a_y$ such that $a_x - a_y = 1$, if $x = y+1$ then we are done, but if $x > y+1$,
then $a_{y+1} - a_y \leq 1$, as required.
$Step:$
Note that $a_x - a_y = b_{y} + b_{y+1} +...+ b_{x-1}$, so if we let $a_x - a_y = F_{2k-1}$, then if one of those $b_i$ is larger than $F_{2k-3}$, then we have at least $k$ $b_i$s smaller than $F_{2k-1}$, as required. However, if none of them are larger than $F_{2k-3}$, then by the inductive hypothesis the maximum value of $a_x - a_y$ is
$F_1 + F_3 +...+ F_{2k-3} = F_{2k-2} < F_{2k-1}$, as by the inductive hypothesis there is at least one less than $F_1$, two less than $F_3$, three less than $F_5$ etc.
This establishes the claim.
Now, this implies that every $b_i$ is smaller than $F_{2n-3}$. However, note that $a_n - a_1 = b_1 +...+ b_{n-1} \leq F_1 + F_3 +...+ F_{2n-3} = F_{2n-2}$.
Therefore, since the maximum difference is $a_n - a_1 \leq F_{2n-2}$, there is no difference larger, so we can only get fibonacci numbers up to $F_{2n-2}$, as required.
mathleticguyyy
02.05.2022 22:50
The answer is $\left\lceil\frac{n}{2}\right\rceil+1$. To see that it's sufficient, consider the set $\{F_0,F_2\ldots\}$. To see that it's necessary, consider the graph formed by elements of $S$ where any two elements differing by a fibonacci number are connected by an edge. Now, color an edge red if it connects two number differing by $F_{2m}$ and blue if it connects two numbers differing by $F_{2m-1}$ for positive integer $m$. Note that there can be no red cycle and no blue cycle by considering the longest edge in each cycle. Hence, there are at most $|S|-1$ blue edges and $|S|-1$ red edges, but notice however that the necessary edge with length $F_2=F_1$ is colored twice, so there can be at most $2|S|-3$ edges in total in a satisfactory $S$, which finishes.
awesomeming327.
17.02.2023 08:03
The answer is $\lfloor \tfrac{n}2 \rfloor + 1$ for which we provide the following construction: \[S_n=\{0\} \cup \{F_i \mid i\equiv n\pmod 2, i>0\}\]which trivially works. Now, to prove the bound, we need to show that we cannot make $F_2$, $F_3$, $\dots$, $F_{2k-1}$ all with differences of a $k$-sized set. For this, note that \begin{align*} F_{2m} &> F_{2m-1}+F_{2m-3}+\dots + F_{3} \\ F_{2m-1} &> F_{2m-2} + F_{2m-4}+\dots + F_2 \end{align*}We proceed by contradiction: construct a $k$-vertex graph with each vertex as a member of the set. For each $F_2$, $F_3$, $\dots$, $F_{2k-1}$, draw exactly one red edge between two vertices whose corresponding elements in the set differ by that fibonacci number with even index, and one blue edge for a fibonacci number with odd index. Note that $2k-2$ edges are drawn, $k-1$ of color red and $k-1$ of color blue. By the two inequalities given above, there are no cycles. Thus, the red and blue vertices each for a tree. Now to finish, consider the edge corresponding with $F_{2k-1}.$ We know from the same inequalities that had us conclude the lack of cycles, that were this edge colored red, then there still may not be a cycle. This is simply not possible. We are done.
Leo.Euler
06.09.2023 02:53
The answer is $\lceil\tfrac n2\rceil+1$, achievable by taking $S=\{F_0,F_2,F_4,\ldots,F_{2k-2}\}$. Construct a graph $G$ on $S$, and for each $j \in \{F_3, F_5, \ldots, F_{2k-1}\}$, draw an edge between a single pair $(v, w)$ of vertices such that $|v-w|=j$. Furthermore, label each edge $v \sim w$ with $|v-w|$. Claim: $G$ has no cycles. Proof. Assume for contradiction that $G$ has a cycle $\mathcal{C}$. Let the largest label in $\mathcal{C}$ be $F_{2m+1}$. By the Triangle inequality, the sum of all other labels in the cycle is at least $F_{2m+1}$, however this sum is at most \[ \sum_{i=1}^m F_{2i-1} = F_{2m},\]which is a contradiction. Thus $G$ must be a tree, so it has at least $\lceil\tfrac n2\rceil+1$ vertices, and we are done.
Pyramix
12.04.2024 15:28
My solution is similar to the ones posted on this thread. We claim that the smallest possible size of $S$ is $\left\lceil\frac n2\right\rceil+1$. The set $S=\left\{F_0, F_2, \ldots, F_{2\left\lceil\frac n2\right\rceil}\right\}$ works as a construction. The main idea is that $F_1+F_3+\cdots+F_{2t-1}=F_{2t}$. This can be shown induction, note that $t=1$ works, and \[F_{2t+2}=F_{2t+1}+F_{2t}=F_{2t+1}+F_{2t-1}+\cdots+F_3+F_1,\]so the summation is correct. Suppose there exists a set $S$ of $m$ elements with $1\leq m\leq \left\lfloor\frac n2\right\rfloor$ that satisfies the given condition. Consider a graph $G$ whose vertices represents the elements in $S$. Then, for every $1\leq k\leq \frac{n+1}2$, vertices $x,y$ of $G$ are adjacent if $x-y=F_{2k-1}$ and to ensure uniqueness, take the smallest such pair. There are exactly $\left\lfloor\frac{n+1}{2}\right\rfloor$ edges in $G$. Claim: $G$ has no cycles. Proof. Suppose there is some cycle of elements $x_1, x_2, \ldots, x_c, x_1$ numbered such that $F_{2d-1}=|x_c-x_1|>|x_i-x_{i-1}|$ for every $2\leq i\leq c$. Then, $d\geq c$ is forced. Then, by Triangle Inequality of Modulus, we have \[F_{2d-1}=|x_c-x_1|\leq |x_2-x_1|+|x_3-x_2|+\cdots+|x_c-x_{c-1}|\leq F_1+F_3+\cdots+F_{2c-1}=F_{2c}\]which is impossible as $d\geq c$. Hence, $G$ has no cycles. $\blacksquare$ From our claim, we have that $G$ is a (possibly disconnected) tree. Then, $1+\left\lceil\frac {n}2\right\rceil=\left\lfloor\frac {n+1}2\right\rfloor=\#(\text{edges}) \leq \#(\text{vertices})-1=m-1$, which means $m\geq2+\left\lceil\frac n2\right\rceil$, giving us the required contradiction. $\blacksquare$