Olympiad problems

1980 IMO Longlists, 20

Let $S$ be a set of 1980 points in the plane such that the distance between every pair of them is at least 1. Prove that $S$ has a subset of 220 points such that the distance between every pair of them is at least $\sqrt{3}.$

2007 Junior Balkan Team Selection Tests - Romania, 3

Tags: modular arithmetic , induction , combinatorics

Consider a $n$x$n$ table such that the unit squares are colored arbitrary in black and white, such that exactly three of the squares placed in the corners of the table are white, and the other one is black. Prove that there exists a $2$x$2$ square which contains an odd number of unit squares white colored.

2003 Bulgaria Team Selection Test, 3

Tags: induction , combinatorial geometry , combinatorics

Some of the vertices of a convex $n$-gon are connected by segments, such that any two of them have no common interior point. Prove that, for any $n$ points in general position, there exists a one-to-one correspondence between the points and the vertices of the $n$ gon, such that any two segments between the points, corresponding to the respective segments from the $n$ gon, have no common interior point.

2008 District Olympiad, 2

Tags: induction

Let $ S\equal{}\{1,2,\ldots,n\}$ be a set, where $ n\geq 6$ is an integer. Prove that $ S$ is the reunion of 3 pairwise disjoint subsets, with the same number of elements and the same sum of their elements, if and only if $ n$ is a multiple of 3.

2011 Turkey Team Selection Test, 1

Tags: function , algorithm , induction , number theory , euclidean algorithm , algebra , functional equation

Let $\mathbb{Q^+}$ denote the set of positive rational numbers. Determine all functions $f: \mathbb{Q^+} \to \mathbb{Q^+}$ that satisfy the conditions \[ f \left( \frac{x}{x+1}\right) = \frac{f(x)}{x+1} \qquad \text{and} \qquad f \left(\frac{1}{x}\right)=\frac{f(x)}{x^3}\] for all $x \in \mathbb{Q^+}.$

2011 ELMO Shortlist, 3

Tags: induction , complex number , imaginary numbers , algebra

Let $N$ be a positive integer. Define a sequence $a_0,a_1,\ldots$ by $a_0=0$, $a_1=1$, and $a_{n+1}+a_{n-1}=a_n(2-1/N)$ for $n\ge1$. Prove that $a_n<\sqrt{N+1}$ for all $n$. [i]Evan O'Dorney.[/i]

1997 USAMO, 6

Tags: floor function , induction , inequalities , algorithm , algebra

Suppose the sequence of nonnegative integers $a_1, a_2, \ldots, a_{1997}$ satisfies \[ a_i + a_j \leq a_{i+j} \leq a_i + a_j + 1 \] for all $i,j \geq 1$ with $i + j \leq 1997$. Show that there exists a real number $x$ such that $a_n = \lfloor nx \rfloor$ (the greatest integer $\leq nx$) for all $1 \leq n \leq 1997$.

1966 IMO Shortlist, 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} \]

1990 IMO Longlists, 73

Tags: function , induction , algebra

Let $\mathbb Q$ be the set of all rational numbers and $\mathbb R$ be the set of real numbers. Function $f: \mathbb Q \to \mathbb R$ satisfies the following conditions: (i) $f(0) = 0$, and for any nonzero $a \in Q, f(a) > 0.$ (ii) $f(x + y) = f(x)f(y) \qquad \forall x,y \in \mathbb Q.$ (iii) $f(x + y) \leq \max\{f(x), f(y)\} \qquad \forall x,y \in \mathbb Q , x,y \neq 0.$ Let $x$ be an integer and $f(x) \neq 1$. Prove that $f(1 + x + x^2+ \cdots + x^n) = 1$ for any positive integer $n.$

1998 China Team Selection Test, 3

Tags: induction , number theory

For any $h = 2^{r}$ ($r$ is a non-negative integer), find all $k \in \mathbb{N}$ which satisfy the following condition: There exists an odd natural number $m > 1$ and $n \in \mathbb{N}$, such that $k \mid m^{h} - 1, m \mid n^{\frac{m^{h}-1}{k}} + 1$.

2006 Putnam, B4

Tags: analytic geometry , vector , induction , linear algebra

Let $Z$ denote the set of points in $\mathbb{R}^{n}$ whose coordinates are $0$ or $1.$ (Thus $Z$ has $2^{n}$ elements, which are the vertices of a unit hypercube in $\mathbb{R}^{n}$.) Given a vector subspace $V$ of $\mathbb{R}^{n},$ let $Z(V)$ denote the number of members of $Z$ that lie in $V.$ Let $k$ be given, $0\le k\le n.$ Find the maximum, over all vector subspaces $V\subseteq\mathbb{R}^{n}$ of dimension $k,$ of the number of points in $V\cap Z.$

1997 IMO, 4

Tags: matrix , combinatorics , coloring , induction

An $ n \times n$ matrix whose entries come from the set $ S \equal{} \{1, 2, \ldots , 2n \minus{} 1\}$ is called a [i]silver matrix[/i] if, for each $ i \equal{} 1, 2, \ldots , n$, the $ i$-th row and the $ i$-th column together contain all elements of $ S$. Show that: (a) there is no silver matrix for $ n \equal{} 1997$; (b) silver matrices exist for infinitely many values of $ n$.

2001 District Olympiad, 4

