Olympiad problems

1967 IMO Shortlist, 1

In a sports meeting a total of $m$ medals were awarded over $n$ days. On the first day one medal and $\frac{1}{7}$ of the remaining medals were awarded. On the second day two medals and $\frac{1}{7}$ of the remaining medals were awarded, and so on. On the last day, the remaining $n$ medals were awarded. How many medals did the meeting last, and what was the total number of medals ?

2021 Saudi Arabia JBMO TST, 1

Tags: number theory , recurrence relation

Let $(a_n)_{n\ge 1}$ be a sequence given by $a_1 = 45$ and $$a_n = a^2_{n-1} + 15a_{n-1}$$ for $n > 1$. Prove that the sequence contains no perfect squares.

2020 Regional Olympiad of Mexico Northeast, 1

Tags: floor function , algebra , recurrence relation , sequence

Let $a_1=2020$ and let $a_{n+1}=\sqrt{2020+a_n}$ for $n\ge 1$. How much is $\left\lfloor a_{2020}\right\rfloor$? Note: $\lfloor x\rfloor$ denotes the integer part of a number, that is that is, the immediate integer less than $x$. For example, $\lfloor 2.71\rfloor=2$ and $\lfloor \pi\rfloor=3$.

1984 Bundeswettbewerb Mathematik, 3

Tags: algebra , recurrence relation , sequence

The sequences $a_1, a_2, a_3,...$ and $b_1, b_2, b_3,... $suffices for all positive integers $n$ of the following recursion: $a_{n+1} = a_n - b_n$ and $b_{n+1} = 2b_n$, if $a_n \ge b_n$, $a_{n+1} = 2a_n$ and $b_{n+1} = b_n - a_n$, if $a_n < b_n$. For which pairs $(a_1, b_1)$ of positive real initial terms is there an index $k$ with $a_k = 0$?

1989 Romania Team Selection Test, 2

Tags: recurrence relation , sequence , number theory , algebra

The sequence ($a_n$) is defined by $a_1 = a_2 = 1, a_3 = 199$ and $a_{n+1} =\frac{1989+a_na_{n-1}}{a_{n-2}}$ for all $n \ge 3$. Prove that all terms of the sequence are positive integers

1973 Dutch Mathematical Olympiad, 4

Tags: recurrence relation , sequence , limit , algebra

We have an infinite sequence of real numbers $x_0,x_1, x_2, ... $ such that $x_{n+1} = \sqrt{x_n -\frac14}$ holds for all natural $n$ and moreover $x_0 \in \frac12$. (a) Prove that for every natural $n$ holds: $x_n > \frac12$ (b) Prove that $\lim_{n \to \infty} x_n$ exists. Calculate this limit.

1989 IMO Shortlist, 16

Tags: algebra , sequence , recurrence relation , inequality

The set $ \{a_0, a_1, \ldots, a_n\}$ of real numbers satisfies the following conditions: [b](i)[/b] $ a_0 \equal{} a_n \equal{} 0,$ [b](ii)[/b] for $ 1 \leq k \leq n \minus{} 1,$ \[ a_k \equal{} c \plus{} \sum^{n\minus{}1}_{i\equal{}k} a_{i\minus{}k} \cdot \left(a_i \plus{} a_{i\plus{}1} \right)\] Prove that $ c \leq \frac{1}{4n}.$

1988 Bundeswettbewerb Mathematik, 4

Tags: algebra , recurrence relation

Starting with four given integers $a_1, b_1, c_1, d_1$ is defined recursively for all positive integers $n$: $$a_{n+1} := |a_n - b_n|, b_{n+1} := |b_n - c_n|, c_{n+1} := |c_n - d_n|, d_{n+1} := |d_n - a_n|.$$ Prove that there is a natural number $k$ such that all terms $a_k, b_k, c_k, d_k$ take the value zero.

2009 Kyiv Mathematical Festival, 5

Tags: algebra , sequence , recurrence relation , recursion , inequalities

