Olympiad problems

2012 Finnish National High School Mathematics Competition, 5

The [i]Collatz's function[i] is a mapping $f:\mathbb{Z}_+\to\mathbb{Z}_+$ satisfying \[ f(x)=\begin{cases} 3x+1,& \mbox{as }x\mbox{ is odd}\\ x/2, & \mbox{as }x\mbox{ is even.}\\ \end{cases} \] In addition, let us define the notation $f^1=f$ and inductively $f^{k+1}=f\circ f^k,$ or to say in another words, $f^k(x)=\underbrace{f(\ldots (f}_{k\text{ times}}(x)\ldots ).$ Prove that there is an $x\in\mathbb{Z}_+$ satisfying \[f^{40}(x)> 2012x.\]

1995 Polish MO Finals, 3

Tags: induction , modular arithmetic , algebra , polynomial , number theory

Let $p$ be a prime number, and define a sequence by: $x_i=i$ for $i=,0,1,2...,p-1$ and $x_n=x_{n-1}+x_{n-p}$ for $n \geq p$ Find the remainder when $x_{p^3}$ is divided by $p$.

2010 Albania National Olympiad, 2

Tags: induction , algebra

We denote $N_{2010}=\{1,2,\cdots,2010\}$ [b](a)[/b]How many non empty subsets does this set have? [b](b)[/b]For every non empty subset of the set $N_{2010}$ we take the product of the elements of the subset. What is the sum of these products? [b](c)[/b]Same question as the [b](b)[/b] part for the set $-N_{2010}=\{-1,-2,\cdots,-2010\}$. Albanian National Mathematical Olympiad 2010---12 GRADE Question 2.

2007 Vietnam Team Selection Test, 1

Tags: induction , combinatorics

Given two sets $A, B$ of positive real numbers such that: $|A| = |B| =n$; $A \neq B$ and $S(A)=S(B)$, where $|X|$ is the number of elements and $S(X)$ is the sum of all elements in set $X$. Prove that we can fill in each unit square of a $n\times n$ square with positive numbers and some zeros such that: a) the set of the sum of all numbers in each row equals $A$; b) the set of the sum of all numbers in each column equals $A$. c) there are at least $(n-1)^{2}+k$ zero numbers in the $n\times n$ array with $k=|A \cap B|$.

2004 Putnam, A1

Tags: induction , inequalities , percent

Basketball star Shanille O'Keal's team statistician keeps track of the number, $S(N),$ of successful free throws she has made in her first $N$ attempts of the season. Early in the season, $S(N)$ was less than 80% of $N,$ but by the end of the season, $S(N)$ was more than 80% of $N.$ Was there necessarily a moment in between when $S(N)$ was exactly 80% of $N$?

2008 China Team Selection Test, 1

Tags: algorithm , induction , geometry

Prove that in a plane, arbitrary $ n$ points can be overlapped by discs that the sum of all the diameters is less than $ n$, and the distances between arbitrary two are greater than $ 1$. (where the distances between two discs that have no common points are defined as that the distances between its centers subtract the sum of its radii; the distances between two discs that have common points are zero)

2012 Macedonia National Olympiad, 3

Tags: function , floor function , inequalities , induction , ceiling function , algebra

Find all functions $f : \mathbb{R} \to \mathbb{Z}$ which satisfy the conditions: $f(x+y) < f(x) + f(y)$ $f(f(x)) = \lfloor {x} \rfloor + 2$

2007 Tournament Of Towns, 6

Tags: induction , irrational number , algebra

Let $a_0$ be an irrational number such that $0 < a_0 < \frac 12$ . Define $a_n = \min \{2a_{n-1},1 - 2a_{n-1}\}$ for $n \geq 1$. [list][b](a)[/b] Prove that $a_n < \frac{3}{16}$ for some $n$. [b](b)[/b] Can it happen that $a_n > \frac{7}{40}$ for all $n$?[/list]

1998 Junior Balkan MO, 3

Tags: induction , algebra , number theory , equation

Find all pairs of positive integers $ (x,y)$ such that \[ x^y \equal{} y^{x \minus{} y}. \] [i]Albania[/i]

PEN K Problems, 18

Tags: functional equation , function , induction

Find all functions $f: \mathbb{Q}\to \mathbb{R}$ such that for all $x,y\in \mathbb{Q}$: \[f(xy)=f(x)f(y)-f(x+y)+1.\]

2019 Pan-African Shortlist, A1

Tags: linear recurrence , recurrence relation , algebra , induction

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.

1980 IMO, 3

Tags: induction , combinatorial geometry , euclidean distance , geometry

