Olympiad problems

2012 ELMO Shortlist, 5

Prove that if $m,n$ are relatively prime positive integers, $x^m-y^n$ is irreducible in the complex numbers. (A polynomial $P(x,y)$ is irreducible if there do not exist nonconstant polynomials $f(x,y)$ and $g(x,y)$ such that $P(x,y) = f(x,y)g(x,y)$ for all $x,y$.) [i]David Yang.[/i]

2014 IMO Shortlist, C3

Tags: pigeonhole principle , combinatorics , global

Let $n \ge 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is [i]peaceful[/i] if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.

2001 China National Olympiad, 3

Tags: pigeonhole principle , combinatorics

Let $P$ be a regular $n$-gon $A_1A_2\ldots A_n$. Find all positive integers $n$ such that for each permutation $\sigma (1),\sigma (2),\ldots ,\sigma (n)$ there exists $1\le i,j,k\le n$ such that the triangles $A_{i}A_{j}A_{k}$ and $A_{\sigma (i)}A_{\sigma (j)}A_{\sigma (k)}$ are both acute, both right or both obtuse.

2010 Albania National Olympiad, 3

Tags: calculus , integration , analytic geometry , geometry , pigeonhole principle , combinatorics

[b](a)[/b]Prove that every pentagon with integral coordinates has at least two vertices , whose respective coordinates have the same parity. [b](b)[/b]What is the smallest area possible of pentagons with integral coordinates. Albanian National Mathematical Olympiad 2010---12 GRADE Question 3.

2009 USAMTS Problems, 4

Tags: inequalities , pigeonhole principle

Let $S$ be a set of $10$ distinct positive real numbers. Show that there exist $x,y \in S$ such that \[0 < x - y < \frac{(1 + x)(1 + y)}{9}.\]

2014 All-Russian Olympiad, 4

Tags: geometry , geometric transformation , homothety , pigeonhole principle , combinatorics , double counting

Given are $n$ pairwise intersecting convex $k$-gons on the plane. Any of them can be transferred to any other by a homothety with a positive coefficient. Prove that there is a point in a plane belonging to at least $1 +\frac{n-1}{2k}$ of these $k$-gons.

2014 IMO, 2

Tags: pigeonhole principle , global , combinatorics

Let $n \ge 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is [i]peaceful[/i] if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.

2011 Turkey Team Selection Test, 3

Tags: function , pigeonhole principle , combinatorics

Let $A$ and $B$ be sets with $2011^2$ and $2010$ elements, respectively. Show that there is a function $f:A \times A \to B$ satisfying the condition $f(x,y)=f(y,x)$ for all $(x,y) \in A \times A$ such that for every function $g:A \to B$ there exists $(a_1,a_2) \in A \times A$ with $g(a_1)=f(a_1,a_2)=g(a_2)$ and $a_1 \neq a_2.$

2012 Belarus 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]

2012 USA TSTST, 1

Tags: symmetry , pigeonhole principle , arithmetic sequence , algebra , additive combinatorics , sequence

Find all infinite sequences $a_1, a_2, \ldots$ of positive integers satisfying the following properties: (a) $a_1 < a_2 < a_3 < \cdots$, (b) there are no positive integers $i$, $j$, $k$, not necessarily distinct, such that $a_i+a_j=a_k$, (c) there are infinitely many $k$ such that $a_k = 2k-1$.

2004 Bulgaria National Olympiad, 3

Tags: pigeonhole principle , combinatorics , graph theory

A group consist of n tourists. Among every 3 of them there are 2 which are not familiar. For every partition of the tourists in 2 buses you can find 2 tourists that are in the same bus and are familiar with each other. Prove that is a tourist familiar to at most $\displaystyle \frac 2{5}n$ tourists.

2003 AIME Problems, 12

Tags: quadratic , ceiling function , pigeonhole principle

The members of a distinguished committee were choosing a president, and each member gave one vote to one of the $27$ candidates. For each candidate, the exact percentage of votes the candidate got was smaller by at least $1$ than the number of votes for that candidate. What is the smallest possible number of members of the committee?

2002 District Olympiad, 2

Tags: invariant , pigeonhole principle