a) Suppose that a sequence of numbers $x_1,x_2,x_3,...$ satisfies the inequality $x_n-2x_{n+1}+x_{n+2} \le 0$ for any $n$ . Moreover $x_o=1,x_{20}=9,x_{200}=6$. What is the maximal value of $x_{2009}$ can be? b) Suppose that a sequence of numbers $x_1,x_2,x_3,...$ satisfies the inequality $2x_n-3x_{n+1}+x_{n+2} \le 0$ for any $n$. Moreover $x_o=1,x_1=2,x_3=1$. Can $x_{2009}$ be greater then $0,678$ ?

2019 Saint Petersburg Mathematical Olympiad, 1

Tags: arithmetic sequence , algebra , arithmetic progression , recurrence , recurrence relation

For a non-constant arithmetic progression $(a_n)$ there exists a natural $n$ such that $a_{n}+a_{n+1} = a_{1}+…+a_{3n-1}$ . Prove that there are no zero terms in this progression.

1965 Dutch Mathematical Olympiad, 1

Tags: recurrence relation , product , algebra

We consider the sequence $t_1,t_2,t_3,...$ By $P_n$ we mean the product of the first $n$ terms of the sequence. Given that $t_{n+1} = t_n \cdot t_{n+2}$ for each $n$, and that $P_{40} = P_{80} = 8$. Calculate $t_1$ and $t_2$.

2008 China Team Selection Test, 2

Tags: induction , number theory , algebra , sequence , recurrence relation

The sequence $ \{x_{n}\}$ is defined by $ x_{1} \equal{} 2,x_{2} \equal{} 12$, and $ x_{n \plus{} 2} \equal{} 6x_{n \plus{} 1} \minus{} x_{n}$, $ (n \equal{} 1,2,\ldots)$. Let $ p$ be an odd prime number, let $ q$ be a prime divisor of $ x_{p}$. Prove that if $ q\neq2,3,$ then $ q\geq 2p \minus{} 1$.

2016 Brazil Undergrad MO, 3

Tags: number theory , recurrence relation

Let it $k \geq 1$ be an integer. Define the sequence $(a_n)_{n \geq 1}$ by $a_0=0,a_1=1$ and \[ a_{n+2} = ka_{n+1}+a_n \] for $n \geq 0$. Let it $p$ an odd prime number. Denote $m(p)$ as the smallest positive integer $m$ such that $p | a_m$. Denote $T(p)$ as the smallest positive integer $T$ such that for every natural $j$ we gave $p | (a_{T+j}-a_j)$. [list='i'] [*] Show that $T(p) \leq (p-1) \cdot m(p)$. [*] Show that if $T(p) = (p-1) \cdot m(p)$ then \[ \prod_{1 \leq j \leq T(p)-1}^{j \not \equiv 0 \pmod{m(p)}}{a_j} \equiv (-1)^{m(p)-1} \pmod{p} \] [/list]

1990 IMO Longlists, 62

Tags: function , algebra , recurrence relation , recursion

Let $ a, b \in \mathbb{N}$ with $ 1 \leq a \leq b,$ and $ M \equal{} \left[\frac {a \plus{} b}{2} \right].$ Define a function $ f: \mathbb{Z} \mapsto \mathbb{Z}$ by \[ f(n) \equal{} \begin{cases} n \plus{} a, & \text{if } n \leq M, \\ n \minus{} b, & \text{if } n >M. \end{cases} \] Let $ f^1(n) \equal{} f(n),$ $ f_{i \plus{} 1}(n) \equal{} f(f^i(n)),$ $ i \equal{} 1, 2, \ldots$ Find the smallest natural number $ k$ such that $ f^k(0) \equal{} 0.$

2013 Saudi Arabia BMO TST, 4

Tags: algebra , recurrence relation , function

Let $f : Z_{\ge 0} \to Z_{\ge 0}$ be a function which satisfies for all integer $n \ge 0$: (a) $f(2n + 1)^2 - f(2n)^2 = 6f(n) + 1$, (b) $f(2n) \ge f(n)$ where $Z_{\ge 0}$ is the set of nonnegative integers. Solve the equation $f(n) = 1000$

1989 Poland - Second Round, 5

Tags: algebra , recurrence relation , floor function , number theory

Given a sequence $ (c_n) $ of natural numbers defined recursively: $ c_1 = 2 $, $ c_{n+1} = \left[ \frac{3}{2}c_n\right] $. Prove that there are infinitely many even numbers and infinitely many odd numbers among the terms of this sequence.

