Olympiad problems

1982 IMO Longlists, 48

Given a finite sequence of complex numbers $c_1, c_2, \ldots , c_n$, show that there exists an integer $k$ ($1 \leq k \leq n$) such that for every finite sequence $a_1, a_2, \ldots, a_n$ of real numbers with $1 \geq a_1 \geq a_2 \geq \cdots \geq a_n \geq 0$, the following inequality holds: \[\left| \sum_{m=1}^n a_mc_m \right| \leq \left| \sum_{m=1}^k c_m \right|.\]

2011 All-Russian Olympiad, 2

Tags: quadratic , invariant , vieta , induction , algebra , polynomial , arithmetic sequence

In the notebooks of Peter and Nick, two numbers are written. Initially, these two numbers are 1 and 2 for Peter and 3 and 4 for Nick. Once a minute, Peter writes a quadratic trinomial $f(x)$, the roots of which are the two numbers in his notebook, while Nick writes a quadratic trinomial $g(x)$ the roots of which are the numbers in [i]his[/i] notebook. If the equation $f(x)=g(x)$ has two distinct roots, one of the two boys replaces the numbers in his notebook by those two roots. Otherwise, nothing happens. If Peter once made one of his numbers 5, what did the other one of his numbers become?

2018 Bulgaria EGMO TST, 3

Tags: induction , function , algebra

Find all one-to-one mappings $f:\mathbb{N}\to\mathbb{N}$ such that for all positive integers $n$ the following relation holds: \[ f(f(n)) \leq \frac {n+f(n)} 2 . \]

2013 USAMTS Problems, 3

Tags: geometry , induction , ratio , inequalities , limit , arithmetic sequence

An infinite sequence of positive real numbers $a_1,a_2,a_3,\dots$ is called [i]territorial[/i] if for all positive integers $i,j$ with $i<j$, we have $|a_i-a_j|\ge\tfrac1j$. Can we find a territorial sequence $a_1,a_2,a_3,\dots$ for which there exists a real number $c$ with $a_i<c$ for all $i$?

2002 China Team Selection Test, 2

Tags: 3d geometry , sphere , vector , induction , geometry

There are $ n$ points ($ n \geq 4$) on a sphere with radius $ R$, and not all of them lie on the same semi-sphere. Prove that among all the angles formed by any two of the $ n$ points and the sphere centre $ O$ ($ O$ is the vertex of the angle), there is at least one that is not less than $ \displaystyle 2 \arcsin{\frac{\sqrt{6}}{3}}$.

1987 China Team Selection Test, 2

Tags: polygon , analytic geometry , induction , coordinates , geometry

A closed recticular polygon with 100 sides (may be concave) is given such that it's vertices have integer coordinates, it's sides are parallel to the axis and all it's sides have odd length. Prove that it's area is odd.

2005 Iran Team Selection Test, 3

Tags: function , induction , modular arithmetic , analytic geometry , combinatorics

Suppose $S= \{1,2,\dots,n\}$ and $n \geq 3$. There is $f:S^k \longmapsto S$ that if $a,b \in S^k$ and $a$ and $b$ differ in all of elements then $f(a) \neq f(b)$. Prove that $f$ is a function of one of its elements.

2013 Kazakhstan National Olympiad, 3

Tags: induction , inequalities , algebra

Consider the following sequence : $a_1=1 ; a_n=\frac{a_[{\frac{n}{2}]}}{2}+\frac{a_[{\frac{n}{3}]}}{3}+\ldots+\frac{a_[{\frac{n}{n}]}}{n}$. Prove that $ a_{2n}< 2*a_{n } (\forall n\in\mathbb{N})$

2011 ELMO Shortlist, 2

Tags: directed graph , induction , combinatorics , graph theory , coloring

A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$, $v$ is not simultaneously in the same set with both of the vertices that it points to. [i]David Yang.[/i] [hide="Stronger Version"]See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492100]here[/url].[/hide]

2009 IMS, 4

Tags: ratio , vector , algebra , polynomial , limit , induction , absolute value

In this infinite tree, degree of each vertex is equal to 3. A real number $ \lambda$ is given. We want to assign a real number to each node in such a way that for each node sum of numbers assigned to its neighbors is equal to $ \lambda$ times of the number assigned to this node. Find all $ \lambda$ for which this is possible.

2012 ELMO Shortlist, 4

Tags: induction , floor function , ceiling function , inequalities , pigeonhole principle , combinatorics

A tournament on $2k$ vertices contains no $7$-cycles. Show that its vertices can be partitioned into two sets, each with size $k$, such that the edges between vertices of the same set do not determine any $3$-cycles. [i]Calvin Deng.[/i]

