Olympiad problems

1977 IMO Longlists, 6

Tags: trigonometry , function , inequalities , induction , algebra

Let $x_1, x_2, \ldots , x_n \ (n \geq 1)$ be real numbers such that $0 \leq x_j \leq \pi, \ j = 1, 2,\ldots, n.$ Prove that if $\sum_{j=1}^n (\cos x_j +1) $ is an odd integer, then $\sum_{j=1}^n \sin x_j \geq 1.$

1991 Federal Competition For Advanced Students, P2, 6

Tags: calculus , induction , number theory

Find the number of ten-digit natural numbers (which do not start with zero) containing no block $ 1991$.

1995 Putnam, 4

Tags: induction , continued fraction

Evaluate : \[ \sqrt[8]{2207-\frac{1}{2207-\frac{1}{2207-\cdots}}} \] Express your expression in the form $\frac{a+b\sqrt{c}}{d}$ where $a,b,c,d\in \Bbb{Z}$.

2009 Putnam, A3

Tags: linear algebra , matrix , trigonometry , limit , induction , function

Let $ d_n$ be the determinant of the $ n\times n$ matrix whose entries, from left to right and then from top to bottom, are $ \cos 1,\cos 2,\dots,\cos n^2.$ (For example, $ d_3 \equal{} \begin{vmatrix}\cos 1 & \cos2 & \cos3 \\ \cos4 & \cos5 & \cos 6 \\ \cos7 & \cos8 & \cos 9\end{vmatrix}.$ The argument of $ \cos$ is always in radians, not degrees.) Evaluate $ \lim_{n\to\infty}d_n.$

2014 Iran MO (3rd Round), 2

Tags: function , induction , algebra

Find all continuous function $f:\mathbb{R}^{\geq 0}\rightarrow \mathbb{R}^{\geq 0}$ such that : \[f(xf(y))+f(f(y)) = f(x)f(y)+2 \: \: \forall x,y\in \mathbb{R}^{\geq 0}\] [i]Proposed by Mohammad Ahmadi[/i]

2002 Iran Team Selection Test, 12

Tags: quadratic , induction , group theory , combinatorics

We call a permutation $ \left(a_1, a_2, ..., a_n\right)$ of $ \left(1, 2, ..., n\right)$ [i]quadratic[/i] if there exists at least a perfect square among the numbers $ a_1$, $ a_1 \plus{} a_2$, $ ...$, $ a_1 \plus{} a_2 \plus{} ... \plus{} a_n$. Find all natural numbers $ n$ such that all permutations in $ S_n$ are quadratic. [i]Remark.[/i] $ S_{n}$ denotes the $ n$-th symmetric group, the group of permutations on $ n$ elements.

2001 USA Team Selection Test, 4

Tags: modular arithmetic , induction , pigeonhole principle , combinatorics

There are 51 senators in a senate. The senate needs to be divided into $n$ committees so that each senator is on one committee. Each senator hates exactly three other senators. (If senator A hates senator B, then senator B does [i]not[/i] necessarily hate senator A.) Find the smallest $n$ such that it is always possible to arrange the committees so that no senator hates another senator on his or her committee.

2008 Germany Team Selection Test, 1

Tags: induction , algebra

A sequence $ (S_n), n \geq 1$ of sets of natural numbers with $ S_1 = \{1\}, S_2 = \{2\}$ and \[{ S_{n + 1} = \{k \in }\mathbb{N}|k - 1 \in S_n \text{ XOR } k \in S_{n - 1}\}. \] Determine $ S_{1024}.$

2013 ELMO Problems, 6

Tags: function , induction , algebra , 3n-3 theorem , continuity

Consider a function $f: \mathbb Z \to \mathbb Z$ such that for every integer $n \ge 0$, there are at most $0.001n^2$ pairs of integers $(x,y)$ for which $f(x+y) \neq f(x)+f(y)$ and $\max\{ \lvert x \rvert, \lvert y \rvert \} \le n$. Is it possible that for some integer $n \ge 0$, there are more than $n$ integers $a$ such that $f(a) \neq a \cdot f(1)$ and $\lvert a \rvert \le n$? [i]Proposed by David Yang[/i]

1987 Romania Team Selection Test, 10

Tags: modular arithmetic , induction , function , algebra , polynomial , number theory

Let $a,b,c$ be integer numbers such that $(a+b+c) \mid (a^{2}+b^{2}+c^{2})$. Show that there exist infinitely many positive integers $n$ such that $(a+b+c) \mid (a^{n}+b^{n}+c^{n})$. [i]Laurentiu Panaitopol[/i]

2013 Romania National Olympiad, 1

Tags: induction , arithmetic sequence , algebra

A series of numbers is called complete if it has non-zero natural terms and any nonzero integer has at least one among multiple series. Show that the arithmetic progression is a complete sequence if and only if it divides the first term relationship.

2004 239 Open Mathematical Olympiad, 7

Tags: induction , combinatorics

$200n$ diagonals are drawn in a convex $n$-gon. Prove that one of them intersects at least 10000 others. [b]proposed by D. Karpov, S. Berlov[/b]

2010 District Olympiad, 4

Tags: function , induction , algebra

Determine all the functions $ f: \mathbb{N}\rightarrow \mathbb{N}$ such that \[ f(n)\plus{}f(n\plus{}1)\plus{}f(f(n))\equal{}3n\plus{}1, \quad \forall n\in \mathbb{N}.\]

2008 AIME Problems, 6

Tags: induction , ratio , factorial

