Olympiad problems

2006 Romania Team Selection Test, 3

For which pairs of positive integers $(m,n)$ there exists a set $A$ such that for all positive integers $x,y$, if $|x-y|=m$, then at least one of the numbers $x,y$ belongs to the set $A$, and if $|x-y|=n$, then at least one of the numbers $x,y$ does not belong to the set $A$? [i]Adapted by Dan Schwarz from A.M.M.[/i]

2009 Germany Team Selection Test, 2

Tags: induction , prime number , number theory

Let $ \left(a_n \right)_{n \in \mathbb{N}}$ defined by $ a_1 \equal{} 1,$ and $ a_{n \plus{} 1} \equal{} a^4_n \minus{} a^3_n \plus{} 2a^2_n \plus{} 1$ for $ n \geq 1.$ Show that there is an infinite number of primes $ p$ such that none of the $ a_n$ is divisible by $ p.$

2007 USA Team Selection Test, 6

Tags: algebra , polynomial , algorithm , modular arithmetic , counting , distinguishability , induction

For a polynomial $ P(x)$ with integer coefficients, $ r(2i \minus{} 1)$ (for $ i \equal{} 1,2,3,\ldots,512$) is the remainder obtained when $ P(2i \minus{} 1)$ is divided by $ 1024$. The sequence \[ (r(1),r(3),\ldots,r(1023)) \] is called the [i]remainder sequence[/i] of $ P(x)$. A remainder sequence is called [i]complete[/i] if it is a permutation of $ (1,3,5,\ldots,1023)$. Prove that there are no more than $ 2^{35}$ different complete remainder sequences.

2019 Canada National Olympiad, 3

Tags: combinatorics , grid , tiling , checkerboard , induction , bijection

You have a $2m$ by $2n$ grid of squares coloured in the same way as a standard checkerboard. Find the total number of ways to place $mn$ counters on white squares so that each square contains at most one counter and no two counters are in diagonally adjacent white squares.

2013 Romania Team Selection Test, 3

Tags: function , induction , inequalities , algebra

Determine all injective functions defined on the set of positive integers into itself satisfying the following condition: If $S$ is a finite set of positive integers such that $\sum\limits_{s\in S}\frac{1}{s}$ is an integer, then $\sum\limits_{s\in S}\frac{1}{f\left( s\right) }$ is also an integer.

2014 China National Olympiad, 3

Tags: function , induction , algebra

Prove that: there exists only one function $f:\mathbb{N^*}\to\mathbb{N^*}$ satisfying: i) $f(1)=f(2)=1$; ii)$f(n)=f(f(n-1))+f(n-f(n-1))$ for $n\ge 3$. For each integer $m\ge 2$, find the value of $f(2^m)$.

2013 USAMO, 2

Tags: induction

For a positive integer $n\geq 3$ plot $n$ equally spaced points around a circle. Label one of them $A$, and place a marker at $A$. One may move the marker forward in a clockwise direction to either the next point or the point after that. Hence there are a total of $2n$ distinct moves available; two from each point. Let $a_n$ count the number of ways to advance around the circle exactly twice, beginning and ending at $A$, without repeating a move. Prove that $a_{n-1}+a_n=2^n$ for all $n\geq 4$.

1979 AMC 12/AHSME, 14

Tags: induction

In a certain sequence of numbers, the first number is $1$, and, for all $n\ge 2$, the product of the first $n$ numbers in the sequence is $n^2$. The sum of the third and the fifth numbers in the sequence is $\textbf{(A) }\frac{25}{9}\qquad\textbf{(B) }\frac{31}{15}\qquad\textbf{(C) }\frac{61}{16}\qquad\textbf{(D) }\frac{576}{225}\qquad\textbf{(E) }34$

2005 France Team Selection Test, 4

Tags: floor function , ceiling function , induction , inequalities , number theory , logarithm

Let $X$ be a non empty subset of $\mathbb{N} = \{1,2,\ldots \}$. Suppose that for all $x \in X$, $4x \in X$ and $\lfloor \sqrt{x} \rfloor \in X$. Prove that $X=\mathbb{N}$.

1978 IMO Longlists, 45

Tags: induction , inequalities

If $r > s >0$ and $a > b > c$, prove that \[a^rb^s + b^rc^s + c^ra^s \ge a^sb^r + b^sc^r + c^sa^r.\]

1996 USAMO, 4

Tags: induction , function , modular arithmetic , strong induction , combinatorics

An $n$-term sequence $(x_1, x_2, \ldots, x_n)$ in which each term is either 0 or 1 is called a [i]binary sequence of length [/i]$n$. Let $a_n$ be the number of binary sequences of length $n$ containing no three consecutive terms equal to 0, 1, 0 in that order. Let $b_n$ be the number of binary sequences of length $n$ that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that $b_{n+1} = 2a_n$ for all positive integers $n$.

2008 Junior Balkan Team Selection Tests - Romania, 1

Tags: induction , modular arithmetic , number theory , logarithm

Let $ p$ be a prime number, $ p\not \equal{} 3$, and integers $ a,b$ such that $p\mid a+b$ and $ p^2\mid a^3 \plus{} b^3$. Prove that $ p^2\mid a \plus{} b$ or $ p^3\mid a^3 \plus{} b^3$.

2006 QEDMO 2nd, 12

Tags: induction , additive number theory