2007 IMC, 5

Tags: function , modular arithmetic , algebra , polynomial , induction

Let $ n$ be a positive integer and $ a_{1}, \ldots, a_{n}$ be arbitrary integers. Suppose that a function $ f: \mathbb{Z}\to \mathbb{R}$ satisfies $ \sum_{i=1}^{n}f(k+a_{i}l) = 0$ whenever $ k$ and $ l$ are integers and $ l \ne 0$. Prove that $ f = 0$.

2011 Stars Of Mathematics, 3

Tags: induction , inequalities

For a given integer $n\geq 3$, determine the range of values for the expression \[ E_n(x_1,x_2,\ldots,x_n) := \dfrac {x_1} {x_2} + \dfrac {x_2} {x_3} + \cdots + \dfrac {x_{n-1}} {x_n} + \dfrac {x_n} {x_1}\] over real numbers $x_1,x_2,\ldots,x_n \geq 1$ satisfying $|x_k - x_{k+1}| \leq 1$ for all $1\leq k \leq n-1$. Do also determine when the extremal values are achieved. (Dan Schwarz)

2000 Bulgaria National Olympiad, 3

Tags: induction , modular arithmetic , number theory

Let $ p$ be a prime number and let $ a_1,a_2,\ldots,a_{p \minus{} 2}$ be positive integers such that $ p$ doesn't $ a_k$ or $ {a_k}^k \minus{} 1$ for any $ k$. Prove that the product of some of the $ a_i$'s is congruent to $ 2$ modulo $ p$.

PEN J Problems, 11

Tags: function , modular arithmetic , inequalities , induction , floor function , number theory , logarithm

Prove that ${d((n^2 +1)}^2)$ does not become monotonic from any given point onwards.

2014 Contests, 3

Tags: algebra , polynomial , inequalities , induction , trigonometry , calculus , derivative

Find all polynomials $P(x)$ with real coefficients that satisfy \[P(x\sqrt{2})=P(x+\sqrt{1-x^2})\]for all real $x$ with $|x|\le 1$.

2005 All-Russian Olympiad Regional Round, 8.8

Tags: vector , induction , inequalities , combinatorics

8.8, 9.8, 11.8 a) 99 boxes contain apples and oranges. Prove that we can choose 50 boxes in such a way that they contain at least half of all apples and half of all oranges. b) 100 boxes contain apples and oranges. Prove that we can choose 34 boxes in such a way that they contain at least a third of all apples and a third of all oranges. c) 100 boxes contain apples, oranges and bananas. Prove that we can choose 51 boxes in such a way that they contain at least half of all apples, and half of all oranges and half of all bananas. ([i]I. Bogdanov, G. Chelnokov, E. Kulikov[/i])

2010 China Western Mathematical Olympiad, 3

Tags: induction , combinatorics

Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.

2006 Petru Moroșan-Trident, 2

Tags: induction , inequalities , inequality

Let be an increasing, infinite sequence of natural numbers $ \left( a_n \right)_{n\ge 1} . $ [b]a)[/b] Prove that if $ a_n=n, $ for any natural numbers $ n, $ then $$ -2+2\sqrt{1+n} <\frac{1}{\sqrt{a_1}} +\frac{1}{\sqrt{a_2}} +\cdots +\frac{1}{\sqrt{a_n}} <2\sqrt n , $$ for any natural numbers $ n. $ [b]b)[/b] Disprove the converse of [b]a).[/b] [i]Vasile Radu[/i]

2013 IFYM, Sozopol, 3

Tags: induction , relatively prime , number theory

Let $\phi(n)$ be the number of positive integers less than $n$ that are relatively prime to $n$, where $n$ is a positive integer. Find all pairs of positive integers $(m,n)$ such that \[2^n + (n-\phi(n)-1)! = n^m+1.\]

2007 IMO Shortlist, 1

Tags: combinatorics , sequence , inequality system , induction

Let $ n > 1$ be an integer. Find all sequences $ a_1, a_2, \ldots a_{n^2 \plus{} n}$ satisfying the following conditions: \[ \text{ (a) } a_i \in \left\{0,1\right\} \text{ for all } 1 \leq i \leq n^2 \plus{} n; \] \[ \text{ (b) } a_{i \plus{} 1} \plus{} a_{i \plus{} 2} \plus{} \ldots \plus{} a_{i \plus{} n} < a_{i \plus{} n \plus{} 1} \plus{} a_{i \plus{} n \plus{} 2} \plus{} \ldots \plus{} a_{i \plus{} 2n} \text{ for all } 0 \leq i \leq n^2 \minus{} n. \] [i]Author: Dusan Dukic, Serbia[/i]