Olympiad problems

MIPT student olimpiad spring 2024, 4

In some finite set of positive numbers, each number is expressed as a linear combination of the rest with rational non-negative coefficients. Prove that the ratio of some two numbers in the set is rational.

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| $.

2014 USA TSTST, 3

Tags: algebra , polynomial , inequalities , induction , trigonometry , calculus , derivative

Find all polynomials $P(x)$ with real coefficients that satisfy \[P(x\sqrt{2})=P(x+\sqrt{1-x^2})\]for all real $x$ with $|x|\le 1$.

2003 Tournament Of Towns, 2

Tags: induction , number theory

Prove that every positive integer can be represented in the form \[3^{u_1} \ldots 2^{v_1} + 3^{u_2} \ldots 2^{v_2} + \ldots + 3^{u_k} \ldots 2^{v_k}\] with integers $u_1, u_2, \ldots , u_k, v_1, \ldots, v_k$ such that $u_1 > u_2 >\ldots > u_k\ge 0$ and $0 \le v_1 < v_2 <\ldots < v_k$.

2003 India IMO Training Camp, 9

Tags: inequalities , induction , number theory , combinatorics

Let $n$ be a positive integer and $\{A,B,C\}$ a partition of $\{1,2,\ldots,3n\}$ such that $|A|=|B|=|C|=n$. Prove that there exist $x \in A$, $y \in B$, $z \in C$ such that one of $x,y,z$ is the sum of the other two.

2013 NIMO Problems, 4

Tags: induction

Consider a set of $1001$ points in the plane, no three collinear. Compute the minimum number of segments that must be drawn so that among any four points, we can find a triangle. [i]Proposed by Ahaan S. Rungta / Amir Hossein[/i]

2013 India IMO Training Camp, 1

Tags: function , induction , limit , algebra , cauchy equation

Find all functions $f$ from the set of real numbers to itself satisfying \[ f(x(1+y)) = f(x)(1 + f(y)) \] for all real numbers $x, y$.

2009 Costa Rica - Final Round, 2

Tags: induction , number theory

Prove that for that for every positive integer $ n$, the smallest integer that is greater than $ (\sqrt {3} \plus{} 1)^{2n}$ is divisible by $ 2^{n \plus{} 1}$.

2013 Cono Sur Olympiad, 4

Tags: induction , combinatorics

Let $M$ be the set of all integers from $1$ to $2013$. Each subset of $M$ is given one of $k$ available colors, with the only condition that if the union of two different subsets $A$ and $B$ is $M$, then $A$ and $B$ are given different colors. What is the least possible value of $k$?

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. \]

2020 Germany Team Selection Test, 1

Tags: combinatorics , induction , local argument

You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.

2006 Hong kong National Olympiad, 4

Tags: induction , algebra

Let $(a_n)_{n\ge 1}$ be a sequence of positive numbers. If there is a constant $M > 0$ such that $a_2^2 + a_2^2 +\ldots + a_n^2 < Ma_{n+1}^2$ for all $n$, then prove that there is a constant $M ' > 0$ such that $a_1 + a_2 +\ldots + a_n < M ' a_{n+1}$ .

PEN G Problems, 11

Tags: trigonometry , induction , strong induction , irrational number

Show that $\cos 1^{\circ}$ is irrational.

2005 All-Russian Olympiad, 4

Tags: induction , ceiling function , search , combinatorics

Given 365 cards, in which distinct numbers are written. We may ask for any three cards, the order of numbers written in them. Is it always possible to find out the order of all 365 cards by 2000 such questions?

2007 Romania Team Selection Test, 4

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

i) Find all infinite arithmetic progressions formed with positive integers such that there exists a number $N \in \mathbb{N}$, such that for any prime $p$, $p > N$, the $p$-th term of the progression is also prime. ii) Find all polynomials $f(X) \in \mathbb{Z}[X]$, such that there exist $N \in \mathbb{N}$, such that for any prime $p$, $p > N$, $| f(p) |$ is also prime. [i]Dan Schwarz[/i]

1985 IMO Longlists, 54

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

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

2008 China Team Selection Test, 3

Tags: induction , rearrangement inequality , inequalities

Let $ 0 < x_{1}\leq\frac {x_{2}}{2}\leq\cdots\leq\frac {x_{n}}{n}, 0 < y_{n}\leq y_{n \minus{} 1}\leq\cdots\leq y_{1},$ Prove that $ (\sum_{k \equal{} 1}^{n}x_{k}y_{k})^2\leq(\sum_{k \equal{} 1}^{n}y_{k})(\sum_{k \equal{} 1}^{n}(x_{k}^2 \minus{} \frac {1}{4}x_{k}x_{k \minus{} 1})y_{k}).$ where $ x_{0} \equal{} 0.$

2012 Philippine MO, 4

Tags: induction , algebra

Let $\star$ be an operation defined in the set of nonnegative integers with the following properties: for any nonnegative integers $x$ and $y$, (i) $(x + 1)\star 0 = (0\star x) + 1$ (ii) $0\star (y + 1) = (y\star 0) + 1$ (iii) $(x + 1)\star (y + 1) = (x\star y) + 1$. If $123\star 456 = 789$, find $246\star 135$.

2006 Tuymaada Olympiad, 3

Tags: geometry , rectangle , geometric transformation , rotation , induction , vector , absolute value

From a $n\times (n-1)$ rectangle divided into unit squares, we cut the [i]corner[/i], which consists of the first row and the first column. (that is, the corner has $2n-2$ unit squares). For the following, when we say [i]corner[/i] we reffer to the above definition, along with rotations and symmetry. Consider an infinite lattice of unit squares. We will color the squares with $k$ colors, such that for any corner, the squares in that corner are coloured differently (that means that there are no squares coloured with the same colour). Find out the minimum of $k$. [i]Proposed by S. Berlov[/i]

2007 Romania Team Selection Test, 1

Tags: induction , calculus , derivative , logarithm , inequalities

If $a_{1}$, $a_{2}$, $\ldots$, $a_{n}\geq 0$ are such that \[a_{1}^{2}+\cdots+a_{n}^{2}=1,\] then find the maximum value of the product $(1-a_{1})\cdots (1-a_{n})$.

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$.

2023 Romania EGMO TST, P2

Tags: function , pigeonhole principle , induction , modular arithmetic , number theory

Suppose that $f : \mathbb{N} \rightarrow \mathbb{N}$ is a function for which the expression $af(a)+bf(b)+2ab$ for all $a,b \in \mathbb{N}$ is always a perfect square. Prove that $f(a)=a$ for all $a \in \mathbb{N}$.

2002 Finnish National High School Mathematics Competition, 3

Tags: probability , induction , combinatorics

$n$ pairs are formed from $n$ girls and $n$ boys at random. What is the probability of having at least one pair of girls? For which $n$ the probability is over $0,9?$

2023 UMD Math Competition Part II, 2

Tags: combinatorics , induction

Let $n \ge 2$ be an integer. There are $n$ houses in a town. All distances between pairs of houses are different. Every house sends a visitor to the house closest to it. Find all possible values of $n$ (with full justification) for which we can design a town with $n$ houses where every house is visited.

2007 Iran MO (2nd Round), 3

Tags: induction , combinatorics

Farhad has made a machine. When the machine starts, it prints some special numbers. The property of this machine is that for every positive integer $n$, it prints exactly one of the numbers $n,2n,3n$. We know that the machine prints $2$. Prove that it doesn't print $13824$.