Tags: limit , induction , inequalities , real analysis

Prove that: a) the sequence $a_n=\frac{1}{n+1}+\frac{1}{n+2}+\ldots+\frac{1}{n+n},\ n\ge 1$ is monotonic. b) there is a sequence $(a_n)_{n\ge 1}\in \{0,1\}$ such that: \[\lim_{n\to \infty} \left(\frac{a_1}{n+1}+\frac{a_2}{n+2}+\ldots +\frac{a_n}{n+n}\right)=\frac{1}{2}\] [i]Radu Gologan[/i]

2007 China Team Selection Test, 1

Tags: function , induction , algebra

Find all functions $ f: \mathbb{Q}^{\plus{}} \mapsto \mathbb{Q}^{\plus{}}$ such that: \[ f(x) \plus{} f(y) \plus{} 2xy f(xy) \equal{} \frac {f(xy)}{f(x\plus{}y)}.\]

2019 Pan-African, 1

Tags: linear recurrence , recurrence relation , algebra , induction

Let $(a_n)_{n=0}^{\infty}$ be a sequence of real numbers defined as follows: [list] [*] $a_0 = 3$, $a_1 = 2$, and $a_2 = 12$; and [*] $2a_{n + 3} - a_{n + 2} - 8a_{n + 1} + 4a_n = 0$ for $n \geq 0$. [/list] Show that $a_n$ is always a strictly positive integer.

1994 Irish Math Olympiad, 3

Tags: polynomial , induction , algebra

Find all real polynomials $ f(x)$ satisfying $ f(x^2)\equal{}f(x)f(x\minus{}1)$ for all $ x$.

2004 Italy TST, 3

Tags: function , quadratic , algorithm , induction , floor function , algebra

Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all $m,n\in\mathbb{N}$, \[(2^m+1)f(n)f(2^mn)=2^mf(n)^2+f(2^mn)^2+(2^m-1)^2n. \]

1984 IMO Longlists, 38

Tags: function , induction , quadratic , domain , algebra

Determine all continuous functions $f: \mathbb R \to \mathbb R$ such that \[f(x + y)f(x - y) = (f(x)f(y))^2, \quad \forall(x, y) \in\mathbb{R}^2.\]

2006 Korea - Final Round, 3

Tags: induction , number theory

A positive integer $N$ is said to be $n-$ good if (i) $N$ has at least $n$ distinct prime divisors, and (ii) there exist distinct positive divisors $1, x_{2}, . . . , x_{n}$ whose sum is $N$ . Show that there exists an $n-$ good number for each $n\geq 6$.

2004 Greece National Olympiad, 2

Tags: induction , algebra

If $m\geq 2$ show that there does not exist positive integers $x_1, x_2, ..., x_m,$ such that \[x_1< x_2<...< x_m \ \ \text{and} \ \ \frac{1}{x_1^3}+\frac{1}{x_2^3}+...+\frac{1}{x_m^3}=1.\]

2006 Mathematics for Its Sake, 2

Tags: linear algebra , linear algebra equation , matrix equation , induction , matrix

Let be a natural number $ n. $ Solve in the set of $ 2\times 2 $ complex matrices the equation $$ \begin{pmatrix} -2& 2007\\ 0&-2 \end{pmatrix} =X^{3n}-3X^n. $$ [i]Petru Vlad[/i]

2005 Korea National Olympiad, 4

Tags: function , induction , calculus , derivative , functional equation , algebra

Find all $f: \mathbb R \to\mathbb R$ such that for all real numbers $x$, $f(x) \geq 0$ and for all real numbers $x$ and $y$, \[ f(x+y)+f(x-y)-2f(x)-2y^2=0. \]

1985 IMO Longlists, 54

Tags: number theory , greatest common divisor , induction , algorithm , modular arithmetic , algebra , binomial theorem

Set $S_n = \sum_{p=1}^n (p^5+p^7)$. Determine the greatest common divisor of $S_n$ and $S_{3n}.$

1987 IMO Longlists, 45

Tags: induction , geometry

Let us consider a variable polygon with $2n$ sides ($n \in N$) in a fixed circle such that $2n - 1$ of its sides pass through $2n - 1$ fixed points lying on a straight line $\Delta$. Prove that the last side also passes through a fixed point lying on $\Delta .$

2003 Iran MO (3rd Round), 29

Tags: polynomial , induction , algebra

Let $ c\in\mathbb C$ and $ A_c \equal{} \{p\in \mathbb C[z]|p(z^2 \plus{} c) \equal{} p(z)^2 \plus{} c\}$. a) Prove that for each $ c\in C$, $ A_c$ is infinite. b) Prove that if $ p\in A_1$, and $ p(z_0) \equal{} 0$, then $ |z_0| < 1.7$. c) Prove that each element of $ A_c$ is odd or even. Let $ f_c \equal{} z^2 \plus{} c\in \mathbb C[z]$. We see easily that $ B_c: \equal{} \{z,f_c(z),f_c(f_c(z)),\dots\}$ is a subset of $ A_c$. Prove that in the following cases $ A_c \equal{} B_c$. d) $ |c| > 2$. e) $ c\in \mathbb Q\backslash\mathbb Z$. f) $ c$ is a non-algebraic number g) $ c$ is a real number and $ c\not\in [ \minus{} 2,\frac14]$.