Olympiad problems

2007 All-Russian Olympiad Regional Round, 9.8

A set contains $ 372$ integers from $ 1,2,...,1200$ . For every element $ a\in S$, the numbers $ a\plus{}4,a\plus{}5,a\plus{}9$ don't belong to $ S$. Prove that $ 600\in S$.

2012 ELMO Shortlist, 6

Tags: logarithm , function , number theory , induction , inequalities , least common multiple , pigeonhole principle

Consider a directed graph $G$ with $n$ vertices, where $1$-cycles and $2$-cycles are permitted. For any set $S$ of vertices, let $N^{+}(S)$ denote the out-neighborhood of $S$ (i.e. set of successors of $S$), and define $(N^{+})^k(S)=N^{+}((N^{+})^{k-1}(S))$ for $k\ge2$. For fixed $n$, let $f(n)$ denote the maximum possible number of distinct sets of vertices in $\{(N^{+})^k(X)\}_{k=1}^{\infty}$, where $X$ is some subset of $V(G)$. Show that there exists $n>2012$ such that $f(n)<1.0001^n$. [i]Linus Hamilton.[/i]

2013 EGMO, 6

Tags: combinatorics , pigeonhole principle

Snow White and the Seven Dwarves are living in their house in the forest. On each of $16$ consecutive days, some of the dwarves worked in the diamond mine while the remaining dwarves collected berries in the forest. No dwarf performed both types of work on the same day. On any two different (not necessarily consecutive) days, at least three dwarves each performed both types of work. Further, on the first day, all seven dwarves worked in the diamond mine. Prove that, on one of these $16$ days, all seven dwarves were collecting berries.

1990 IMO Longlists, 10

Tags: combinatorics , counting , pigeonhole principle

Let $p, k$ and $x$ be positive integers such that $p \geq k$ and $x < \left[ \frac{p(p-k+1)}{2(k-1)} \right]$, where $[q]$ is the largest integer no larger than $q$. Prove that when $x$ balls are put into $p$ boxes arbitrarily, there exist $k$ boxes with the same number of balls.

2009 Moldova Team Selection Test, 2

Tags: pigeonhole principle , geometric transformation , greatest common divisor , algebra , geometry , number theory , polynomial

$ f(x)$ and $ g(x)$ are two polynomials with nonzero degrees and integer coefficients, such that $ g(x)$ is a divisor of $ f(x)$ and the polynomial $ f(x)\plus{}2009$ has $ 50$ integer roots. Prove that the degree of $ g(x)$ is at least $ 5$.

2012 Iran Team Selection Test, 2

Tags: polynomial , algebra , pigeonhole principle

Do there exist $2000$ real numbers (not necessarily distinct) such that all of them are not zero and if we put any group containing $1000$ of them as the roots of a monic polynomial of degree $1000$, the coefficients of the resulting polynomial (except the coefficient of $x^{1000}$) be a permutation of the $1000$ remaining numbers? [i]Proposed by Morteza Saghafian[/i]

2001 Austrian-Polish Competition, 2

Tags: algebra , limit , system of equations , pigeonhole principle

Let $n$ be a positive integer greater than $2$. Solve in nonnegative real numbers the following system of equations \[x_{k}+x_{k+1}=x_{k+2}^{2}\quad , \quad k=1,2,\cdots,n\] where $x_{n+1}=x_{1}$ and $x_{n+2}=x_{2}$.

2023 Bulgaria EGMO TST, 4

Tags: combinatorics , pigeonhole principle , coloring , digit

Each two-digit is number is coloured in one of $k$ colours. What is the minimum value of $k$ such that, regardless of the colouring, there are three numbers $a$, $b$ and $c$ with different colours with $a$ and $b$ having the same units digit (second digit) and $b$ and $c$ having the same tens digit (first digit)?

2001 IberoAmerican, 3

Tags: algebra , geometry , pigeonhole principle

Show that it is impossible to cover a unit square with five equal squares with side $s<\frac{1}{2}$.

PEN O Problems, 57

Tags: number theory , relatively prime , pigeonhole principle

Prove that every selection of $1325$ integers from $M=\{1, 2, \cdots, 1987 \}$ must contain some three numbers $\{a, b, c\}$ which are pairwise relatively prime, but that it can be avoided if only $1324$ integers are selected.

1997 Brazil Team Selection Test, Problem 4

Tags: number theory , matrix , 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.

2022 Thailand TST, 1

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]

1997 South africa National Olympiad, 6

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

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

2004 Iran MO (3rd Round), 6

Tags: geometry , probability , induction , combinatorics , pigeonhole principle , rectangle , expected value

assume that we have a n*n table we fill it with 1,...,n such that each number exists exactly n times prove that there exist a row or column such that at least $\sqrt{n}$ diffrent number are contained.

2009 Germany Team Selection Test, 1

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

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 Contests, 1

Tags: algebra , pigeonhole principle , system of equations

Find all triples $(a,b,c)$ of positive real numbers satisfying the system of equations \[ a\sqrt{b}-c \&= a,\qquad b\sqrt{c}-a \&= b,\qquad c\sqrt{a}-b \&= c. \]

2010 Romanian Masters In Mathematics, 6

Tags: algebra , induction , pigeonhole principle , relatively prime , polynomial , number theory

Given a polynomial $f(x)$ with rational coefficients, of degree $d \ge 2$, we define the sequence of sets $f^0(\mathbb{Q}), f^1(\mathbb{Q}), \ldots$ as $f^0(\mathbb{Q})=\mathbb{Q}$, $f^{n+1}(\mathbb{Q})=f(f^{n}(\mathbb{Q}))$ for $n\ge 0$. (Given a set $S$, we write $f(S)$ for the set $\{f(x)\mid x\in S\})$. Let $f^{\omega}(\mathbb{Q})=\bigcap_{n=0}^{\infty} f^n(\mathbb{Q})$ be the set of numbers that are in all of the sets $f^n(\mathbb{Q})$, $n\geq 0$. Prove that $f^{\omega}(\mathbb{Q})$ is a finite set. [i]Dan Schwarz, Romania[/i]

2003 Romania Team Selection Test, 11

Tags: trigonometry , pigeonhole principle , area of a triangle , geometry

In a square of side 6 the points $A,B,C,D$ are given such that the distance between any two of the four points is at least 5. Prove that $A,B,C,D$ form a convex quadrilateral and its area is greater than 21. [i]Laurentiu Panaitopol[/i]

1972 IMO Shortlist, 12

Tags: combinatorics , pigeonhole principle

Prove that from a set of ten distinct two-digit numbers, it is always possible to find two disjoint subsets whose members have the same sum.

1998 Niels Henrik Abels Math Contest (Norwegian Math Olympiad) Round 2, 4

Tags: pigeonhole principle , ceiling function

In a store, there are 7 cases containing 128 apples altogether. Let $ N$ be the greatest number such that one can be certain to find a case with at least $ N$ apples. Then, the last digit of $ N$ is $ \text{(A)}\ 0 \qquad \text{(B)}\ 2 \qquad \text{(C)}\ 5 \qquad \text{(D)}\ 7 \qquad \text{(E)}\ 9$

1999 Junior Balkan MO, 3

Tags: geometry , combinatorics , pigeonhole principle

Let $S$ be a square with the side length 20 and let $M$ be the set of points formed with the vertices of $S$ and another 1999 points lying inside $S$. Prove that there exists a triangle with vertices in $M$ and with area at most equal with $\frac 1{10}$. [i]Yugoslavia[/i]