Olympiad problems

1999 Mediterranean Mathematics Olympiad, 2

A plane figure of area $A > n$ is given, where $n$ is a positive integer. Prove that this figure can be placed onto a Cartesian plane so that it covers at least $n+1$ points with integer coordinates.

2004 Manhattan Mathematical Olympiad, 1

Tags: pigeonhole principle

Seven line segments, with lengths no greater than $10$ inches, and no shorter than $1$ inch, are given. Show that one can choose three of them to represent the sides of a triangle. Give an example which shows that if only six segments are used, then such a choice may be impossible.

1985 IMO, 4

Tags: modular arithmetic , pigeonhole principle , combinatorics , extremal combinatorics , number theory

Given a set $M$ of $1985$ distinct positive integers, none of which has a prime divisor greater than $23$, prove that $M$ contains a subset of $4$ elements whose product is the $4$th power of an integer.

1976 AMC 12/AHSME, 12

Tags: pigeonhole principle , probability , expected value

A supermarket has $128$ crates of apples. Each crate contains at least $120$ apples and at most $144$ apples. What is the largest integer $n$ such that there must be at least $n$ crates containing the same number of apples? $\textbf{(A) }4\qquad\textbf{(B) }5\qquad\textbf{(C) }6\qquad\textbf{(D) }24\qquad \textbf{(E) }25$

2014 Turkey Junior National Olympiad, 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.

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.

2006 Mathematics for Its Sake, 3

Tags: geometry , pigeonhole principle , discrete math , discrete geometry , g.m.

Show that if the point $ M $ is situated in the interior of a square $ ABCD, $ then, among the segments $ MA,MB,MC,MD, $ [b]a)[/b] at most one of them is greater with a factor of $ \sqrt 5/2 $ than the side of the square. [b]b)[/b] at most two of them are greater than the side of the square. [b]c)[/b] at most three of them are greater with a factor of $ \sqrt 2/2 $ than the side of the square.

2010 Polish MO Finals, 1

Tags: pigeonhole principle , ceiling function , combinatorics

The integer number $n > 1$ is given and a set $S \subset \{0, 1, 2, \ldots, n-1\}$ with $|S| > \frac{3}{4} n$. Prove that there exist integer numbers $a, b, c$ such that the remainders after the division by $n$ of the numbers: \[a, b, c, a+b, b+c, c+a, a+b+c\] belong to $S$.

2024 Bangladesh Mathematical Olympiad, P4

Tags: combinatorics , sequence , modular arithmetic , pigeonhole principle

Let $a_1, a_2, \ldots, a_{11}$ be integers. Prove that there exist numbers $b_1, b_2, \ldots, b_{11}$ such that [list] [*] $b_i$ is equal to $-1,0$ or $1$ for all $i \in \{1, 2,\dots, 11\}$. [*] all numbers can't be zero at a time. [*] the number $N=a_1b_1+a_2b_2+\ldots+a_{11}b_{11}$ is divisible by $2024$. [/list]

2008 Bulgaria National Olympiad, 3

Tags: inequalities , trigonometry , modular arithmetic , induction , ceiling function , pigeonhole principle , algebra

Let $n\in\mathbb{N}$ and $0\leq a_1\leq a_2\leq\ldots\leq a_n\leq\pi$ and $b_1,b_2,\ldots ,b_n$ are real numbers for which the following inequality is satisfied : \[\left|\sum_{i\equal{}1}^{n} b_i\cos(ka_i)\right|<\frac{1}{k}\] for all $ k\in\mathbb{N}$. Prove that $ b_1\equal{}b_2\equal{}\ldots \equal{}b_n\equal{}0$.

1998 Poland - Second Round, 5

Tags: pigeonhole principle , geometry , rhombus , combinatorics

Let $a_1,a_2,\ldots,a_7, b_1,b_2,\ldots,b_7\geq 0$ be real numbers satisfying $a_i+b_i\le 2$ for all $i=\overline{1,7}$. Prove that there exist $k\ne m$ such that $|a_k-a_m|+|b_k-b_m|\le 1$. Thanks for show me the mistake typing