The sequence $ \{a_n\}$ is defined by \[ a_0 \equal{} 1,a_1 \equal{} 1, \text{ and } a_n \equal{} a_{n \minus{} 1} \plus{} \frac {a_{n \minus{} 1}^2}{a_{n \minus{} 2}}\text{ for }n\ge2. \]The sequence $ \{b_n\}$ is defined by \[ b_0 \equal{} 1,b_1 \equal{} 3, \text{ and } b_n \equal{} b_{n \minus{} 1} \plus{} \frac {b_{n \minus{} 1}^2}{b_{n \minus{} 2}}\text{ for }n\ge2. \]Find $ \frac {b_{32}}{a_{32}}$.

2010 Bulgaria National Olympiad, 2

Tags: function , floor function , induction , algebra

Let $f: \mathbb N \to \mathbb N$ be a function such that $f(1)=1$ and \[f(n)=n - f(f(n-1)), \quad \forall n \geq 2.\] Prove that $f(n+f(n))=n $ for each positive integer $n.$

2000 Italy TST, 3

Tags: induction , algebra

Given positive numbers $a_1$ and $b_1$, consider the sequences defined by \[a_{n+1}=a_n+\frac{1}{b_n},\quad b_{n+1}=b_n+\frac{1}{a_n}\quad (n \ge 1)\] Prove that $a_{25}+b_{25} \geq 10\sqrt{2}$.

2009 Dutch IMO TST, 1

Tags: induction , number theory , easy

For a positive integer $n$ let $S(n)$ be the sum of digits in the decimal representation of $n$. Any positive integer obtained by removing several (at least one) digits from the right-hand end of the decimal representation of $n$ is called a [i]stump[/i] of $n$. Let $T(n)$ be the sum of all stumps of $n$. Prove that $n=S(n)+9T(n)$.

2008 Harvard-MIT Mathematics Tournament, 5

Tags: induction

Let $ S$ be the smallest subset of the integers with the property that $ 0\in S$ and for any $ x\in S$, we have $ 3x\in S$ and $ 3x \plus{} 1\in S$. Determine the number of non-negative integers in $ S$ less than $ 2008$.

2010 USA Team Selection Test, 8

Tags: induction , algebra , polynomial , combinatorics

Let $m,n$ be positive integers with $m \geq n$, and let $S$ be the set of all $n$-term sequences of positive integers $(a_1, a_2, \ldots a_n)$ such that $a_1 + a_2 + \cdots + a_n = m$. Show that \[\sum_S 1^{a_1} 2^{a_2} \cdots n^{a_n} = {n \choose n} n^m - {n \choose n-1} (n-1)^m + \cdots + (-1)^{n-2} {n \choose 2} 2^m + (-1)^{n-1} {n \choose 1}.\]

2010 Indonesia TST, 1

Tags: geometry , trigonometry , algebra , polynomial , induction , function , ratio

Is there a triangle with angles in ratio of $ 1: 2: 4$ and the length of its sides are integers with at least one of them is a prime number? [i]Nanang Susyanto, Jogjakarta[/i]

1970 Miklós Schweitzer, 12

Tags: probability , parameterization , induction , algebra , polynomial , probability and stats

Let $ \vartheta_1,...,\vartheta_n$ be independent, uniformly distributed, random variables in the unit interval $ [0,1]$. Define \[ h(x)\equal{} \frac1n \# \{k: \; \vartheta_k<x\ \}.\] Prove that the probability that there is an $ x_0 \in (0,1)$ such that $ h(x_0)\equal{}x_0$, is equal to $ 1\minus{} \frac1n.$ [i]G. Tusnady[/i]

2008 All-Russian Olympiad, 8

Tags: induction , symmetry , modular arithmetic , combinatorial geometry , combinatorics

In a chess tournament $ 2n\plus{}3$ players take part. Every two play exactly one match. The schedule is such that no two matches are played at the same time, and each player, after taking part in a match, is free in at least $ n$ next (consecutive) matches. Prove that one of the players who play in the opening match will also play in the closing match.

2009 China Team Selection Test, 3

Tags: induction , inequalities

Let $ x_{1},x_{2},\cdots,x_{m},y_{1},y_{2},\cdots,y_{n}$ be positive real numbers. Denote by $ X \equal{} \sum_{i \equal{} 1}^{m}x,Y \equal{} \sum_{j \equal{} 1}^{n}y.$ Prove that $ 2XY\sum_{i \equal{} 1}^{m}\sum_{j \equal{} 1}^{n}|x_{i} \minus{} y_{j}|\ge X^2\sum_{j \equal{} 1}^{n}\sum_{l \equal{} 1}^{n}|y_{i} \minus{} y_{l}| \plus{} Y^2\sum_{i \equal{} 1}^{m}\sum_{k \equal{} 1}^{m}|x_{i} \minus{} x_{k}|$

2021 Princeton University Math Competition, B2

Tags: number theory , induction

Let $p$ be an odd prime. Prove that for every integer $k$, there exist integers $a, b$ such that $p|a^2 + b^2 - k$.

2003 China Girls Math Olympiad, 5

Tags: inequalities , function , induction , algebra

Let $ \{a_n\}^{\infty}_1$ be a sequence of real numbers such that $ a_1 \equal{} 2,$ and \[ a_{n\plus{}1} \equal{} a^2_n \minus{} a_n \plus{} 1, \forall n \in \mathbb{N}.\] Prove that \[ 1 \minus{} \frac{1}{2003^{2003}} < \sum^{2003}_{i\equal{}1} \frac{1}{a_i} < 1.\]