Let $S$ be a set of 1980 points in the plane such that the distance between every pair of them is at least 1. Prove that $S$ has a subset of 220 points such that the distance between every pair of them is at least $\sqrt{3}.$

1998 Romania Team Selection Test, 3

Tags: inequalities , induction , divisibility theory

Find all positive integers $(x, n)$ such that $x^{n}+2^{n}+1$ divides $x^{n+1}+2^{n+1}+1$.

PEN S Problems, 6

Tags: algebra , polynomial , induction , complex number

Suppose that $x$ and $y$ are complex numbers such that \[\frac{x^{n}-y^{n}}{x-y}\] are integers for some four consecutive positive integers $n$. Prove that it is an integer for all positive integers $n$.

2014 Greece Team Selection Test, 1

Tags: induction , modular arithmetic , quadratic , number theory

Let $(x_{n}) \ n\geq 1$ be a sequence of real numbers with $x_{1}=1$ satisfying $2x_{n+1}=3x_{n}+\sqrt{5x_{n}^{2}-4}$ a) Prove that the sequence consists only of natural numbers. b) Check if there are terms of the sequence divisible by $2011$.

2013 India IMO Training Camp, 1

Tags: induction , rearrangement inequality , inequalities

Let $a, b, c$ be positive real numbers such that $a + b + c = 1$. If $n$ is a positive integer then prove that \[ \frac{(3a)^n}{(b + 1)(c + 1)} + \frac{(3b)^n}{(c + 1)(a + 1)} + \frac{(3c)^n}{(a + 1)(b + 1)} \ge \frac{27}{16} \,. \]

2014 Saudi Arabia BMO TST, 5

Tags: induction , inequalities , algebra

Find all positive integers $n$ such that \[3^n+4^n+\cdots+(n+2)^n=(n+3)^n.\]

1998 Iran MO (2nd round), 1

Tags: induction , rearrangement inequality , inequalities

If $a_1<a_2<\cdots<a_n$ be real numbers, prove that: \[ a_1a_2^4+a_2a_3^4+\cdots+a_{n-1}a_n^4+a_na_1^4\geq a_2a_1^4+a_3a_2^4+\cdots+a_na_{n-1}^4+a_1a_n^4. \]

1981 Miklós Schweitzer, 4

Tags: superior algebra , induction

Let $ G$ be finite group and $ \mathcal{K}$ a conjugacy class of $ G$ that generates $ G$. Prove that the following two statements are equivalent: (1) There exists a positive integer $ m$ such that every element of $ G$ can be written as a product of $ m$ (not necessarily distinct) elements of $ \mathcal{K}$. (2) $ G$ is equal to its own commutator subgroup. [i]J. Denes[/i]

PEN L Problems, 4

Tags: linear recurrence , induction

The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $F_{mn}-F_{n+1}^{m}+F_{n-1}^{m}$ is divisible by $F_{n}^{3}$ for all $m \ge 1$ and $n>1$.

1971 IMO Longlists, 44

Tags: induction , number theory , logarithm

Let $m$ and $n$ denote integers greater than $1$, and let $\nu (n)$ be the number of primes less than or equal to $n$. Show that if the equation $\frac{n}{\nu(n)}=m$ has a solution, then so does the equation $\frac{n}{\nu(n)}=m-1$.

2005 Gheorghe Vranceanu, 3

Tags: induction , combinatorics , number theory

Prove by the method of induction that: [b]a)[/b] $ a!b! $ divides $ (a+b)! , $ for any natural numbers $ a,b. $ [b]b)[/b] $ p $ divides $ (-1)^{k+1} +\binom{p-1}{k} , $ for any odd primes $ p $ and $ k\in\{ 0,1,\ldots ,p-1\} . $

2011 ELMO Shortlist, 2

Tags: function , induction , functional equation , algebra

Find all functions $f:\mathbb{R}^+\to\mathbb{R}^+$ such that whenever $a>b>c>d>0$ and $ad=bc$, \[f(a+d)+f(b-c)=f(a-d)+f(b+c).\] [i]Calvin Deng.[/i]

2011 ELMO Shortlist, 6

Tags: algebra , polynomial , counting , derangement , induction , geometric transformation , geometry

Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$, \[\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!} = Q(n),\]where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$. [i]Calvin Deng.[/i]

PEN K Problems, 4

Tags: functional equation , function , induction , algebra , polynomial , complex number

Find all functions $f: \mathbb{N}\to \mathbb{N}$ such that for all $n\in \mathbb{N}$: \[f(f(f(n)))+f(f(n))+f(n)=3n.\]