2012 Math Prize for Girls Olympiad, 4

Tags: function , pigeonhole principle , factorial

Let $f$ be a function from the set of rational numbers to the set of real numbers. Suppose that for all rational numbers $r$ and $s$, the expression $f(r + s) - f(r) - f(s)$ is an integer. Prove that there is a positive integer $q$ and an integer $p$ such that \[ \Bigl\lvert f\Bigl(\frac{1}{q}\Bigr) - p \Bigr\rvert \le \frac{1}{2012} \, . \]

2010 Romanian Masters In Mathematics, 6

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

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]

2000 Korea - Final Round, 1

Tags: pigeonhole principle , quadratic , number theory

Prove that for any prime $p$, there exist integers $x,y,z,$ and $w$ such that $x^2+y^2+z^2-wp=0$ and $0<w<p$

2006 USAMO, 1

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

Let $p$ be a prime number and let $s$ be an integer with $0 < s < p.$ Prove that there exist integers $m$ and $n$ with $0 < m < n < p$ and \[ \left \{\frac{sm}{p} \right\} < \left \{\frac{sn}{p} \right \} < \frac{s}{p} \] if and only if $s$ is not a divisor of $p-1$. Note: For $x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$, and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of x.

2010 Contests, 1

Tags: pigeonhole principle , system of equations , algebra

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

2012 Korea National Olympiad, 4

Tags: modular arithmetic , pigeonhole principle , combinatorics

Let $ p \equiv 3 \pmod{4}$ be a prime. Define $T = \{ (i,j) \mid i, j \in \{ 0, 1, \cdots , p-1 \} \} \smallsetminus \{ (0,0) \} $. For arbitrary subset $ S ( \ne \emptyset ) \subset T $, prove that there exist subset $ A \subset S $ satisfying following conditions: (a) $ (x_i , y_i ) \in A ( 1 \le i \le 3) $ then $ p \not | x_1 + x_2 - y_3 $ or $ p \not | y_1 + y_2 + x_3 $. (b) $ 8 n(A) > n(S) $

2022 Estonia Team Selection Test, 4

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]

2005 MOP Homework, 1

Tags: geometry , rectangle , pigeonhole principle , rotation , combinatorics

Two rooks on a chessboard are said to be attacking each other if they are placed in the same row or column of the board. (a) There are eight rooks on a chessboard, none of them attacks any other. Prove that there is an even number of rooks on black fields. (b) How many ways can eight mutually non-attacking rooks be placed on the 9 £ 9 chessboard so that all eight rooks are on squares of the same color.

1969 IMO Longlists, 58

Tags: pigeonhole principle , geometry , 3d geometry , tetrahedron

$(SWE 1)$ Six points $P_1, . . . , P_6$ are given in $3-$dimensional space such that no four of them lie in the same plane. Each of the line segments $P_jP_k$ is colored black or white. Prove that there exists one triangle $P_jP_kP_l$ whose edges are of the same color.

2011 IMO Shortlist, 2

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]

2003 Poland - Second Round, 4

Tags: number theory , combinatorics , combinatorial number theory , pigeonhole principle , prime number

Prove that for any prime number $p > 3$ exist integers $x, y, k$ that meet conditions: $0 < 2k < p$ and $kp + 3 = x^2 + y^2$.

2012 ELMO Shortlist, 4

Tags: induction , floor function , ceiling function , inequalities , pigeonhole principle , combinatorics

A tournament on $2k$ vertices contains no $7$-cycles. Show that its vertices can be partitioned into two sets, each with size $k$, such that the edges between vertices of the same set do not determine any $3$-cycles. [i]Calvin Deng.[/i]

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

2001 USAMO, 1

Tags: extremal combinatorics , pigeonhole principle , combinatorics

Each of eight boxes contains six balls. Each ball has been colored with one of $n$ colors, such that no two balls in the same box are the same color, and no two colors occur together in more than one box. Determine, with justification, the smallest integer $n$ for which this is possible.