Olympiad problems

2005 Taiwan TST Round 2, 2

Starting from a positive integer $n$, we can replace the current number with a multiple of the current number or by deleting one or more zeroes from the decimal representation of the current number. Prove that for all values of $n$, it is possible to obtain a single-digit number by applying the above algorithm a finite number of times. There is a nice solution to this...

2014 India IMO Training Camp, 1

Tags: binomial theorem , pigeonhole principle , algebra

Prove that in any set of $2000$ distinct real numbers there exist two pairs $a>b$ and $c>d$ with $a \neq c$ or $b \neq d $, such that \[ \left| \frac{a-b}{c-d} - 1 \right|< \frac{1}{100000}. \]

1997 Moldova Team Selection Test, 3

Tags: pigeonhole principle , decimal representation , divisibility , multiple , digit , number theory

Prove that every integer $ k$ greater than 1 has a multiple that is less than $ k^4$ and can be written in the decimal system with at most four different digits.

2005 Federal Competition For Advanced Students, Part 1, 1

Tags: pigeonhole principle , number theory

Prove that there are infinitely many multiples of 2005 that contain all the digits 0, 1, 2,...,9 an equal number of times.

1993 All-Russian Olympiad, 3

Tags: floor function , pigeonhole principle , combinatorics

What is the maximum number of checkers it is possible to put on a $ n \times n$ chessboard such that in every row and in every column there is an even number of checkers?

1999 Croatia National Olympiad, Problem 4

Tags: number theory , pigeonhole principle

Given nine positive integers, is it always possible to choose four different numbers $a,b,c,d$ such that $a+b$ and $c+d$ are congruent modulo $20$?

2009 Romania Team Selection Test, 2

Tags: combinatorics , pigeonhole principle

A square of side $N=n^2+1$, $n\in \mathbb{N}^*$, is partitioned in unit squares (of side $1$), along $N$ rows and $N$ columns. The $N^2$ unit squares are colored using $N$ colors, $N$ squares with each color. Prove that for any coloring there exists a row or a column containing unit squares of at least $n+1$ colors.

2009 Germany Team Selection Test, 1

Tags: pigeonhole principle , geometry , combinatorics , extremal combinatorics , point set , bezout s identity

In the coordinate plane consider the set $ S$ of all points with integer coordinates. For a positive integer $ k$, two distinct points $A$, $ B\in S$ will be called $ k$-[i]friends[/i] if there is a point $ C\in S$ such that the area of the triangle $ ABC$ is equal to $ k$. A set $ T\subset S$ will be called $ k$-[i]clique[/i] if every two points in $ T$ are $ k$-friends. Find the least positive integer $ k$ for which there exits a $ k$-clique with more than 200 elements. [i]Proposed by Jorge Tipe, Peru[/i]

2010 China Team Selection Test, 3

Tags: pigeonhole principle , ceiling function , number theory

Let $k>1$ be an integer, set $n=2^{k+1}$. Prove that for any positive integers $a_1<a_2<\cdots<a_n$, the number $\prod_{1\leq i<j\leq n}(a_i+a_j)$ has at least $k+1$ different prime divisors.

1994 Iran MO (2nd round), 1

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

Let $\overline{a_1a_2a_3\ldots a_n}$ be the representation of a $n-$digits number in base $10.$ Prove that there exists a one-to-one function like $f : \{0, 1, 2, 3, \ldots, 9\} \to \{0, 1, 2, 3, \ldots, 9\}$ such that $f(a_1) \neq 0$ and the number $\overline{ f(a_1)f(a_2)f(a_3) \ldots f(a_n) }$ is divisible by $3.$

2012 Online Math Open Problems, 20

Tags: algorithm , inequalities , induction , pigeonhole principle , strong induction

The numbers $1, 2, \ldots, 2012$ are written on a blackboard. Each minute, a student goes up to the board, chooses two numbers $x$ and $y$, erases them, and writes the number $2x+2y$ on the board. This continues until only one number $N$ remains. Find the remainder when the maximum possible value of $N$ is divided by 1000. [i]Victor Wang.[/i]

2008 Romania Team Selection Test, 3

Tags: induction , pigeonhole principle , combinatorics

Let $ n \geq 3$ be a positive integer and let $ m \geq 2^{n\minus{}1}\plus{}1$. Prove that for each family of nonzero distinct subsets $ (A_j)_{j \in \overline{1, m}}$ of $ \{1, 2, ..., n\}$ there exist $ i$, $ j$, $ k$ such that $ A_i \cup A_j \equal{} A_k$.

2014 Contests, 3

Tags: pigeonhole principle , combinatorics

There are $2014$ balls with $106$ different colors, $19$ of each color. Determine the least possible value of $n$ so that no matter how these balls are arranged around a circle, one can choose $n$ consecutive balls so that amongst them, there are $53$ balls with different colors.

1997 South africa National Olympiad, 6

Tags: floor function , pigeonhole principle , graph theory , ramsey theory , combinatorics

