Olympiad problems

2006 Alexandru Myller, 3

$ 5 $ points are situated in the plane so that any three of them form a triangle of area at most $ 1. $ Prove that there is a trapezoid of area at most $ 3 $ which contains all these points ('including' here means that the points can also be on the sides of the trapezoid).

2005 All-Russian Olympiad, 2

Tags: pigeonhole principle , number theory

Lesha put numbers from 1 to $22^2$ into cells of $22\times 22$ board. Can Oleg always choose two cells, adjacent by the side or by vertex, the sum of numbers in which is divisible by 4?

2010 Albania National Olympiad, 5

Tags: pigeonhole principle , combinatorics

All members of the senate were firstly divided into $S$ senate commissions . According to the rules, no commission has less that $5$ senators and every two commissions have different number of senators. After the first session the commissions were closed and new commissions were opened. Some of the senators now are not a part of any commission. It resulted also that every two senators that were in the same commission in the first session , are not any more in the same commission. [b](a)[/b]Prove that at least $4S+10$ senators were left outside the commissions. [b](b)[/b]Prove that this number is achievable. Albanian National Mathematical Olympiad 2010---12 GRADE Question 5.

2014 USA TSTST, 4

Tags: modular arithmetic , linear algebra , floor function , vector , pigeonhole principle , polynomial , algebra

Let $P(x)$ and $Q(x)$ be arbitrary polynomials with real coefficients, and let $d$ be the degree of $P(x)$. Assume that $P(x)$ is not the zero polynomial. Prove that there exist polynomials $A(x)$ and $B(x)$ such that: (i) both $A$ and $B$ have degree at most $d/2$ (ii) at most one of $A$ and $B$ is the zero polynomial. (iii) $\frac{A(x)+Q(x)B(x)}{P(x)}$ is a polynomial with real coefficients. That is, there is some polynomial $C(x)$ with real coefficients such that $A(x)+Q(x)B(x)=P(x)C(x)$.

2007 Singapore MO Open, 1

Tags: combinatorics , pigeonhole principle , n-variable inequality , algebra

Let $x_1,x_2,\ldots,x_n$ be real numbers satisfying $x_1^2+x_2^2+\ldots+x_n^2=1$. Prove that for every integer $k\ge2$ there are integers $a_1,a_2,\ldots,a_n$, not all zero, such that $|a_i|\le k-1$ for all $i$, and $|a_1x_1+a_2x_2+\ldots+a_nx_n|\le{(k-1)\sqrt n\over k^n-1}$.

2011 Purple Comet Problems, 11

Tags: probability , pigeonhole principle , modular arithmetic

Six distinct positive integers are randomly chosen between $1$ and $2011;$ inclusive. The probability that some pair of the six chosen integers has a difference that is a multiple of $5 $ is $n$ percent. Find $n.$

2010 Contests, 3

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

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

2004 Romania Team Selection Test, 9

Tags: matrix , linear algebra , inequalities , pigeonhole principle , combinatorics

Let $n\geq 2$ be a positive integer, and $X$ a set with $n$ elements. Let $A_{1},A_{2},\ldots,A_{101}$ be subsets of $X$ such that the union of any $50$ of them has more than $\frac{50}{51}n$ elements. Prove that among these $101$ subsets there exist $3$ subsets such that any two of them have a common element.

1997 All-Russian Olympiad, 4

Tags: pigeonhole principle , combinatorics , geometric transformation , geometry

The numbers from $1$ to $100$ are arranged in a $10\times 10$ table so that any two adjacent numbers have sum no larger than $S$. Find the least value of $S$ for which this is possible. [i]D. Hramtsov[/i]

2012 China Girls Math Olympiad, 4

Tags: geometry , pigeonhole principle , trapezoid , combinatorics , inequalities

There is a stone at each vertex of a given regular $13$-gon, and the color of each stone is black or white. Prove that we may exchange the position of two stones such that the coloring of these stones are symmetric with respect to some symmetric axis of the $13$-gon.

2014 APMO, 4

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

Let $n$ and $b$ be positive integers. We say $n$ is $b$-discerning if there exists a set consisting of $n$ different positive integers less than $b$ that has no two different subsets $U$ and $V$ such that the sum of all elements in $U$ equals the sum of all elements in $V$. (a) Prove that $8$ is $100$-discerning. (b) Prove that $9$ is not $100$-discerning. [i]Senior Problems Committee of the Australian Mathematical Olympiad Committee[/i]

2013 China Girls Math Olympiad, 3

Tags: pigeonhole principle , combinatorics , graph theory , symmetry , inequalities

In a group of $m$ girls and $n$ boys, any two persons either know each other or do not know each other. For any two boys and any two girls, there are at least one boy and one girl among them,who do not know each other. Prove that the number of unordered pairs of (boy, girl) who know each other does not exceed $m+\frac{n(n-1)}{2}$.