Let $a_{1}=1$, $a_{2}=2$, $a_{3}$, $a_{4}$, $\cdots$ be the sequence of positive integers of the form $2^{\alpha}3^{\beta}$, where $\alpha$ and $\beta$ are nonnegative integers. Prove that every positive integer is expressible in the form \[a_{i_{1}}+a_{i_{2}}+\cdots+a_{i_{n}},\] where no summand is a multiple of any other.

2012 Centers of Excellency of Suceava, 1

Tags: function , induction , algebra

Function ${{f\colon \mathbb[0, +\infty)}\to\mathbb[0, +\infty)}$ satisfies the condition $f(x)+f(y){\ge}2f(x+y)$ for all $x,y{\ge}0$. Prove that $f(x)+f(y)+f(z){\ge}3f(x+y+z)$ for all $x,y,z{\ge}0$. Mathematical induction? __________________________________ Azerbaijan Land of the Fire :lol:

2008 Iran MO (3rd Round), 1

Tags: induction , number theory

Let $ k>1$ be an integer. Prove that there exists infinitely many natural numbers such as $ n$ such that: \[ n|1^n\plus{}2^n\plus{}\dots\plus{}k^n\]

1995 All-Russian Olympiad Regional Round, 11.6

Tags: induction , algebra

The sequence $ a_n$ satisfies $ a_{m\plus{}n}\plus{} a_{m\minus{}n}\equal{}\frac12(a_{2m}\plus{}a_{2n})$ for all $ m\geq n\geq 0$. If $ a_1\equal{}1$, find $ a_{1995}$.

2014 ELMO Shortlist, 3

Tags: algebra , polynomial , induction , binomial theorem , number theory

Let $t$ and $n$ be fixed integers each at least $2$. Find the largest positive integer $m$ for which there exists a polynomial $P$, of degree $n$ and with rational coefficients, such that the following property holds: exactly one of \[ \frac{P(k)}{t^k} \text{ and } \frac{P(k)}{t^{k+1}} \] is an integer for each $k = 0,1, ..., m$. [i]Proposed by Michael Kural[/i]

2007 China Team Selection Test, 3

Tags: function , induction , combinatorics

Let $ n$ be positive integer, $ A,B\subseteq[0,n]$ are sets of integers satisfying $ \mid A\mid \plus{} \mid B\mid\ge n \plus{} 2.$ Prove that there exist $ a\in A, b\in B$ such that $ a \plus{} b$ is a power of $ 2.$

2014 Online Math Open Problems, 25

Tags: induction , function , integration , calculus , factorial , derivative

If \[ \sum_{n=1}^{\infty}\frac{\frac11 + \frac12 + \dots + \frac 1n}{\binom{n+100}{100}} = \frac pq \] for relatively prime positive integers $p,q$, find $p+q$. [i]Proposed by Michael Kural[/i]

2013 Romanian Master of Mathematics, 5

Tags: floor function , induction , number theory

Given a positive integer $k\geq2$, set $a_1=1$ and, for every integer $n\geq 2$, let $a_n$ be the smallest solution of equation \[x=1+\sum_{i=1}^{n-1}\left\lfloor\sqrt[k]{\frac{x}{a_i}}\right\rfloor\] that exceeds $a_{n-1}$. Prove that all primes are among the terms of the sequence $a_1,a_2,\ldots$

2014 Vietnam Team Selection Test, 1

Tags: induction , algebra

Find all $ f:\mathbb{Z}\rightarrow\mathbb{Z} $ such that \[ f(2m+f(m)+f(m)f(n))=nf(m)+m \] $ \forall m,n\in\mathbb{Z} $

2014 Iran Team Selection Test, 1

Tags: induction , combinatorics

Consider a tree with $n$ vertices, labeled with $1,\ldots,n$ in a way that no label is used twice. We change the labeling in the following way - each time we pick an edge that hasn't been picked before and swap the labels of its endpoints. After performing this action $n-1$ times, we get another tree with its labeling a permutation of the first graph's labeling. Prove that this permutation contains exactly one cycle.

2012 ELMO Shortlist, 9

Tags: algebra , polynomial , function , induction , inequalities

Let $a,b,c$ be distinct positive real numbers, and let $k$ be a positive integer greater than $3$. Show that \[\left\lvert\frac{a^{k+1}(b-c)+b^{k+1}(c-a)+c^{k+1}(a-b)}{a^k(b-c)+b^k(c-a)+c^k(a-b)}\right\rvert\ge \frac{k+1}{3(k-1)}(a+b+c)\] and \[\left\lvert\frac{a^{k+2}(b-c)+b^{k+2}(c-a)+c^{k+2}(a-b)}{a^k(b-c)+b^k(c-a)+c^k(a-b)}\right\rvert\ge \frac{(k+1)(k+2)}{3k(k-1)}(a^2+b^2+c^2).\] [i]Calvin Deng.[/i]

2024 Turkey EGMO TST, 4

Tags: algebra , sequence , inequality , induction

Let $(a_n)_{n=1}^{\infty}$ be a strictly increasing sequence such that inequality $$a_n(a_n-2a_{n-1})+a_{n-1}(a_{n-1}-2a_{n-2})\geq 0$$ holds for all $n \geq 3$. Prove that for all $n\geq2$ the inequality $$a_n \geq a_{n-1}+a_{n-2}+\dots+a_1$$ holds as well.

2008 AMC 10, 24

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$