Olympiad problems

2005 Iran MO (2nd round), 1

Tags: induction , combinatorics

We have a $2\times n$ rectangle. We call each $1\times1$ square a room and we show the room in the $i^{th}$ row and $j^{th}$ column as $(i,j)$. There are some coins in some rooms of the rectangle. If there exist more than $1$ coin in each room, we can delete $2$ coins from it and add $1$ coin to its right adjacent room OR we can delete $2$ coins from it and add $1$ coin to its up adjacent room. Prove that there exists a finite configuration of allowable operations such that we can put a coin in the room $(1,n)$.

2014 Saudi Arabia IMO TST, 3

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

We are given a lattice and two pebbles $A$ and $B$ that are placed at two lattice points. At each step we are allowed to relocate one of the pebbles to another lattice point with the condition that the distance between pebbles is preserved. Is it possible after finite number of steps to switch positions of the pebbles?

2008 IMS, 1

Tags: induction , linear algebra , matrix , algebra , polynomial

Let $ A_1,A_2,\dots,A_n$ be idempotent matrices with real entries. Prove that: \[ \mbox{N}(A_1)\plus{}\mbox{N}(A_2)\plus{}\dots\plus{}\mbox{N}(A_n)\geq \mbox{rank}(I\minus{}A_1A_2\dots A_n)\] $ \mbox{N}(A)$ is $ \mbox{dim}(\mbox{ker(A)})$

2006 Romania Team Selection Test, 2

Tags: induction , combinatorics

Let $m$ and $n$ be positive integers and $S$ be a subset with $(2^m-1)n+1$ elements of the set $\{1,2,3,\ldots, 2^mn\}$. Prove that $S$ contains $m+1$ distinct numbers $a_0,a_1,\ldots, a_m$ such that $a_{k-1} \mid a_{k}$ for all $k=1,2,\ldots, m$.

2010 Contests, 4

Tags: polynomial , induction , strong induction , algebra

Let $p(x)=x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$ be a monic polynomial of degree $n>2$, with real coefficients and all its roots real and different from zero. Prove that for all $k=0,1,2,\cdots,n-2$, at least one of the coefficients $a_k,a_{k+1}$ is different from zero.

2005 Georgia Team Selection Test, 1

Tags: induction , combinatorics

1. The transformation $ n \to 2n \minus{} 1$ or $ n \to 3n \minus{} 1$, where $ n$ is a positive integer, is called the 'change' of $ n$. Numbers $ a$ and $ b$ are called 'similar', if there exists such positive integer, that can be got by finite number of 'changes' from both $ a$ and $ b$. Find all positive integers 'similar' to $ 2005$ and less than $ 2005$.

2014 Peru IMO TST, 16

Tags: induction , combinatorics , additive combinatorics , partition

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

1991 Federal Competition For Advanced Students, 3

Tags: induction , modular arithmetic , quadratic , number theory

Find the number of squares in the sequence given by $ a_0\equal{}91$ and $ a_{n\plus{}1}\equal{}10a_n\plus{}(\minus{}1)^n$ for $ n \ge 0.$

2011 Today's Calculation Of Integral, 752

Tags: calculus , integration , induction , calculus computations

Find $f_n(x)$ such that $f_1(x)=x,\ f_n(x)=\int_0^x tf_{n-1}(x-t)dt\ (n=2,\ 3,\ \cdots).$

2005 All-Russian Olympiad, 4

Tags: induction , ceiling function , search , combinatorics

Given 365 cards, in which distinct numbers are written. We may ask for any three cards, the order of numbers written in them. Is it always possible to find out the order of all 365 cards by 2000 such questions?

2002 Romania Team Selection Test, 4

Tags: induction , combinatorics

At an international conference there are four official languages. Any two participants can speak in one of these languages. Show that at least $60\%$ of the participants can speak the same language. [i]Mihai Baluna[/i]

PEN O Problems, 9

Tags: pigeonhole principle , induction , absolute value

Let $n$ be an integer, and let $X$ be a set of $n+2$ integers each of absolute value at most $n$. Show that there exist three distinct numbers $a, b, c \in X$ such that $c=a+b$.

2011 IMC, 5

Tags: vector , algebra , polynomial , function , abstract algebra , analytic geometry , induction

Let $n$ be a positive integer and let $V$ be a $(2n-1)$-dimensional vector space over the two-element field. Prove that for arbitrary vectors $v_1,\dots,v_{4n-1} \in V,$ there exists a sequence $1\leq i_1<\dots<i_{2n}\leq 4n-1$ of indices such that $v_{i_1}+\dots+v_{i_{2n}}=0.$

2012 Math Prize For Girls Problems, 19

Tags: function , calculus , derivative , induction

Define $L(x) = x - \frac{x^2}{2}$ for every real number $x$. If $n$ is a positive integer, define $a_n$ by \[ a_n = L \Bigl( L \Bigl( L \Bigl( \cdots L \Bigl( \frac{17}{n} \Bigr) \cdots \Bigr) \Bigr) \Bigr), \] where there are $n$ iterations of $L$. For example, \[ a_4 = L \Bigl( L \Bigl( L \Bigl( L \Bigl( \frac{17}{4} \Bigr) \Bigr) \Bigr) \Bigr). \] As $n$ approaches infinity, what value does $n a_n$ approach?

2008 Saint Petersburg Mathematical Olympiad, 4