1989 Austrian-Polish Competition, 7

Tags: recurrence relation , function , algebra

Functions $f_0, f_1,f_2,...$ are recursively defined by $f_0(x) = x$ and $f_{2k+1} (x) = 3^{f_{2k}(x)}$ and $f_{2k+2} = 2^{f_{2k+1}(x)}$, $k = 0,1,2,...$ for all $x \in R$. Find the greater one of the numbers $f_{10}(1)$ and $f_9(2)$.

2008 Federal Competition For Advanced Students, P1, 3

Tags: inequalities , sequence , recurrence relation , algebra

Let $p > 1$ be a natural number. Consider the set $F_p$ of all non-constant sequences of non-negative integers that satisfy the recursive relation $a_{n+1} = (p+1)a_n - pa_{n-1}$ for all $n > 0$. Show that there exists a sequence ($a_n$) in $F_p$ with the property that for every other sequence ($b_n$) in $F_p$, the inequality $a_n \le b_n$ holds for all $n$.

2008 VJIMC, Problem 2

Tags: fe , functional equation , recurrence relation , algebra , sequence

Find all functions $f:(0,\infty)\to(0,\infty)$ such that $$f(f(f(x)))+4f(f(x))+f(x)=6x.$$

2019 Pan-African, 1

Tags: recurrence relation , algebra , induction , linear recurrence

Let $(a_n)_{n=0}^{\infty}$ be a sequence of real numbers defined as follows: [list] [*] $a_0 = 3$, $a_1 = 2$, and $a_2 = 12$; and [*] $2a_{n + 3} - a_{n + 2} - 8a_{n + 1} + 4a_n = 0$ for $n \geq 0$. [/list] Show that $a_n$ is always a strictly positive integer.

2019 Peru EGMO TST, 5

Tags: recurrence relation , sequence , inequalities , algebra

Define the sequence sequence $a_0,a_1, a_2,....,a_{2018}, a_{2019}$ of real numbers as follows: $\bullet$ $a_0 = 1$. $\bullet$ $a_{n + 1} = a_n - \frac{a_n^2}{2019}$ for $n = 0, 1, ...,2018$. Prove that $a_{2019} < \frac12 <a_{2018}$.

2000 Regional Competition For Advanced Students, 4

Tags: rational , number theory , algebra , sequence , recurrence relation

We consider the sequence $\{u_n\}$ defined by recursion $u_{n+1} =\frac{u_n(u_n + 1)}{n}$ for $n \ge 1$. (a) Determine the terms of the sequence for $u_1 = 1$. (b) Show that if a member of the sequence is rational, then all subsequent members are also rational numbers. (c) Show that for every natural number $K$ there is a $u_1 > 1$ such that the first $K$ terms of the sequence are natural numbers.

1980 Austrian-Polish Competition, 7

Tags: number theory , sequence , recurrence relation

Find the greatest natural number $n$ such there exist natural numbers $x_{1}, x_{2}, \ldots, x_{n}$ and natural $a_{1}< a_{2}< \ldots < a_{n-1}$ satisfying the following equations for $i =1,2,\ldots,n-1$: \[x_{1}x_{2}\ldots x_{n}= 1980 \quad \text{and}\quad x_{i}+\frac{1980}{x_{i}}= a_{i}.\]

1997 Tournament Of Towns, (551) 1

Tags: algebra , sequence , recurrence relation

The sequence $x_1,x_2, ...$ is defined by the following equations: $$x_1=19, \ \ x_2=97, \ \ x_{n+2} =x_n - \frac{1}{x_{n+1}}$$ for $n \ge 1$. Prove that there exists a positive integer $k$ such that $x_k=0$ and find $k$. (A Berzinsh)

1979 IMO Shortlist, 9

Tags: combinatorics , recurrence relation , counting , linear recurrence

Let $A$ and $E$ be opposite vertices of an octagon. A frog starts at vertex $A.$ From any vertex except $E$ it jumps to one of the two adjacent vertices. When it reaches $E$ it stops. Let $a_n$ be the number of distinct paths of exactly $n$ jumps ending at $E$. Prove that: \[ a_{2n-1}=0, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}. \]