Olympiad problems

2015 Thailand TSTST, 1

Prove that the Fibonacci sequence $\{F_n\}^\infty_{n=1}$ defined by $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1}+F_n$ for all $n \geq 1$ is a divisibility sequence, that is, if $m\mid n$ then $F_m \mid F_n$ for all positive integers $m$ and $n$.

1996 Akdeniz University MO, 2

Tags: Fibonacci , Sequence , number theory

Let $u_1=1,u_2=1$ and for all $k \geq 1$'s $$u_{k+2}=u_{k+1}+u_{k}$$ Prove that for all $m \geq 1$'s $5$ divides $u_{5m}$

2020 IMO Shortlist, C4

Tags: Fibonacci , combinatorics , IMO Shortlist , IMO Shortlist 2020 , additive representation

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$. [i]Proposed by Croatia[/i]

2021 Taiwan TST Round 2, C

Tags: Fibonacci , combinatorics , IMO Shortlist , IMO Shortlist 2020 , additive representation

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$. [i]Proposed by Croatia[/i]

1992 IMO Longlists, 78

Tags: Fibonacci , Fibonacci sequence , limit , Sequence , IMO Shortlist , IMO Longlist , calculus

Let $F_n$ be the nth Fibonacci number, defined by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n > 2$. Let $A_0, A_1, A_2,\cdots$ be a sequence of points on a circle of radius $1$ such that the minor arc from $A_{k-1}$ to $A_k$ runs clockwise and such that \[\mu(A_{k-1}A_k)=\frac{4F_{2k+1}}{F_{2k+1}^2+1}\] for $k \geq 1$, where $\mu(XY )$ denotes the radian measure of the arc $XY$ in the clockwise direction. What is the limit of the radian measure of arc $A_0A_n$ as $n$ approaches infinity?

1992 IMO Longlists, 79

Tags: floor function , algebra , Sequence , Fibonacci , Fibonacci sequence , Inequality , IMO Shortlist

Let $ \lfloor x \rfloor$ denote the greatest integer less than or equal to $ x.$ Pick any $ x_1$ in $ [0, 1)$ and define the sequence $ x_1, x_2, x_3, \ldots$ by $ x_{n\plus{}1} \equal{} 0$ if $ x_n \equal{} 0$ and $ x_{n\plus{}1} \equal{} \frac{1}{x_n} \minus{} \left \lfloor \frac{1}{x_n} \right \rfloor$ otherwise. Prove that \[ x_1 \plus{} x_2 \plus{} \ldots \plus{} x_n < \frac{F_1}{F_2} \plus{} \frac{F_2}{F_3} \plus{} \ldots \plus{} \frac{F_n}{F_{n\plus{}1}},\] where $ F_1 \equal{} F_2 \equal{} 1$ and $ F_{n\plus{}2} \equal{} F_{n\plus{}1} \plus{} F_n$ for $ n \geq 1.$

ICMC 6, 3

Tags: ICMC , combinatorics , Fibonacci , college contests

Bugs Bunny plays a game in the Euclidean plane. At the $n$-th minute $(n \geq 1)$, Bugs Bunny hops a distance of $F_n$ in the North, South, East, or West direction, where $F_n$ is the $n$-th Fibonacci number (defined by $F_1 = F_2 =1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$). If the first two hops were perpendicular, prove that Bugs Bunny can never return to where he started. [i]Proposed by Dylan Toh[/i]

2020 European Mathematical Cup, 2

Tags: number theory , Fibonacci , divisor , Sequence , emc

A positive integer $k\geqslant 3$ is called[i] fibby[/i] if there exists a positive integer $n$ and positive integers $d_1 < d_2 < \ldots < d_k$ with the following properties: \\ $\bullet$ $d_{j+2}=d_{j+1}+d_j$ for every $j$ satisfying $1\leqslant j \leqslant k-2$, \\ $\bullet$ $d_1, d_2, \ldots, d_k$ are divisors of $n$, \\ $\bullet$ any other divisor of $n$ is either less than $d_1$ or greater than $d_k$. Find all fibby numbers. \\ \\ [i]Proposed by Ivan Novak.[/i]

2016 Israel National Olympiad, 5

