Olympiad problems

1992 IMO Shortlist, 18

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

2023 Olimphíada, 2

Tags: fibonacci , sequence , algebra

The Fibonacci sequence is defined by $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1}+F_n$ for every integer $n$. A sequence $(a_n)$ of integers is said to be $\textit{phirme}$ if there is a fixed integer $k$ such that $a_n + a_{n+1} = F_{n+k}$ for all $n \geq 1$. Show that if $(a_n)$ is a $\textit{phirme}$ sequence, then there exists an integer $c$ such that $$a_n = F_{n+k-2} + (-1)^nc.$$

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

2017 Baltic Way, 3

Tags: algebra , fibonacci , additive number theory , extremal combinatorics

Positive integers $x_1,...,x_m$ (not necessarily distinct) are written on a blackboard. It is known that each of the numbers $F_1,...,F_{2018}$ can be represented as a sum of one or more of the numbers on the blackboard. What is the smallest possible value of $m$? (Here $F_1,...,F_{2018}$ are the first $2018$ Fibonacci numbers: $F_1=F_2=1, F_{k+1}=F_k+F_{k-1}$ for $k>1$.)

Russian TST 2021, P2

Tags: fibonacci , combinatorics , 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]

2022 Baltic Way, 7

Tags: fibonacci number , combinatorics , fibonacci , fibonacci sequence

The writer Arthur has $n \ge1$ co-authors who write books with him. Each book has a list of authors including Arthur himself. No two books have the same set of authors. At a party with all his co-author, each co-author writes on a note how many books they remember having written with Arthur. Inspecting the numbers on the notes, they discover that the numbers written down are the first $n$ Fibonacci numbers (defined by $F_1 = F_2 = 1$ and $F_{k+2}= F_{k+1} + F_k$). For which $n$ is it possible that none of the co-authors had a lapse of memory?

2019 USA TSTST, 6

Tags: algebra , integer polynomial , fibonacci

Suppose $P$ is a polynomial with integer coefficients such that for every positive integer $n$, the sum of the decimal digits of $|P(n)|$ is not a Fibonacci number. Must $P$ be constant? (A [i]Fibonacci number[/i] is an element of the sequence $F_0, F_1, \dots$ defined recursively by $F_0=0, F_1=1,$ and $F_{k+2} = F_{k+1}+F_k$ for $k\ge 0$.) [i]Nikolai Beluhov[/i]

2023 SG Originals, Q3

Tags: combinatorics , fibonacci

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]

1983 IMO Shortlist, 19

Tags: polynomial , fibonacci , fibonacci sequence , sequence , algebra

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

2023 Olimphíada, 1

Tags: fibonacci , sequence , algebra

The Fibonacci sequence is defined by $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1}+F_n$ for every integer $n$. Let $k$ be a fixed integer. A sequence $(a_n)$ of integers is said to be $\textit{phirme}$ if $a_n + a_{n+1} = F_{n+k}$ for all $n \geq 1$. Find all $\textit{phirme}$ sequences in terms of $n$ and $k$.

2018 Romanian Master of Mathematics Shortlist, N2

Tags: number theory , fibonacci

Prove that for each positive integer $k$ there exists a number base $b$ along with $k$ triples of Fibonacci numbers $(F_u,F_v,F_w)$ such that when they are written in base $b$, their concatenation is also a Fibonacci number written in base $b$. (Fibonacci numbers are defined by $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1} + F_n$ for all positive integers $n$.) [i]Proposed by Serbia[/i]

1997 Slovenia National Olympiad, Problem 2

Tags: fibonacci sequence , fibonacci

The Fibonacci sequence $f_n$ is defined by $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for $n\in\mathbb N$. (a) Show that $f_{1005}$ is divisible by $10$. (b) Show that $f_{1005}$ is not divisible by $100$.

2015 Israel National Olympiad, 7

Tags: fibonacci , fibonacci sequence , prime number , 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]

2018 Stanford Mathematics Tournament, 4

Tags: fibonacci number , fibonacci , fibonacci sequence , number theory