Tags: induction , inequalities

The numbers $x_1,...x_{100}$ are written on a board so that $ x_1=\frac{1}{2}$ and for every $n$ from $1$ to $99$, $x_{n+1}=1-x_1x_2x_3*...*x_{100}$. Prove that $x_{100}>0.99$.

1998 Poland - First Round, 4

Tags: induction , algebra , polynomial , strong induction

Let $ x,y$ be real numbers such that the numbers $ x\plus{}y, x^2\plus{}y^2, x^3\plus{}y^3$ and $ x^4\plus{}y^4$ are integers. Prove that for all positive integers $ n$, the number $ x^n \plus{} y^n$ is an integer.

2000 Taiwan National Olympiad, 3

Tags: function , induction , algebra

Define a function $f:\mathbb{N}\rightarrow\mathbb{N}_0$ by $f(1)=0$ and \[f(n)=\max_j\{ f(j)+f(n-j)+j\}\quad\forall\, n\ge 2 \] Determine $f(2000)$.

2014 Contests, 1

Tags: induction , inequalities , triangle inequality , algebra , n-variable inequality

Let $a_1,\ldots,a_n$ and $b_1\ldots,b_n$ be $2n$ real numbers. Prove that there exists an integer $k$ with $1\le k\le n$ such that $ \sum_{i=1}^n|a_i-a_k| ~~\le~~ \sum_{i=1}^n|b_i-a_k|.$ (Proposed by Gerhard Woeginger, Austria)

2013 NIMO Summer Contest, 15

Tags: induction , modular arithmetic

\begin{quote} Ted quite likes haikus, \\ poems with five-seven-five, \\ but Ted knows few words. He knows $2n$ words \\ that contain $n$ syllables \\ for every int $n$. Ted can only write \\ $N$ distinct haikus. Find $N$. \\ Take mod one hundred. \end{quote} Ted loves creating haikus (Japanese three-line poems with $5$, $7$, $5$ syllables each), but his vocabulary is rather limited. In particular, for integers $1 \le n \le 7$, he knows $2n$ words with $n$ syllables. Furthermore, words cannot cross between lines, but may be repeated. If Ted can make $N$ distinct haikus, compute the remainder when $N$ is divided by $100$. [i]Proposed by Lewis Chen[/i]

2007 Brazil National Olympiad, 1

Tags: quadratic , induction , algebra , polynomial , limit , quadratic formula

Let $ f(x) \equal{} x^2 \plus{} 2007x \plus{} 1$. Prove that for every positive integer $ n$, the equation $ \underbrace{f(f(\ldots(f}_{n\ {\rm times}}(x))\ldots)) \equal{} 0$ has at least one real solution.

2015 Vietnam National Olympiad, 1

Tags: polynomial , induction , algebra

Let ${\left\{ {f(x)} \right\}}$ be a sequence of polynomial, where ${f_0}(x) = 2$, ${f_1}(x) = 3x$, and ${f_n}(x) = 3x{f_{n - 1}}(x) + (1 - x - 2{x^2}){f_{n - 2}}(x)$ $(n \ge 2)$ Determine the value of $n$ such that ${f_n}(x)$ is divisible by $x^3-x^2+x$.

2005 AMC 12/AHSME, 20

Tags: function , induction

For each $ x$ in $ [0,1]$, define \[ f(x)=\begin{cases}2x, &\text { if } 0 \leq x \leq \frac {1}{2}; \\ 2 - 2x, &\text { if } \frac {1}{2} < x \leq 1. \end{cases} \]Let $ f^{[2]}(x) = f(f(x))$, and $ f^{[n + 1]}(x) = f^{[n]}(f(x))$ for each integer $ n \geq 2$. For how many values of $ x$ in $ [0,1]$ is $ f^{[2005]}(x) = \frac {1}{2}$? $ \textbf{(A)}\ 0 \qquad \textbf{(B)}\ 2005 \qquad \textbf{(C)}\ 4010 \qquad \textbf{(D)}\ 2005^2 \qquad \textbf{(E)}\ 2^{2005}$

2002 China Girls Math Olympiad, 6

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]

2006 China Western Mathematical Olympiad, 4

Tags: induction , combinatorics

Given a positive integer $ n\geq 2$, let $ B_{1}$, $ B_{2}$, ..., $ B_{n}$ denote $ n$ subsets of a set $ X$ such that each $ B_{i}$ contains exactly two elements. Find the minimum value of $ \left|X\right|$ such that for any such choice of subsets $ B_{1}$, $ B_{2}$, ..., $ B_{n}$, there exists a subset $ Y$ of $ X$ such that: (1) $ \left|Y\right| \equal{} n$; (2) $ \left|Y \cap B_{i}\right|\leq 1$ for every $ i\in\left\{1,2,...,n\right\}$.

2009 Tournament Of Towns, 7

Tags: algorithm , induction

At the entrance to a cave is a rotating round table. On top of the table are $n$ identical barrels, evenly spaced along its circumference. Inside each barrel is a herring either with its head up or its head down. In a move, Ali Baba chooses from $1$ to $n$ of the barrels and turns them upside down. Then the table spins around. When it stops, it is impossible to tell which barrels have been turned over. The cave will open if the heads of the herrings in all $n$ barrels are up or are all down. Determine all values of $n$ for which Ali Baba can open the cave in a finite number of moves. [i](11 points)[/i]