A group of $67$ students pass their examination consisting of $6$ questions, labeled with the numbers $1$ to $6$. A correct answer to question $n$ is quoted $n$ points and for an incorrect answer to the same question a student loses $n$ point. a) Find the least possible positive difference between any $2$ final scores b) Show that at least $4$ participants have the same final score c) Show that at least $2$ students gave identical answer to all six questions.

2012 Argentina Cono Sur TST, 1

Tags: pigeonhole principle , ceiling function , geometry , rectangle

Sofía colours $46$ cells of a $9 \times 9$ board red. If Pedro can find a $2 \times 2$ square from the board that has $3$ or more red cells, he wins; otherwise, Sofía wins. Determine the player with the winning strategy.

1997 Vietnam National Olympiad, 3

Tags: 3d geometry , pigeonhole principle , geometry

In the unit cube, given 75 points, no three of which are collinear. Prove that there exits a triangle whose vertices are among the given points and whose area is not greater than 7/72.

2021 Iran MO (3rd Round), 3

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]

2011 IMO Shortlist, 2

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

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]

2013 Online Math Open Problems, 43

Tags: pigeonhole principle

In a tennis tournament, each competitor plays against every other competitor, and there are no draws. Call a group of four tennis players ``ordered'' if there is a clear winner and a clear loser (i.e., one person who beat the other three, and one person who lost to the other three.) Find the smallest integer $n$ for which any tennis tournament with $n$ people has a group of four tennis players that is ordered. [i]Ray Li[/i]

2006 Iran MO (3rd Round), 4

Tags: analytic geometry , algorithm , pigeonhole principle , geometry , combinatorics

The image shown below is a cross with length 2. If length of a cross of length $k$ it is called a $k$-cross. (Each $k$-cross ahs $6k+1$ squares.) [img]http://aycu08.webshots.com/image/4127/2003057947601864020_th.jpg[/img] a) Prove that space can be tiled with $1$-crosses. b) Prove that space can be tiled with $2$-crosses. c) Prove that for $k\geq5$ space can not be tiled with $k$-crosses.

1978 IMO Shortlist, 1

Tags: pigeonhole principle , combinatorics , partition , set systems , extremal combinatorics

The set $M = \{1, 2, . . . , 2n\}$ is partitioned into $k$ nonintersecting subsets $M_1,M_2, \dots, M_k,$ where $n \ge k^3 + k.$ Prove that there exist even numbers $2j_1, 2j_2, \dots, 2j_{k+1}$ in $M$ that are in one and the same subset $M_i$ $(1 \le i \le k)$ such that the numbers $2j_1 - 1, 2j_2 - 1, \dots, 2j_{k+1} - 1$ are also in one and the same subset $M_j (1 \le j \le k).$

2010 Postal Coaching, 1

Tags: pigeonhole principle , ratio , geometry

Let $A, B, C, D$ be four distinct points in the plane such that the length of the six line segments $AB, AC, AD, BC, BD, CD$ form a $2$-element set ${a, b}$. If $a > b$, determine all the possible values of $\frac ab$.

2008 China National Olympiad, 2

Tags: trapezoid , pigeonhole principle , combinatorics , geometry

Find the smallest integer $n$ satisfying the following condition: regardless of how one colour the vertices of a regular $n$-gon with either red, yellow or blue, one can always find an isosceles trapezoid whose vertices are of the same colour.

1961 AMC 12/AHSME, 39

Tags: pigeonhole principle

Any five points are taken inside or on a square with side length $1$. Let $a$ be the [i]smallest[/i] possible number with the property that it is always possible to select one pair of points from these five such that the distance between them is equal to or less than $a$. Then $a$ is: ${{ \textbf{(A)}\ \sqrt{3}/3 \qquad\textbf{(B)}\ \sqrt{2}/2 \qquad\textbf{(C)}\ 2\sqrt{2}/3 \qquad\textbf{(D)}\ 1 }\qquad\textbf{(E)}\ \sqrt{2} } $

2012 India IMO Training Camp, 2

Tags: pigeonhole principle , number theory

Let $S$ be a nonempty set of primes satisfying the property that for each proper subset $P$ of $S$, all the prime factors of the number $\left(\prod_{p\in P}p\right)-1$ are also in $S$. Determine all possible such sets $S$.

2007 All-Russian Olympiad Regional Round, 9.8

Tags: pigeonhole principle , combinatorics

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