Olympiad problems

2021 Saudi Arabia IMO TST, 6

Find all functions $f : \mathbb{Z}\rightarrow \mathbb{Z}$ satisfying \[f^{a^{2} + b^{2}}(a+b) = af(a) +bf(b)\] for all integers $a$ and $b$

1992 IMO Longlists, 7

Tags: function , geometry , coordinate geometry , Iteration , IMO Shortlist , IMO Longlist

Let $X$ be a bounded, nonempty set of points in the Cartesian plane. Let $f(X)$ be the set of all points that are at a distance of at most $1$ from some point in $X$. Let $f_n(X) = f(f(\cdots(f(X))\cdots))$ ($n$ times). Show that $f_n(X)$ becomes “more circular” as $n$ gets larger. In other words, if $r_n = \sup\{\text{radii of circles contained in } f_n(X) \}$ and $R_n = \inf \{\text{radii of circles containing } f_n(X)\}$, then show that $R_n/r_n$ gets arbitrarily close to $1$ as $n$ becomes arbitrarily large. [hide]I'm not sure that I'm posting this in a right forum. If it's in a wrong forum, please mods move it.[/hide]

1990 IMO Longlists, 95

Tags: algebra , polynomial , number theory , Cubic , Iteration , IMO Shortlist

Let $ p(x)$ be a cubic polynomial with rational coefficients. $ q_1$, $ q_2$, $ q_3$, ... is a sequence of rationals such that $ q_n \equal{} p(q_{n \plus{} 1})$ for all positive $ n$. Show that for some $ k$, we have $ q_{n \plus{} k} \equal{} q_n$ for all positive $ n$.

1990 IMO Shortlist, 26

Tags: algebra , polynomial , number theory , Cubic , Iteration , IMO Shortlist

Let $ p(x)$ be a cubic polynomial with rational coefficients. $ q_1$, $ q_2$, $ q_3$, ... is a sequence of rationals such that $ q_n \equal{} p(q_{n \plus{} 1})$ for all positive $ n$. Show that for some $ k$, we have $ q_{n \plus{} k} \equal{} q_n$ for all positive $ n$.

1995 IMO Shortlist, 3

Tags: induction , algebra , polynomial , Iteration , Sequence , IMO Shortlist , imo 1995

For an integer $x \geq 1$, let $p(x)$ be the least prime that does not divide $x$, and define $q(x)$ to be the product of all primes less than $p(x)$. In particular, $p(1) = 2.$ For $x$ having $p(x) = 2$, define $q(x) = 1$. Consider the sequence $x_0, x_1, x_2, \ldots$ defined by $x_0 = 1$ and \[ x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} \] for $n \geq 0$. Find all $n$ such that $x_n = 1995$.

1992 IMO Longlists, 35

Tags: algebra , polynomial , functional equation , Iteration , IMO Shortlist , IMO Longlist

Let $ f(x)$ be a polynomial with rational coefficients and $ \alpha$ be a real number such that \[ \alpha^3 \minus{} \alpha \equal{} [f(\alpha)]^3 \minus{} f(\alpha) \equal{} 33^{1992}.\] Prove that for each $ n \geq 1,$ \[ \left [ f^{n}(\alpha) \right]^3 \minus{} f^{n}(\alpha) \equal{} 33^{1992},\] where $ f^{n}(x) \equal{} f(f(\cdots f(x))),$ and $ n$ is a positive integer.

2018 China Team Selection Test, 6

Tags: function , Divisibility , Iteration , algebra , functional equation

Let $M,a,b,r$ be non-negative integers with $a,r\ge 2$, and suppose there exists a function $f:\mathbb{Z}\rightarrow\mathbb{Z}$ satisfying the following conditions: (1) For all $n\in \mathbb{Z}$, $f^{(r)}(n)=an+b$ where $f^{(r)}$ denotes the composition of $r$ copies of $f$ (2) For all $n\ge M$, $f(n)\ge 0$ (3) For all $n>m>M$, $n-m|f(n)-f(m)$ Show that $a$ is a perfect $r$-th power.

2021 Thailand TST, 3

Tags: algebra , functional equation , IMO Shortlist , IMO Shortlist 2020 , Iteration

Find all functions $f : \mathbb{Z}\rightarrow \mathbb{Z}$ satisfying \[f^{a^{2} + b^{2}}(a+b) = af(a) +bf(b)\] for all integers $a$ and $b$

2020 IMO Shortlist, A6

Tags: algebra , functional equation , IMO Shortlist , IMO Shortlist 2020 , Iteration

Find all functions $f : \mathbb{Z}\rightarrow \mathbb{Z}$ satisfying \[f^{a^{2} + b^{2}}(a+b) = af(a) +bf(b)\] for all integers $a$ and $b$

1976 IMO Longlists, 29

Tags: floor function , function , algebra , Iteration , interval , IMO Shortlist

Let $I = (0, 1]$ be the unit interval of the real line. For a given number $a \in (0, 1)$ we define a map $T : I \to I$ by the formula if \[ T (x, y) = \begin{cases} x + (1 - a),&\mbox{ if } 0< x \leq a,\\ \text{ } \\ x - a, & \mbox{ if } a < x \leq 1.\end{cases} \] Show that for every interval $J \subset I$ there exists an integer $n > 0$ such that $T^n(J) \cap J \neq \emptyset.$

1995 IMO Shortlist, 1

Tags: algebra , IMO Shortlist , functional equation , Iteration

