Olympiad problems

2007 IMC, 4

Tags: induction , function

Let $ G$ be a finite group. For arbitrary sets $ U, V, W \subset G$, denote by $ N_{UVW}$ the number of triples $ (x, y, z) \in U \times V \times W$ for which $ xyz$ is the unity . Suppose that $ G$ is partitioned into three sets $ A, B$ and $ C$ (i.e. sets $ A, B, C$ are pairwise disjoint and $ G = A \cup B \cup C$). Prove that $ N_{ABC}= N_{CBA}.$

2013 India IMO Training Camp, 1

Tags: function , induction , limit , algebra , cauchy equation

Find all functions $f$ from the set of real numbers to itself satisfying \[ f(x(1+y)) = f(x)(1 + f(y)) \] for all real numbers $x, y$.

2013 AIME Problems, 14

Tags: induction , modular arithmetic , number theory , pattern finding

For positive integers $n$ and $k$, let $f(n,k)$ be the remainder when $n$ is divided by $k$, and for $n>1$ let $F(n) = \displaystyle\max_{1 \le k \le \frac{n}{2}} f(n,k)$. Find the remainder when $\displaystyle\sum_{n=20}^{100} F(n)$ is divided by $1000$.

1966 IMO Longlists, 61

Tags: trigonometry , induction , algebra , trigonometric identities

Prove that for every natural number $n$, and for every real number $x \neq \frac{k\pi}{2^t}$ ($t=0,1, \dots, n$; $k$ any integer) \[ \frac{1}{\sin{2x}}+\frac{1}{\sin{4x}}+\dots+\frac{1}{\sin{2^nx}}=\cot{x}-\cot{2^nx} \]

2011 China Girls Math Olympiad, 7

Tags: chip-firing , algorithm , induction , abstract algebra , combinatorics

There are $n$ boxes ${B_1},{B_2},\ldots,{B_n}$ from left to right, and there are $n$ balls in these boxes. If there is at least $1$ ball in ${B_1}$, we can move one to ${B_2}$. If there is at least $1$ ball in ${B_n}$, we can move one to ${B_{n - 1}}$. If there are at least $2$ balls in ${B_k}$, $2 \leq k \leq n - 1$ we can move one to ${B_{k - 1}}$, and one to ${B_{k + 1}}$. Prove that, for any arrangement of the $n$ balls, we can achieve that each box has one ball in it.

2005 All-Russian Olympiad Regional Round, 10.4

Tags: induction , combinatorics

10.4, 11.3 Given $N\geq 3$ points enumerated with 1, 2, ..., $N$. Each two numbers are connected by mean of arrow from a lesser number to a greater one. A coloring of all arrows into red and blue is called [i]monochromatic[/i] iff for any numbers $A$ and $B$ there are [color=red]no[/color] two monochromatic paths from $A$ to $B$ of different colors. Find the number of monochromatic colorings. ([i]I. Bogdanov, G. Chelnokov[/i])

2013 China Western Mathematical Olympiad, 2

Tags: induction , inequalities

Let the integer $n \ge 2$, and the real numbers $x_1,x_2,\cdots,x_n\in \left[0,1\right] $.Prove that\[\sum_{1\le k<j\le n} kx_kx_j\le \frac{n-1}{3}\sum_{k=1}^n kx_k.\]

PEN B Problems, 5

Tags: modular arithmetic , algebra , polynomial , vieta , symmetry , search , induction

Let $p$ be an odd prime. If $g_{1}, \cdots, g_{\phi(p-1)}$ are the primitive roots $\pmod{p}$ in the range $1<g \le p-1$, prove that \[\sum_{i=1}^{\phi(p-1)}g_{i}\equiv \mu(p-1) \pmod{p}.\]

2001 China Western Mathematical Olympiad, 1

Tags: induction , integration , algebra

The sequence $ \{x_n\}$ satisfies $ x_1 \equal{} \frac {1}{2}, x_{n \plus{} 1} \equal{} x_n \plus{} \frac {x_n^2}{n^2}$. Prove that $ x_{2001} < 1001$.

2013 Mediterranean Mathematics Olympiad, 2

Tags: induction , combinatorics

Determine the least integer $k$ for which the following story could hold true: In a chess tournament with $24$ players, every pair of players plays at least $2$ and at most $k$ games against each other. At the end of the tournament, it turns out that every player has played a different number of games.

2013 Baltic Way, 18

Tags: induction , inequalities , number theory

Find all pairs $(x,y)$ of integers such that $y^3-1=x^4+x^2$.

2004 Junior Balkan Team Selection Tests - Romania, 3

Tags: induction , number theory

Let $A$ be a set of positive integers such that a) if $a\in A$, the all the positive divisors of $a$ are also in $A$; b) if $a,b\in A$, with $1<a<b$, then $1+ab \in A$. Prove that if $A$ has at least 3 elements, then $A$ is the set of all positive integers.

2005 Pan African, 3

Tags: function , induction

Let $f: \mathbb{Z} \rightarrow \mathbb{Z}$ be a function such that: For all $a$ and $b$ in $\mathbb{Z} - \{0\}$, $f(ab) \geq f(a) + f(b)$. Show that for all $a \in \mathbb{Z} - \{0\}$ we have $f(a^n) = nf(a)$ for all $n \in \mathbb{N}$ if and only if $f(a^2) = 2f(a)$

