Olympiad problems

2002 USA Team Selection Test, 2

Let $p>5$ be a prime number. For any integer $x$, define \[{f_p}(x) = \sum_{k=1}^{p-1} \frac{1}{(px+k)^2}\] Prove that for any pair of positive integers $x$, $y$, the numerator of $f_p(x) - f_p(y)$, when written as a fraction in lowest terms, is divisible by $p^3$.

1998 USAMO, 3

Tags: trigonometry , function , inequalities , inequalities proposed , n-variable inequality , Hi

Let $a_0,a_1,\cdots ,a_n$ be numbers from the interval $(0,\pi/2)$ such that \[ \tan (a_0-\frac{\pi}{4})+ \tan (a_1-\frac{\pi}{4})+\cdots +\tan (a_n-\frac{\pi}{4})\geq n-1. \] Prove that \[ \tan a_0\tan a_1 \cdots \tan a_n\geq n^{n+1}. \]

2005 USAMO, 2

Tags: modular arithmetic , algebra proposed , algebra , Diophantine equation , Hi

Prove that the system \begin{align*} x^6+x^3+x^3y+y & = 147^{157} \\ x^3+x^3y+y^2+y+z^9 & = 157^{147} \end{align*} has no solutions in integers $x$, $y$, and $z$.

2013 IMO Shortlist, N2

Tags: number theory , IMO , induction , IMO 2013 , IMO Shortlist , Hi

Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that \[1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\] [i]Proposed by Japan[/i]

2013 Tournament of Towns, 7

Tags: game strategy , game , Hi

On a table, there are $11$ piles of ten stones each. Pete and Basil play the following game. In turns they take $1, 2$ or $3$ stones at a time: Pete takes stones from any single pile while Basil takes stones from different piles but no more than one from each. Pete moves first. The player who cannot move, loses. Which of the players, Pete or Basil, has a winning strategy?

2008 IMO Shortlist, 5

Tags: inequalities , algebra , IMO Shortlist , Hi

Let $ a$, $ b$, $ c$, $ d$ be positive real numbers such that $ abcd \equal{} 1$ and $ a \plus{} b \plus{} c \plus{} d > \dfrac{a}{b} \plus{} \dfrac{b}{c} \plus{} \dfrac{c}{d} \plus{} \dfrac{d}{a}$. Prove that \[ a \plus{} b \plus{} c \plus{} d < \dfrac{b}{a} \plus{} \dfrac{c}{b} \plus{} \dfrac{d}{c} \plus{} \dfrac{a}{d}\] [i]Proposed by Pavel Novotný, Slovakia[/i]

2010 Contests, 2

Tags: inequalities , Hi

Let $a, b, c$ be positive reals such that $abc=1$. Show that \[\frac{1}{a^5(b+2c)^2} + \frac{1}{b^5(c+2a)^2} + \frac{1}{c^5(a+2b)^2} \ge \frac{1}{3}.\]

2011 Brazil Team Selection Test, 3

Tags: inequalities , algebra , polynomial , IMO Shortlist , Hi

Let the real numbers $a,b,c,d$ satisfy the relations $a+b+c+d=6$ and $a^2+b^2+c^2+d^2=12.$ Prove that \[36 \leq 4 \left(a^3+b^3+c^3+d^3\right) - \left(a^4+b^4+c^4+d^4 \right) \leq 48.\] [i]Proposed by Nazar Serdyuk, Ukraine[/i]

2005 IMO Shortlist, 2

Tags: counting , IMO , IMO 2005 , number theory , combinatorics , IMO Shortlist , Hi

Let $a_1,a_2,\ldots$ be a sequence of integers with infinitely many positive and negative terms. Suppose that for every positive integer $n$ the numbers $a_1,a_2,\ldots,a_n$ leave $n$ different remainders upon division by $n$. Prove that every integer occurs exactly once in the sequence $a_1,a_2,\ldots$.

2018 Taiwan TST Round 2, 5

Tags: algebra , inequalities , IMO Shortlist , Hi

An integer $n \geq 3$ is given. We call an $n$-tuple of real numbers $(x_1, x_2, \dots, x_n)$ [i]Shiny[/i] if for each permutation $y_1, y_2, \dots, y_n$ of these numbers, we have $$\sum \limits_{i=1}^{n-1} y_i y_{i+1} = y_1y_2 + y_2y_3 + y_3y_4 + \cdots + y_{n-1}y_n \geq -1.$$ Find the largest constant $K = K(n)$ such that $$\sum \limits_{1 \leq i < j \leq n} x_i x_j \geq K$$ holds for every Shiny $n$-tuple $(x_1, x_2, \dots, x_n)$.

2022 Greece Team Selection Test, 1

Tags: number theory , IMO Shortlist , Divisibility , cubefree , Hi

Find all positive integers $n\geq1$ such that there exists a pair $(a,b)$ of positive integers, such that $a^2+b+3$ is not divisible by the cube of any prime, and $$n=\frac{ab+3b+8}{a^2+b+3}.$$

2020 Azerbaijan IMO TST, 2

Tags: combinatorics , binomial coefficients , IMO Shortlist , IMO Shortlist 2019 , trivial , Hi

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

2012 Brazil Team Selection Test, 2

Tags: combinatorics , IMO Shortlist , Hi , discrete continous