Does there exist a sequence $ F(1), F(2), F(3), \ldots$ of non-negative integers that simultaneously satisfies the following three conditions? [b](a)[/b] Each of the integers $ 0, 1, 2, \ldots$ occurs in the sequence. [b](b)[/b] Each positive integer occurs in the sequence infinitely often. [b](c)[/b] For any $ n \geq 2,$ \[ F(F(n^{163})) \equal{} F(F(n)) \plus{} F(F(361)). \]

1992 IMO Shortlist, 9

Tags: algebra , polynomial , functional equation , Iteration , IMO Shortlist , IMO Longlist

Let $ f(x)$ be a polynomial with rational coefficients and $ \alpha$ be a real number such that \[ \alpha^3 \minus{} \alpha \equal{} [f(\alpha)]^3 \minus{} f(\alpha) \equal{} 33^{1992}.\] Prove that for each $ n \geq 1,$ \[ \left [ f^{n}(\alpha) \right]^3 \minus{} f^{n}(\alpha) \equal{} 33^{1992},\] where $ f^{n}(x) \equal{} f(f(\cdots f(x))),$ and $ n$ is a positive integer.

1976 IMO Shortlist, 7

Tags: floor function , function , algebra , Iteration , interval , IMO Shortlist

Let $I = (0, 1]$ be the unit interval of the real line. For a given number $a \in (0, 1)$ we define a map $T : I \to I$ by the formula if \[ T (x, y) = \begin{cases} x + (1 - a),&\mbox{ if } 0< x \leq a,\\ \text{ } \\ x - a, & \mbox{ if } a < x \leq 1.\end{cases} \] Show that for every interval $J \subset I$ there exists an integer $n > 0$ such that $T^n(J) \cap J \neq \emptyset.$

2017-IMOC, A7

Tags: algebra , Iteration , function , functional equation

Determine all non negative integers $k$ such that there is a function $f : \mathbb{N} \to \mathbb{N}$ that satisfies \[ f^n(n) = n + k \] for all $n \in \mathbb{N}$

2018 China Team Selection Test, 6

Tags: function , Divisibility , Iteration , algebra , functional equation

Let $M,a,b,r$ be non-negative integers with $a,r\ge 2$, and suppose there exists a function $f:\mathbb{Z}\rightarrow\mathbb{Z}$ satisfying the following conditions: (1) For all $n\in \mathbb{Z}$, $f^{(r)}(n)=an+b$ where $f^{(r)}$ denotes the composition of $r$ copies of $f$ (2) For all $n\ge M$, $f(n)\ge 0$ (3) For all $n>m>M$, $n-m|f(n)-f(m)$ Show that $a$ is a perfect $r$-th power.

2018 Pan-African Shortlist, A7

Tags: algebra , number theory , Iteration , Integer sequence

Let $f(n) = n + \lfloor \sqrt{n} \rfloor$. Prove that for every positive integer $m$, the integer sequence $m, f(m), f(f(m)), \dots$ contains at least one square of an integer.

2025 Euler Olympiad, Round 2, 6

Tags: Euler Olympiad , algebra , combinatorics , number theory , graph theory , Iteration

For any subset $S \subseteq \mathbb{Z}^+$, a function $f : S \to S$ is called [i]interesting[/i] if the following two conditions hold: [b]1.[/b] There is no element $a \in S$ such that $f(a) = a$. [b]2.[/b] For every $a \in S$, we have $f^{f(a) + 1}(a) = a$ (where $f^{k}$ denotes the $k$-th iteration of $f$). Prove that: [b]a) [/b]There exist infinitely many interesting functions $f : \mathbb{Z}^+ \to \mathbb{Z}^+$. [b]b) [/b]There exist infinitely many positive integers $n$ for which there is no interesting function $$ f : \{1, 2, \ldots, n\} \to \{1, 2, \ldots, n\}. $$ [i]Proposed by Giorgi Kekenadze, Georgia[/i]

2021 Taiwan TST Round 3, 4

Tags: algebra , functional equation , IMO Shortlist , IMO Shortlist 2020 , Iteration

Find all functions $f : \mathbb{Z}\rightarrow \mathbb{Z}$ satisfying \[f^{a^{2} + b^{2}}(a+b) = af(a) +bf(b)\] for all integers $a$ and $b$

1993 IMO Shortlist, 5

Tags: function , modular arithmetic , number theory , Iteration , functional equation , IMO Shortlist

Let $S$ be the set of all pairs $(m,n)$ of relatively prime positive integers $m,n$ with $n$ even and $m < n.$ For $s = (m,n) \in S$ write $n = 2^k \cdot n_o$ where $k, n_0$ are positive integers with $n_0$ odd and define \[ f(s) = (n_0, m + n - n_0). \] Prove that $f$ is a function from $S$ to $S$ and that for each $s = (m,n) \in S,$ there exists a positive integer $t \leq \frac{m+n+1}{4}$ such that \[ f^t(s) = s, \] where \[ f^t(s) = \underbrace{ (f \circ f \circ \cdots \circ f) }_{t \text{ times}}(s). \] If $m+n$ is a prime number which does not divide $2^k - 1$ for $k = 1,2, \ldots, m+n-2,$ prove that the smallest value $t$ which satisfies the above conditions is $\left [\frac{m+n+1}{4} \right ]$ where $\left[ x \right]$ denotes the greatest integer $\leq x.$