Let $F_k$ denote the series of Fibonacci numbers shifted back by one index, so that $F_0 = 1$, $F_1 = 1,$ and $F_{k+1} = F_k +F_{k-1}$. It is known that for any fixed $n \ge 1$ there exist real constants $b_n$, $c_n$ such that the following recurrence holds for all $k \ge 1$: $$F_{n\cdot (k+1)} = b_n \cdot F_{n \cdot k} + c_n \cdot F_{n\cdot (k-1)}.$$ Prove that $|c_n| = 1$ for all $n \ge 1$.

2012 USAJMO, 2

Tags: geometry , fibonacci

Find all integers $n \geq 3$ such that among any $n$ positive real numbers $a_1, a_2, \hdots, a_n$ with $\text{max}(a_1,a_2,\hdots,a_n) \leq n \cdot \text{min}(a_1,a_2,\hdots,a_n)$, there exist three that are the side lengths of an acute triangle.

1992 IMO Longlists, 18

Tags: combinatorics , fibonacci , fibonacci sequence , combinatorics of words , sequence

Fibonacci numbers are defined as follows: $F_0 = F_1 = 1, F_{n+2} = F_{n+1}+F_n, n \geq 0$. Let $a_n$ be the number of words that consist of $n$ letters $0$ or $1$ and contain no two letters $1$ at distance two from each other. Express $a_n$ in terms of Fibonacci numbers.

2015 Thailand TSTST, 2

Tags: algebra , polynomial , number theory , fibonacci

Let $\{F_n\}^\infty_{n=1}$ be the Fibonacci sequence and let $f$ be a polynomial of degree $1006$ such that $f(k) = F_k$ for all $k \in \{1008, \dots , 2014\}$. Prove that $$233\mid f(2015)+1.$$ [i]Note: $F_1=F_2=1$ and $F_{n+2}=F_{n+1}+F_n$ for all $n\geq 1$.[/i]

2019 Dutch Mathematical Olympiad, 4

Tags: fibonacci sequence , fibonacci , sum , algebra , inequalities

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

2002 Federal Math Competition of S&M, Problem 2

Tags: geometry , fibonacci

The (Fibonacci) sequence $f_n$ is defined by $f_1=f_2=1$ and $f_{n+2}=f_{n+1}+f_n$ for $n\ge1$. Prove that the area of the triangle with the sides $\sqrt{f_{2n+1}},\sqrt{f_{2n+2}},$ and $\sqrt{f_{2n+3}}$ is equal to $\frac12$.

1992 IMO Longlists, 78

Tags: fibonacci , fibonacci sequence , limit , sequence , 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?

2020 Latvia TST, 1.3

Tags: fibonacci , infinitely many solutions , number theory

Prove that equation $a^2 - b^2=ab - 1$ has infinitely many solutions, if $a,b$ are positive integers

2023 Philippine MO, 7

Tags: number theory , fibonacci

A set of positive integers is said to be [i]pilak[/i] if it can be partitioned into 2 disjoint subsets $F$ and $T$, each with at least $2$ elements, such that the elements of $F$ are consecutive Fibonacci numbers, and the elements of $T$ are consecutive triangular numbers. Find all positive integers $n$ such that the set containing all the positive divisors of $n$ except $n$ itself is pilak.

1983 IMO Longlists, 52

Tags: algebra , polynomial , fibonacci , fibonacci sequence , sequence

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

2018 Mathematical Talent Reward Programme, MCQ: P 3

Tags: fibonacci , algebra

$F_{n}$ denotes the Fibonacci Sequence where $F_{1}=0, F_{2}=1, F_{n}=F_{n-1}+F_{n-2},\ \forall \ n \geq 3$ Find$$\sum\limits_{n=3}^{\infty}\frac{18+999F_n}{F_{n-1}\times F_{n+1}}$$ [list=1] [*] 2016 [*] 2017 [*] 2018 [*] None of these [/list]

2009 BAMO, 2

Tags: fibonacci , sum

The Fibonacci sequence is the list of numbers that begins $1, 2, 3, 5, 8, 13$ and continues with each subsequent number being the sum of the previous two. Prove that for every positive integer $n$ when the first $n$ elements of the Fibonacci sequence are alternately added and subtracted, the result is an element of the sequence or the negative of an element of the sequence. For example, when $n = 4$ we have $1-2+3-5 = -3$ and $3$ is an element of the Fibonacci sequence.