Suppose that $1000$ students are standing in a circle. Prove that there exists an integer $k$ with $100 \leq k \leq 300$ such that in this circle there exists a contiguous group of $2k$ students, for which the first half contains the same number of girls as the second half. [i]Proposed by Gerhard Wöginger, Austria[/i]

2006 Germany Team Selection Test, 3

Tags: combinatorics , rectangle , matrix , counting , graph theory , IMO Shortlist , Hi

Consider a $m\times n$ rectangular board consisting of $mn$ unit squares. Two of its unit squares are called [i]adjacent[/i] if they have a common edge, and a [i]path[/i] is a sequence of unit squares in which any two consecutive squares are adjacent. Two parths are called [i]non-intersecting[/i] if they don't share any common squares. Each unit square of the rectangular board can be colored black or white. We speak of a [i]coloring[/i] of the board if all its $mn$ unit squares are colored. Let $N$ be the number of colorings of the board such that there exists at least one black path from the left edge of the board to its right edge. Let $M$ be the number of colorings of the board for which there exist at least two non-intersecting black paths from the left edge of the board to its right edge. Prove that $N^{2}\geq M\cdot 2^{mn}$.

2020 IMO Shortlist, A4

Tags: inequalities , IMO 2020 , IMO , algebra , IMO Shortlist 2020 , Mount Inquality , Hi

The real numbers $a, b, c, d$ are such that $a\geq b\geq c\geq d>0$ and $a+b+c+d=1$. Prove that \[(a+2b+3c+4d)a^ab^bc^cd^d<1\] [i]Proposed by Stijn Cambie, Belgium[/i]

2010 Iran MO (3rd Round), 6

Tags: number theory proposed , number theory , Hi

$g$ and $n$ are natural numbers such that $gcd(g^2-g,n)=1$ and $A=\{g^i|i \in \mathbb N\}$ and $B=\{x\equiv (n)|x\in A\}$(by $x\equiv (n)$ we mean a number from the set $\{0,1,...,n-1\}$ which is congruent with $x$ modulo $n$). if for $0\le i\le g-1$ $a_i=|[\frac{ni}{g},\frac{n(i+1)}{g})\cap B|$ prove that $g-1|\sum_{i=0}^{g-1}ia_i$.( the symbol $|$ $|$ means the number of elements of the set)($\frac{100}{6}$ points) the exam time was 4 hours

2011 IMO, 5

Tags: function , symmetry , modular arithmetic , number theory , IMO , IMO Shortlist , Hi

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m- n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$. [i]Proposed by Mahyar Sefidgaran, Iran[/i]

2020 Greece Team Selection Test, 3

Tags: combinatorics , binomial coefficients , IMO Shortlist , IMO Shortlist 2019 , trivial , Hi

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

2007 Peru IMO TST, 4

Tags: inequalities , inequalities proposed , Hi

Let $a,b$ and $c$ be sides of a triangle. Prove that: $\frac{\sqrt{b+c-a}}{\sqrt{b}+\sqrt{c}-\sqrt{a}}+\frac{\sqrt{c+a-b}}{\sqrt{c}+\sqrt{a}-\sqrt{b}}+\frac{\sqrt{a+b-c}}{\sqrt{a}+\sqrt{b}-\sqrt{c}}\leq 3$

2004 IMO Shortlist, 4

Tags: algebra , polynomial , functional equation , IMO , IMO 2004 , hojoo lee , Hi

Find all polynomials $f$ with real coefficients such that for all reals $a,b,c$ such that $ab+bc+ca = 0$ we have the following relations \[ f(a-b) + f(b-c) + f(c-a) = 2f(a+b+c). \]

2006 France Team Selection Test, 3

Tags: modular arithmetic , number theory , Divisibility , IMO Shortlist , Chinese Remainder Theorem , Hi

Let $a$, $b$ be positive integers such that $b^n+n$ is a multiple of $a^n+n$ for all positive integers $n$. Prove that $a=b$. [i]Proposed by Mohsen Jamali, Iran[/i]

2011 Cono Sur Olympiad, 6

Tags: combinatorics proposed , combinatorics , Hi

Let $Q$ be a $(2n+1) \times (2n+1)$ board. Some of its cells are colored black in such a way that every $2 \times 2$ board of $Q$ has at most $2$ black cells. Find the maximum amount of black cells that the board may have.

2010 IMO Shortlist, 5

Tags: combinatorics , IMO Shortlist , graph theory , Tournament graphs , vertex degree , Hi

$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players $bad$ if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that \[\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0.\] [i]Proposed by Sung Yun Kim, South Korea[/i]

2017 Taiwan TST Round 1, 1

Tags: IMO Shortlist , inequalities , three variable inequality , Hi , ineqstd

Let $a$, $b$, $c$ be positive real numbers such that $\min(ab,bc,ca) \ge 1$. Prove that $$\sqrt[3]{(a^2+1)(b^2+1)(c^2+1)} \le \left(\frac{a+b+c}{3}\right)^2 + 1.$$ [i]Proposed by Tigran Margaryan, Armenia[/i]

2013 IMO, 1

Tags: number theory , IMO , induction , IMO 2013 , IMO Shortlist , Hi

Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that \[1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\] [i]Proposed by Japan[/i]