Olympiad problems

2008 ITAMO, 3

Find all functions $ f: Z \rightarrow R$ that verify the folowing two conditions: (i) for each pair of integers $ (m,n)$ with $ m<n$ one has $ f(m)<f(n)$; (ii) for each pair of integers $ (m,n)$ there exists an integer $ k$ such that $ f(m)\minus{}f(n)\equal{}f(k)$.

2005 Brazil National Olympiad, 6

Tags: modular arithmetic , induction , greatest common divisor , geometric sequence , number theory

Given positive integers $a,c$ and integer $b$, prove that there exists a positive integer $x$ such that \[ a^x + x \equiv b \pmod c, \] that is, there exists a positive integer $x$ such that $c$ is a divisor of $a^x + x - b$.

1978 USAMO, 3

Tags: induction , algebra , equation , additive number theory

An integer $n$ will be called [i]good[/i] if we can write \[n=a_1+a_2+\cdots+a_k,\] where $a_1,a_2, \ldots, a_k$ are positive integers (not necessarily distinct) satisfying \[\frac{1}{a_1}+\frac{1}{a_2}+\cdots+\frac{1}{a_n}=1.\] Given the information that the integers 33 through 73 are good, prove that every integer $\ge 33$ is good.

2011 Brazil National Olympiad, 4

Tags: number theory , number theory gcd , induction

Do there exist $2011$ positive integers $a_1 < a_2 < \ldots < a_{2011}$ such that $\gcd(a_i,a_j) = a_j - a_i$ for any $i$, $j$ such that $1 \le i < j \le 2011$?

2000 Finnish National High School Mathematics Competition, 3

Tags: inequalities , induction , algebra , logarithm

Determine the positive integers $n$ such that the inequality \[n! > \sqrt{n^n}\] holds.

2015 India IMO Training Camp, 1

Tags: number theory , frobenius , additive combinatorics , additive number theory , additive representation , induction

Let $n \ge 2$ be an integer, and let $A_n$ be the set \[A_n = \{2^n - 2^k\mid k \in \mathbb{Z},\, 0 \le k < n\}.\] Determine the largest positive integer that cannot be written as the sum of one or more (not necessarily distinct) elements of $A_n$ . [i]Proposed by Serbia[/i]

2001 Tournament Of Towns, 6

Tags: induction , combinatorics

Several numbers are written in a row. In each move, Robert chooses any two adjacent numbers in which the one on the left is greater than the one on the right, doubles each of them and then switches them around. Prove that Robert can make only a finite number of moves.

2013 India National Olympiad, 4

Tags: induction , function , floor function , combinatorics

Let $N$ be an integer greater than $1$ and let $T_n$ be the number of non empty subsets $S$ of $\{1,2,.....,n\}$ with the property that the average of the elements of $S$ is an integer.Prove that $T_n - n$ is always even.

2003 Iran MO (3rd Round), 22

Tags: induction , number theory

Let $ a_1\equal{}a_2\equal{}1$ and \[ a_{n\plus{}2}\equal{}\frac{n(n\plus{}1)a_{n\plus{}1}\plus{}n^2a_n\plus{}5}{n\plus{}2}\minus{}2\]for each $ n\in\mathbb N$. Find all $ n$ such that $ a_n\in\mathbb N$.

2006 Iran Team Selection Test, 6

Tags: induction , combinatorics

Let $G$ be a tournoment such that it's edges are colored either red or blue. Prove that there exists a vertex of $G$ like $v$ with the property that, for every other vertex $u$ there is a mono-color directed path from $v$ to $u$.

2013 Korea - Final Round, 6

Tags: induction , combinatorics

For any permutation $ f : \{ 1, 2, \cdots , n \} \to \{1, 2, \cdots , n \} $, and define \[ A = \{ i | i > f(i) \} \] \[ B = \{ (i, j) | i<j \le f(j) < f(i) \ or \ f(j) < f(i) < i < j \} \] \[ C = \{ (i, j) | i<j \le f(i) < f(j) \ or \ f(i) < f(j) < i < j \} \] \[ D = \{ (i, j) | i< j \ and \ f(i) > f(j)\} \] Prove that $ |A| + 2|B| + |C| = |D| $.

2013 USA TSTST, 5

Tags: goofy , ahhhh , induction , combinatorics , number theory

Let $p$ be a prime. Prove that any complete graph with $1000p$ vertices, whose edges are labelled with integers, has a cycle whose sum of labels is divisible by $p$.

1986 IMO Longlists, 64

Tags: induction , number theory

Let $(a_n)_{n\in \mathbb N}$ be the sequence of integers defined recursively by $a_1 = a_2 = 1, a_{n+2} = 7a_{n+1} - a_n - 2$ for $n \geq 1$. Prove that $a_n$ is a perfect square for every $n.$