Tags: algebra , number theory , Fibonacci , Fibonacci sequence , Polynomials , degree , polynomial

The Fibonacci sequence $F_n$ is defined by $F_1=F_2=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq3$. Let $m,n\geq1$ be integers. Find the minimal degree $d$ for which there exists a polynomial $f(x)=a_dx^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$, which satisfies $f(k)=F_{m+k}$ for all $k=0,1,...,n$.

2021 Saudi Arabia IMO TST, 8

Tags: Fibonacci , combinatorics , IMO Shortlist , IMO Shortlist 2020 , additive representation

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$. [i]Proposed by Croatia[/i]

2023 Regional Olympiad of Mexico Southeast, 4

Tags: algebra , Fibonacci

Given the Fibonacci sequence with $f_0=f_1=1$and for $n\geq 1, f_{n+1}=f_n+f_{n-1}$, find all real solutions to the equation: $$x^{2024}=f_{2023}x+f_{2022}.$$

2020 Brazil National Olympiad, 2

Tags: Fibonacci , number theory , Brazilian Math Olympiad , Brazil , Analytic Number Theory

For a positive integer $a$, define $F_1 ^{(a)}=1$, $F_2 ^{(a)}=a$ and for $n>2$, $F_n ^{(a)}=F_{n-1} ^{(a)}+F_{n-2} ^{(a)}$. A positive integer is [i]fibonatic[/i] when it is equal to $F_n ^{(a)}$ for a positive integer $a$ and $n>3$. Prove that there are infintely many not [i]fibonatic[/i] integers.

2023 Olimphíada, 4

Tags: Fibonacci , college contests

We all know the Fibonacci sequence. However, a slightly less known sequence is the $k$-bonacci sequence. In it, we have $F_1^{(k)} = F_2^{(k)} = \cdots = F_{k-1}^{(k)} = 0, F_k^{(k)} = 1$ and $$F^{(k)}_{n+k} = F^{(k)}_{n+k-1} + F^{(k)}_{n+k-2} + \cdots + F^{(k)}_n,$$for all $n \geq 1$. Find all positive integers $k$ for which there exists a constant $N$ such that $$F^{(k)}_{n-1}F^{(k)}_{n+1} - (F ^{(k)}_n)^2 = (-1)^n$$ for every positive integer $n \geq N$.

2007 IMAC Arhimede, 1

Tags: number theory , Fibonacci , Fibonacci sequence , inequalities , algebra

Let $(f_n) _{n\ge 0}$ be the sequence defined by$ f_0 = 0, f_1 = 1, f_{n + 2 }= f_{n + 1} + f_n$ for $n> 0$ (Fibonacci string) and let $t_n =$ ${n+1}\choose{2}$ for $n \ge 1$ . Prove that: a) $f_1^2+f_2^2+...+f_n^2 = f_n \cdot f_{n+1}$ for $n \ge 1$ b) $\frac{1}{n^2} \cdot \Sigma_{k=1}^{n}\left( \frac{t_k}{f_k}\right)^2 \ge \frac{t_{n+1}^2}{9 f_n \cdot f_{n+1}}$

2015 Israel National Olympiad, 7

Tags: Fibonacci , Fibonacci sequence , prime numbers , Divisibility , number theory , combinatorics

The Fibonacci sequence $F_n$ is defined by $F_0=0,F_1=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq2$. Let $p\geq3$ be a prime number. [list=a] [*] Prove that $F_{p-1}+F_{p+1}-1$ is divisible by $p$. [*] Prove that $F_{p^{k+1}-1}+F_{p^{k+1}+1}-\left(F_{p^k-1}+F_{p^k+1}\right)$ is divisible by $p^{k+1}$ for any positive integer $k$. [/list]

1981 IMO Shortlist, 4

Tags: algebra , Fibonacci , Fibonacci sequence , Sequence , IMO Shortlist , number theory

Let $\{fn\}$ be the Fibonacci sequence $\{1, 1, 2, 3, 5, \dots.\}. $ (a) Find all pairs $(a, b)$ of real numbers such that for each $n$, $af_n +bf_{n+1}$ is a member of the sequence. (b) Find all pairs $(u, v)$ of positive real numbers such that for each $n$, $uf_n^2 +vf_{n+1}^2$ is a member of the sequence.

