Another SL problem about fibonacci numbers :3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

30 users

TOPICS

No tags match your search

M

No tags match your search

M

Another SL problem about fibonacci numbers :3

G H J

Reveal topic tags

IMO Shortlist 2020

additive representation

L

G H BBookmark kLocked kLocked NReply

Source: ISL 2020 C4

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1451 posts

#1 h Jul 20, 2021, 9:09 PM • 3 Y

Y by centslordm, microsoft_office_word, starchan

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

This post has been edited 5 times. Last edited by MathLuis, Apr 19, 2022, 8:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

381 posts

Davsch

#2 h Jul 20, 2021, 11:13 PM • 2 Y

Y by centslordm, akasht

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

691 posts

#3 h Jul 20, 2021, 11:18 PM • 11 Y

Y by centslordm, 554183, microsoft_office_word, MatBoy-123, hakN, akasht, rcorreaa, rayfish, erkosfobiladol, Jalil_Huseynov, sabkx

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.

This post has been edited 1 time. Last edited by IndoMathXdZ, Jul 20, 2021, 11:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

119 posts

sn6dh

#4 h Jul 20, 2021, 11:34 PM • 2 Y

Y by centslordm, ElaineHuang

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\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1739 posts

#5 h Jul 20, 2021, 11:44 PM • 4 Y

Y by centslordm, khina, love.math, sabkx

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

This post has been edited 1 time. Last edited by TheUltimate123, Jul 20, 2021, 11:44 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

110 posts

#6 h Jul 22, 2021, 5:38 AM • 3 Y

Y by Prabh2005, JG666, CyclicISLscelesTrapezoid

$\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$ .
Motivation?

$\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:
$[asy]usepackage("tikz");label("\begin{tikzpicture}[scale=0.7] \draw[red,thick] (-1.5,-0.5)--(8.7,-0.5); \draw[red!20!white,dashed] (-1.7,0.5)--(9,0.5); \draw[green!33!white,dashed] (-1.7,-1.5)--(9,-1.5); \node at (0,0) {$d_{i_1}$}; \node at (0,-1) {$D_{i_1}$}; \node at (2,0) {$d_{i_2}$}; \node at (2,-1) {$D_{i_2}$}; \node at (4,0) {$d_{i_3}$}; \node at (4,-1) {$D_{i_3}$}; \node at (-1,0) {?}; \node at (1,0) {?}; \node at (3,0) {?}; \node at (5.5,0) {$\dots$}; \node at (7,0) {$d_{i_m}$}; \node at (7,-1) {$D_{i_m}$}; \node at (8,0) {?}; \node at (4,-2) {Fig 1.}; \begin{footnotesize} \node at (4,-2.6) {$\textbf{note}$: ? = not yet and will be covered (later).}; \end{footnotesize} \end{tikzpicture}");[/asy]$
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$
Notes.

Motivation: Not-Combi Size Issues + Where Does Completeness Help?

This post has been edited 3 times. Last edited by alexiaslexia, Jul 22, 2021, 4:32 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

186 posts

#7 h Jul 25, 2021, 6:59 AM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1040 posts

508669

#8 h Aug 24, 2021, 12:49 PM • 3 Y

Y by Mango247, Mango247, Mango247

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.

This post has been edited 2 times. Last edited by 508669, Aug 24, 2021, 12:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

91 posts

#9 h Apr 22, 2022, 11:22 AM

Y by

hint
bigger hint
possible fakesolve

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3217 posts

#10 h May 2, 2022, 7:50 PM

Y by

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.

This post has been edited 1 time. Last edited by mathleticguyyy, May 2, 2022, 7:50 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1665 posts

awesomeming327.

#11 h Feb 17, 2023, 5:03 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

577 posts

#12 h Sep 5, 2023, 11:53 PM

Y by

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.
:yoda:

:yoda:

Thus $G$ must be a tree, so it has at least $\lceil\tfrac n2\rceil+1$ vertices, and we are done.
:starwars:

:starwars:

This post has been edited 2 times. Last edited by Leo.Euler, Sep 6, 2023, 11:53 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

419 posts

#13 h Apr 12, 2024, 12:28 PM

Y by

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$

This post has been edited 2 times. Last edited by Pyramix, Apr 12, 2024, 12:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

34 posts

#16 h Tuesday at 8:16 PM

Y by

We claim that the answer is $\left\lceil \frac{n}{2} \right\rceil + 1$ . This is achieved by the numbers $0, 1, 3, \dots, F_{2\lceil\frac{n}{2}\rceil}$ . We will now show that this bound holds.

Consider a minimal graph $G$ such that each vertex in $G$ represents a number in $S$ , and for any $2 \leq k \leq n$ , there is precisely one edge in $G$ such that the difference between its vertices is $F_k$ . We will refer to this edge as representing the number $F_k$ .

It is clear that $G$ has $n - 1$ edges. We will show that $G$ has at least $\left \lceil \frac{n}{2} \right \rceil + 1$ vertices. The key here is to show that we can split $G$ 's edge set into two forests. Let $H$ be the subgraph of $G$ with the same vertex set and edge set containing edges representing $F_{2d}$ for integral $d$ .

We claim $H$ is a forest. This claim follows easily because if it were not true, then a cycle exists, and so $1 + 3 + \dots + F_{2k} \geq F_{2k + 2}$ would hold for some $k$ . This is clearly false.

It follows that the number of vertices in $H$ is greater than the number of edges in $H$ . Because $H$ clearly has $\left \lceil \frac{n}{2} \right \rceil$ edges, it must have at least $\left \lceil \frac{n}{2} \right \rceil + 1$ vertices, and we are done.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a