Six points are connected in pairs by lines, each of which is either red or blue. Every pair of points is joined. Determine whether there must be a closed path having four sides all of the same colour. (A path is closed if it begins and ends at the same point.)

2000 Dutch Mathematical Olympiad, 4

Tags: pigeonhole principle , trigonometry

Fifteen boys are standing on a field, and each of them has a ball. No two distances between two of the boys are equal. Each boy throws his ball to the boy standing closest to him. (a) Show that one of the boys does not get any ball. (b) Prove that none of the boys gets more than five balls.

2001 Romania Team Selection Test, 2

Tags: function , pigeonhole principle , number theory , prime number , combinatorics , algebra

a) Let $f,g:\mathbb{Z}\rightarrow\mathbb{Z}$ be one to one maps. Show that the function $h:\mathbb{Z}\rightarrow\mathbb{Z}$ defined by $h(x)=f(x)g(x)$, for all $x\in\mathbb{Z}$, cannot be a surjective function. b) Let $f:\mathbb{Z}\rightarrow\mathbb{Z}$ be a surjective function. Show that there exist surjective functions $g,h:\mathbb{Z}\rightarrow\mathbb{Z}$ such that $f(x)=g(x)h(x)$, for all $x\in\mathbb{Z}$.

2002 Romania Team Selection Test, 3

Tags: pigeonhole principle , number theory

Let $a,b$ be positive real numbers. For any positive integer $n$, denote by $x_n$ the sum of digits of the number $[an+b]$ in it's decimal representation. Show that the sequence $(x_n)_{n\ge 1}$ contains a constant subsequence. [i]Laurentiu Panaitopol[/i]

2004 National Olympiad First Round, 3

Tags: pigeonhole principle

At most how many elements does a set have such that all elements are less than $102$ and it doesn't contain the sum of any two elements? $ \textbf{(A)}\ 49 \qquad\textbf{(B)}\ 50 \qquad\textbf{(C)}\ 51 \qquad\textbf{(D)}\ 54 \qquad\textbf{(E)}\ 62 $

2022 Taiwan TST Round 1, C

Tags: pigeonhole principle , c2

Let $n\ge 3$ be a fixed integer. There are $m\ge n+1$ beads on a circular necklace. You wish to paint the beads using $n$ colors, such that among any $n+1$ consecutive beads every color appears at least once. Find the largest value of $m$ for which this task is $\emph{not}$ possible. [i]Carl Schildkraut, USA[/i]

2001 USA Team Selection Test, 3

Tags: induction , pigeonhole principle , combinatorics , probabilistic method

For a set $S$, let $|S|$ denote the number of elements in $S$. Let $A$ be a set of positive integers with $|A| = 2001$. Prove that there exists a set $B$ such that (i) $B \subseteq A$; (ii) $|B| \ge 668$; (iii) for any $u, v \in B$ (not necessarily distinct), $u+v \not\in B$.

2012 Morocco TST, 2

Tags: induction , pigeonhole principle , algebra

Let $\left ( a_{n} \right )_{n \geq 1}$ be an increasing sequence of positive integers such that $a_1=1$, and for all positive integers $n$, $a_{n+1}\leq 2n$. Prove that for every positive $n$; there exists positive integers $p$ and $q$ such that $n=a_{p}-a_{q}$.

2012 Germany Team Selection Test, 1

Tags: algebra , polynomial , pigeonhole principle , number theory , combinatorics

Consider a polynomial $P(x) = \prod^9_{j=1}(x+d_j),$ where $d_1, d_2, \ldots d_9$ are nine distinct integers. Prove that there exists an integer $N,$ such that for all integers $x \geq N$ the number $P(x)$ is divisible by a prime number greater than 20. [i]Proposed by Luxembourg[/i]

1997 Brazil Team Selection Test, Problem 4

Tags: matrix , number theory , pigeonhole principle

Consider an $N\times N$ matrix, where $N$ is an odd positive integer, such that all its entries are $-1,0$ or $1$. Consider the sum of the numbers in every line and every column. Prove that at least two of the $2N$ sums are equal.

2014 USAMTS Problems, 4:

Tags: pigeonhole principle , inequalities , geometry , geometric transformation , rotation , ceiling function

Nine distinct positive integers are arranged in a circle such that the product of any two non-adjacent numbers in the circle is a multiple of $n$ and the product of any two adjacent numbers in the circle is not a multiple of $n$, where $n$ is a fixed positive integer. Find the smallest possible value for $n$.

1997 Irish Math Olympiad, 3

Tags: pigeonhole principle , combinatorics

Let $ A$ be a subset of $ \{ 0,1,2,...,1997 \}$ containing more than $ 1000$ elements. Prove that either $ A$ contains a power of $ 2$ (that is, a number of the form $ 2^k$ with $ k\equal{}0,1,2,...)$ or there exist two distinct elements $ a,b \in A$ such that $ a\plus{}b$ is a power of $ 2$.