VMEO I 2004, 2

Tags: Fibonacci Numbers , Fibonacci sequence , Fibonacci , number theory , Perfect power , divisibe

The Fibonacci numbers $(F_n)_{n=1}^{\infty}$ are defined as follows: $$F_1 = F_2 = 1, F_n = F_{n-2} + F_{n-1}, n = 3, 4, ...$$ Assume $p$ is a prime greater than $3$. With $m$ being a natural number greater than $3$, find all $n$ numbers such that $F_n$ is divisible by $p^m$.

2019 Dutch Mathematical Olympiad, 4

Tags: Fibonacci sequence , Fibonacci , Sum , inequalities , algebra

The sequence of Fibonacci numbers $F_0, F_1, F_2, . . .$ is defined by $F_0 = F_1 = 1 $ and $F_{n+2} = F_n+F_{n+1}$ for all $n > 0$. For example, we have $F_2 = F_0 + F_1 = 2, F_3 = F_1 + F_2 = 3, F_4 = F_2 + F_3 = 5$, and $F_5 = F_3 + F_4 = 8$. The sequence $a_0, a_1, a_2, ...$ is defined by $a_n =\frac{1}{F_nF_{n+2}}$ for all $n \ge 0$. Prove that for all $m \ge 0$ we have: $a_0 + a_1 + a_2 + ... + a_m < 1$.

1946 Moscow Mathematical Olympiad, 121

Tags: Fibonacci , Sequence , Integer sequence , algebra

Given the Fibonacci sequence $0, 1, 1, 2, 3, 5, 8, ... ,$ ascertain whether among its first $(10^8+1)$ terms there is a number that ends with four zeros.

2020/2021 Tournament of Towns, P6

Tags: number theory , Fibonacci , Tournament of Towns

Find at least one real number $A{}$ such that for any positive integer $n{}$ the distance between $\lceil A^n\rceil$ and the nearest square of an integer is equal to two. [i]Dmitry Krekov[/i]

2017 Regional Olympiad of Mexico Southeast, 6

Tags: Fibonacci , number theory

Consider $f_1=1, f_2=1$ and $f_{n+1}=f_n+f_{n-1}$ for $n\geq 2$. Determine if exists $n\leq 1000001$ such that the last three digits of $f_n$ are zero.

1983 IMO Longlists, 52

Tags: algebra , polynomial , Fibonacci , Fibonacci sequence , Sequence , IMO Shortlist

Let $(F_n)_{n\geq 1} $ be the Fibonacci sequence $F_1 = F_2 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 1),$ and $P(x)$ the polynomial of degree $990$ satisfying \[ P(k) = F_k, \qquad \text{ for } k = 992, . . . , 1982.\] Prove that $P(1983) = F_{1983} - 1.$

2020 ELMO Problems, P2

Tags: number theory , Fibonacci

Define the Fibonacci numbers by $F_1 = F_2 = 1$ and $F_n = F_{n-1} + F_{n-2}$ for $n\geq 3$. Let $k$ be a positive integer. Suppose that for every positive integer $m$ there exists a positive integer $n$ such that $m \mid F_n-k$. Must $k$ be a Fibonacci number? [i]Proposed by Fedir Yudin.[/i]

2023 SG Originals, Q3

Tags: ICMC , combinatorics , Fibonacci , college contests

Bugs Bunny plays a game in the Euclidean plane. At the $n$-th minute $(n \geq 1)$, Bugs Bunny hops a distance of $F_n$ in the North, South, East, or West direction, where $F_n$ is the $n$-th Fibonacci number (defined by $F_1 = F_2 =1$ and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 3$). If the first two hops were perpendicular, prove that Bugs Bunny can never return to where he started. [i]Proposed by Dylan Toh[/i]

1999 Croatia National Olympiad, Problem 3

Tags: Sum , Summation , Fibonacci , Fibonacci sequence , algebra

Let $(a_n)$ be defined by $a_1=a_2=1$ and $a_n=a_{n-1}+a_{n-2}$ for $n>2$. Compute the sum $\frac{a_1}2+\frac{a_2}{2^2}+\frac{a_3}{2^3}+\ldots$.