2021 Cyprus JBMO TST, 4

Tags: ramsey theory , pigeonhole principle , combinatorics

We colour every square of a $4\times 19$ chess board with one of the colours red, green and blue. Prove that however this colouring is done, we can always find two horizontal rows and two vertical columns such that the $4$ squares on the intersections of these lines all have the same colour.

2013 AMC 12/AHSME, 20

Tags: pigeonhole principle , inequalities , symmetry

Let $S$ be the set $\{1,2,3,...,19\}$. For $a,b \in S$, define $a \succ b$ to mean that either $0 < a - b \leq 9$ or $b - a > 9$. How many ordered triples $(x,y,z)$ of elements of $S$ have the property that $x \succ y$, $y \succ z$, and $z \succ x$? $ \textbf{(A)} \ 810 \qquad \textbf{(B)} \ 855 \qquad \textbf{(C)} \ 900 \qquad \textbf{(D)} \ 950 \qquad \textbf{(E)} \ 988$

2008 ISI B.Math Entrance Exam, 4

Tags: pigeonhole principle

Let $a_1,a_2,...,a_n$ be integers . Show that there exists integers $k$ and $r$ such that the sum $a_k+a_{k+1}+...+a_{k+r}$ is divisible by $n$ .

2003 Austrian-Polish Competition, 9

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

Take any 26 distinct numbers from {1, 2, ... , 100}. Show that there must be a non-empty subset of the $ 26$ whose product is a square. [hide] I think that the upper limit for such subset is 37.[/hide]

2011 India National Olympiad, 4

Tags: floor function , trapezoid , combinatorics , pigeonhole principle , geometry

Suppose five of the nine vertices of a regular nine-sided polygon are arbitrarily chosen. Show that one can select four among these five such that they are the vertices of a trapezium.

2009 Argentina Team Selection Test, 1

Tags: combinatorics , pigeonhole principle , induction

On a $ 50 \times 50$ board, the centers of several unit squares are colored black. Find the maximum number of centers that can be colored black in such a way that no three black points form a right-angled triangle.

2005 BAMO, 3

Tags: pigeonhole principle , inequalities , ceiling function , trigonometry

Let $ n\ge12$ be an integer, and let $ P_1,P_2,...P_n, Q$ be distinct points in a plane. Prove that for some $ i$, at least $ \frac{n}{6}\minus{}1$ of the distances $ P_1P_i,P_2P_i,...P_{i\minus{}1}P_i,P_{i\plus{}1}P_i,...P_nP_i$ are less than $ P_iQ$.

2011 Croatia Team Selection Test, 1

Tags: modular arithmetic , pigeonhole principle , algebra , induction

We define a sequence $a_n$ so that $a_0=1$ and \[a_{n+1} = \begin{cases} \displaystyle \frac{a_n}2 & \textrm { if } a_n \equiv 0 \pmod 2, \\ a_n + d & \textrm{ otherwise. } \end{cases} \] for all postive integers $n$. Find all positive integers $d$ such that there is some positive integer $i$ for which $a_i=1$.

2008 Argentina National Olympiad, 1

Tags: pigeonhole principle , modular arithmetic , number theory

$ 101$ positive integers are written on a line. Prove that we can write signs $ \plus{}$, signs $ \times$ and parenthesis between them, without changing the order of the numbers, in such a way that the resulting expression makes sense and the result is divisible by $ 16!$.

2014 Putnam, 3

Tags: vector , putnam matrices , pigeonhole principle

Let $A$ be an $m\times n$ matrix with rational entries. Suppose that there are at least $m+n$ distinct prime numbers among the absolute values of the entries of $A.$ Show that the rank of $A$ is at least $2.$

1972 IMO Longlists, 44

Tags: pigeonhole principle , combinatorics

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.

2002 All-Russian Olympiad, 2

Tags: combinatorics , pigeonhole principle , induction

We are given one red and $k>1$ blue cells, and a pack of $2n$ cards, enumerated by the numbers from $1$ to $2n$. Initially, the pack is situated on the red cell and arranged in an arbitrary order. In each move, we are allowed to take the top card from one of the cells and place it either onto the top of another cell on which the number on the top card is greater by $1$, or onto an empty cell. Given $k$, what is the maximal $n$ for which it is always possible to move all the cards onto a blue cell?

2023 Junior Balkan Team Selection Tests - Romania, P4

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

Given is a cube $3 \times 3 \times 3$ with $27$ unit cubes. In each such cube a positive integer is written. Call a $\textit {strip}$ a block $1 \times 1 \times 3$ of $3$ cubes. The numbers are written so that for each cube, its number is the sum of three other numbers, one from each of the three strips it is in. Prove that there are at least $16$ numbers that are at most $60$.