1987 USAMO, 3

Tags: polynomial , induction , algebra

Construct a set $S$ of polynomials inductively by the rules: (i) $x\in S$; (ii) if $f(x)\in S$, then $xf(x)\in S$ and $x+(1-x)f(x)\in S$. Prove that there are no two distinct polynomials in $S$ whose graphs intersect within the region $\{0 < x < 1\}$.

2008 Iran MO (3rd Round), 3

Tags: function , induction , combinatorics

Prove that for each $ n$: \[ \sum_{k\equal{}1}^n\binom{n\plus{}k\minus{}1}{2k\minus{}1}\equal{}F_{2n}\]

2000 Putnam, 4

Tags: function , trigonometry , induction

Let $f(x)$ be a continuous function such that $f(2x^2-1)=2xf(x)$ for all $x$. Show that $f(x)=0$ for $-1\le x \le 1$.

1999 All-Russian Olympiad, 2

Tags: induction , function , combinatorics

Each rational point on a real line is assigned an integer. Prove that there is a segment such that the sum of the numbers at its endpoints does not exceed twice the number at its midpoint.

2014 ELMO Shortlist, 2

Tags: geometry , induction , combinatorics

A $2^{2014} + 1$ by $2^{2014} + 1$ grid has some black squares filled. The filled black squares form one or more snakes on the plane, each of whose heads splits at some points but never comes back together. In other words, for every positive integer $n$ greater than $2$, there do not exist pairwise distinct black squares $s_1$, $s_2$, \dots, $s_n$ such that $s_i$ and $s_{i+1}$ share an edge for $i=1,2, \dots, n$ (here $s_{n+1}=s_1$). What is the maximum possible number of filled black squares? [i]Proposed by David Yang[/i]

2009 China Team Selection Test, 2

Tags: induction , ratio , inequalities

Given an integer $ n\ge 2$, find the maximal constant $ \lambda (n)$ having the following property: if a sequence of real numbers $ a_{0},a_{1},a_{2},\cdots,a_{n}$ satisfies $ 0 \equal{} a_{0}\le a_{1}\le a_{2}\le \cdots\le a_{n},$ and $ a_{i}\ge\frac {1}{2}(a_{i \plus{} 1} \plus{} a_{i \minus{} 1}),i \equal{} 1,2,\cdots,n \minus{} 1,$ then $ (\sum_{i \equal{} 1}^n{ia_{i}})^2\ge \lambda (n)\sum_{i \equal{} 1}^n{a_{i}^2}.$

2003 India IMO Training Camp, 9

Tags: inequalities , induction , number theory , combinatorics

Let $n$ be a positive integer and $\{A,B,C\}$ a partition of $\{1,2,\ldots,3n\}$ such that $|A|=|B|=|C|=n$. Prove that there exist $x \in A$, $y \in B$, $z \in C$ such that one of $x,y,z$ is the sum of the other two.

2006 Iran Team Selection Test, 4

Tags: induction , function , triangle inequality , inequalities

Let $x_1,x_2,\ldots,x_n$ be real numbers. Prove that \[ \sum_{i,j=1}^n |x_i+x_j|\geq n\sum_{i=1}^n |x_i| \]

2013 ELMO Shortlist, 7

Tags: function , induction , algebra , 3n-3 theorem , continuity

Consider a function $f: \mathbb Z \to \mathbb Z$ such that for every integer $n \ge 0$, there are at most $0.001n^2$ pairs of integers $(x,y)$ for which $f(x+y) \neq f(x)+f(y)$ and $\max\{ \lvert x \rvert, \lvert y \rvert \} \le n$. Is it possible that for some integer $n \ge 0$, there are more than $n$ integers $a$ such that $f(a) \neq a \cdot f(1)$ and $\lvert a \rvert \le n$? [i]Proposed by David Yang[/i]

2010 Albania Team Selection Test, 2

Tags: function , induction , domain , functional equation , algebra

Find all the continuous functions $f : \mathbb{R} \mapsto\mathbb{R}$ such that $\forall x,y \in \mathbb{R}$, $(1+f(x)f(y))f(x+y)=f(x)+f(y)$.

2009 Argentina Team Selection Test, 1

Tags: induction , pigeonhole principle , combinatorics

On a $ 50 \times 50$ board, the centers of several unit squares are colored black. Find the maximum number of centers that can be colored black in such a way that no three black points form a right-angled triangle.

2013 China Team Selection Test, 1

Tags: analytic geometry , induction , floor function , combinatorics

For a positive integer $k\ge 2$ define $\mathcal{T}_k=\{(x,y)\mid x,y=0,1,\ldots, k-1\}$ to be a collection of $k^2$ lattice points on the cartesian coordinate plane. Let $d_1(k)>d_2(k)>\cdots$ be the decreasing sequence of the distinct distances between any two points in $T_k$. Suppose $S_i(k)$ be the number of distances equal to $d_i(k)$. Prove that for any three positive integers $m>n>i$ we have $S_i(m)=S_i(n)$.