2003 India Regional Mathematical Olympiad, 2

Tags: induction

If $n$ is an integer greater than $7$, prove that ${n \choose 7} - \left[ \frac{n}{7} \right]$ is divisible by $7$.

1997 IMC, 6

Tags: induction , combinatorics

Suppose $F$ is a family of finite subsets of $\mathbb{N}$ and for any 2 sets $A,B \in F$ we have $A \cap B \not= \O$. (a) Is it true that there is a finite subset $Y$ of $\mathbb{N}$ such that for any $A,B \in F$ we have $A\cap B\cap Y \not= \O$? (b) Is the above true if we assume that all members of $F$ have the same size?

2003 China Western Mathematical Olympiad, 1

Tags: calculus , integration , induction , function , quadratic , algebra

The sequence $ \{a_n\}$ satisfies $ a_0 \equal{} 0, a_{n \plus{} 1} \equal{} ka_n \plus{} \sqrt {(k^2 \minus{} 1)a_n^2 \plus{} 1}, n \equal{} 0, 1, 2, \ldots$, where $ k$ is a fixed positive integer. Prove that all the terms of the sequence are integral and that $ 2k$ divides $ a_{2n}, n \equal{} 0, 1, 2, \ldots$.

2008 AMC 12/AHSME, 15

Tags: induction , modular arithmetic , number theory

Let $ k\equal{}2008^2\plus{}2^{2008}$. What is the units digit of $ k^2\plus{}2^k$? $ \textbf{(A)}\ 0 \qquad \textbf{(B)}\ 2 \qquad \textbf{(C)}\ 4 \qquad \textbf{(D)}\ 6 \qquad \textbf{(E)}\ 8$

2009 APMO, 1

Tags: induction , invariant , combinatorics

Consider the following operation on positive real numbers written on a blackboard: Choose a number $ r$ written on the blackboard, erase that number, and then write a pair of positive real numbers $ a$ and $ b$ satisfying the condition $ 2 r^2 \equal{} ab$ on the board. Assume that you start out with just one positive real number $ r$ on the blackboard, and apply this operation $ k^2 \minus{} 1$ times to end up with $ k^2$ positive real numbers, not necessarily distinct. Show that there exists a number on the board which does not exceed kr.

2011 Croatia Team Selection Test, 1

Tags: modular arithmetic , pigeonhole principle , induction , algebra

We define a sequence $a_n$ so that $a_0=1$ and \[a_{n+1} = \begin{cases} \displaystyle \frac{a_n}2 & \textrm { if } a_n \equiv 0 \pmod 2, \\ a_n + d & \textrm{ otherwise. } \end{cases} \] for all postive integers $n$. Find all positive integers $d$ such that there is some positive integer $i$ for which $a_i=1$.

2007 Singapore MO Open, 5

Tags: number theory , least common multiple , floor function , induction

Find the largest integer $n$ such that $n$ is divisible by all positive integers less than $\sqrt[3]{n}$.

2014 USAMTS Problems, 5:

Tags: induction , asymptote

Let $a_0,a_1,a_2,\dots$ be a sequence of nonnegative integers such that $a_2=5$, $a_{2014}=2015$, and $a_n=a_{a_{n-1}}$ for all positive integers $n$. Find all possible values of $a_{2015}$.

2007 Romania Team Selection Test, 3

Tags: induction , number theory

Find all subsets $A$ of $\left\{ 1, 2, 3, 4, \ldots \right\}$, with $|A| \geq 2$, such that for all $x,y \in A, \, x \neq y$, we have that $\frac{x+y}{\gcd (x,y)}\in A$. [i]Dan Schwarz[/i]

1998 IberoAmerican, 1

Tags: pigeonhole principle , induction , combinatorics

There are representants from $n$ different countries sit around a circular table ($n\geq2$), in such way that if two representants are from the same country, then, their neighbors to the right are not from the same country. Find, for every $n$, the maximal number of people that can be sit around the table.

PEN I Problems, 3

Tags: floor function , induction

Prove that for any positive integer $n$, \[\left\lfloor \frac{n+1}{2}\right\rfloor+\left\lfloor \frac{n+2}{4}\right\rfloor+\left\lfloor \frac{n+4}{8}\right\rfloor+\left\lfloor \frac{n+8}{16}\right\rfloor+\cdots = n.\]

2007 Balkan MO, 3

Tags: algebra , polynomial , floor function , induction , number theory

Find all positive integers $n$ such that there exist a permutation $\sigma$ on the set $\{1,2,3, \ldots, n\}$ for which \[\sqrt{\sigma(1)+\sqrt{\sigma(2)+\sqrt{\ldots+\sqrt{\sigma(n-1)+\sqrt{\sigma(n)}}}}}\] is a rational number.