This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 396

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.

2021 Science ON grade VI, 3
Tags: pigeonhole principle , combinatorics , set
Consider positive integers $a<b$ and the set $C\subset\{a,a+1,a+2,\dots ,b-2,b-1,b\}$. Suppose $C$ has more than $\frac{b-a+1}{2}$ elements. Prove that there are two elements $x,y\in C$ that satisfy $x+y=a+b$. [i] (From "Radu Păun" contest, Radu Miculescu)[/i]

2013 ELMO Shortlist, 3
Tags: pigeonhole principle , probability , expected value , combinatorics
Let $a_1,a_2,...,a_9$ be nine real numbers, not necessarily distinct, with average $m$. Let $A$ denote the number of triples $1 \le i < j < k \le 9$ for which $a_i + a_j + a_k \ge 3m$. What is the minimum possible value of $A$? [i]Proposed by Ray Li[/i]

2015 Kosovo Team Selection Test, 4
Tags: combinatorics , pigeonhole principle
Let $P_1,P_2,...,P_{2556}$ be distinct points inside a regular hexagon $ABCDEF$ of side $1$. If any three points from the set $S=\{A,B,C,D,E,F,P_1,P_2...,P_{2556}\}$ aren't collinear, prove that there exists a triangle with area smaller than $\frac{1}{1700}$, with vertices from the set $S$.

2007 Iran Team Selection Test, 2
Tags: ceiling function , pigeonhole principle , modular arithmetic , search , combinatorics
Let $A$ be the largest subset of $\{1,\dots,n\}$ such that for each $x\in A$, $x$ divides at most one other element in $A$. Prove that \[\frac{2n}3\leq |A|\leq \left\lceil \frac{3n}4\right\rceil. \]

2010 Czech-Polish-Slovak Match, 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. \]

2003 Bulgaria National Olympiad, 1
Tags: pigeonhole principle , symmetry , combinatorics
Let $x_1, x_2 \ldots , x_5$ be real numbers. Find the least positive integer $n$ with the following property: if some $n$ distinct sums of the form $x_p+x_q+x_r$ (with $1\le p<q<r\le 5$) are equal to $0$, then $x_1=x_2=\cdots=x_5=0$.

1996 Korea National Olympiad, 1
Tags: combinatorics , pigeonhole principle
If you draw $4$ points on the unit circle, prove that you can always find two points where their distance between is less than $\sqrt{2}.$

1996 Bosnia and Herzegovina Team Selection Test, 5
Tags: combinatorics , pigeonhole principle
Group of $10$ people are buying books. We know the following: $i)$ Every person bought four different books $ii)$ Every two persons bought at least one book common for both of them Taking in consideration book which was bought by maximum number of people, determine minimal value of that number

2003 Canada National Olympiad, 5
Tags: pigeonhole principle , combinatorics
Let $S$ be a set of $n$ points in the plane such that any two points of $S$ are at least $1$ unit apart. Prove there is a subset $T$ of $S$ with at least $\frac{n}{7}$ points such that any two points of $T$ are at least $\sqrt{3}$ units apart.

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.

2018 Poland - Second Round, 5
Tags: combinatorics , set theory , pigeonhole principle , counting
Let $A_1, A_2, ..., A_k$ be $5$-element subsets of set $\{1, 2, ..., 23\}$ such that, for all $1 \le i < j \le k$ set $A_i \cap A_j$ has at most three elements. Show that $k \le 2018$.

2004 China Girls Math Olympiad, 8
Tags: pigeonhole principle , rectangle , combinatorics , geometry
When the unit squares at the four corners are removed from a three by three squares, the resulting shape is called a cross. What is the maximum number of non-overlapping crosses placed within the boundary of a $ 10\times 11$ chessboard? (Each cross covers exactly five unit squares on the board.)

2022 Cyprus JBMO TST, 4
Tags: number theory , pigeonhole principle
Let $A$ be a subset of $\{1, 2, 3, \ldots, 50\}$ with the property: for every $x,y\in A$ with $x\neq y$, it holds that \[\left| \frac{1}{x}- \frac{1}{y}\right|>\frac{1}{1000}.\] Determine the largest possible number of elements that the set $A$ can have.

2014 Taiwan TST Round 2, 4
Tags: algebra , binomial theorem , pigeonhole principle
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}. \]

2012 Online Math Open Problems, 44
Tags: geometric transformation , reflection , analytic geometry , induction , pigeonhole principle , geometry
Given a set of points in space, a [i]jump[/i] consists of taking two points, $P$ and $Q,$ and replacing $P$ with the reflection of $P$ over $Q$. Find the smallest number $n$ such that for any set of $n$ lattice points in $10$-dimensional-space, it is possible to perform a finite number of jumps so that some two points coincide. [i]Author: Anderson Wang[/i]

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

2003 Gheorghe Vranceanu, 4
Tags: permutation , partition , combinatorics , pigeonhole , pigeonhole principle
Prove that among any $ 16 $ numbers smaller than $ 101 $ there are four of them that have the property that the sum of two of them is equal to the sum of the other two.

1999 Junior Balkan MO, 3
Tags: geometry , pigeonhole principle , combinatorics
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]

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?

2000 USAMO, 4
Tags: induction , pigeonhole principle , contradiction , combinatorics , grid
Find the smallest positive integer $n$ such that if $n$ squares of a $1000 \times 1000$ chessboard are colored, then there will exist three colored squares whose centers form a right triangle with sides parallel to the edges of the board.

2004 Baltic Way, 9
Tags: pigeonhole principle , number theory
A set $S$ of $n-1$ natural numbers is given ($n\ge 3$). There exist at least at least two elements in this set whose difference is not divisible by $n$. Prove that it is possible to choose a non-empty subset of $S$ so that the sum of its elements is divisible by $n$.

PEN P Problems, 42
Tags: pigeonhole principle , inequalities , additive number theory
Prove that for each positive integer $K$ there exist infinitely many even positive integers which can be written in more than $K$ ways as the sum of two odd primes.

2009 Polish MO Finals, 2
Tags: analytic geometry , geometry , pigeonhole principle , modular arithmetic , number theory , least common multiple , combinatorics
Let $ S$ be a set of all points of a plane whose coordinates are integers. Find the smallest positive integer $ k$ for which there exists a 60-element subset of set $ S$ with the following condition satisfied for any two elements $ A,B$ of the subset there exists a point $ C$ contained in $ S$ such that the area of triangle $ ABC$ is equal to k .

2008 Ukraine Team Selection Test, 7
Tags: induction , pigeonhole principle , number theory , combinatorics
There is graph $ G_0$ on vertices $ A_1, A_2, \ldots, A_n$. Graph $ G_{n \plus{} 1}$ on vertices $ A_1, A_2, \ldots, A_n$ is constructed by the rule: $ A_i$ and $ A_j$ are joined only if in graph $ G_n$ there is a vertices $ A_k\neq A_i, A_j$ such that $ A_k$ is joined with both $ A_i$ and $ A_j$. Prove that the sequence $ \{G_n\}_{n\in\mathbb{N}}$ is periodic after some term with period $ T \le 2^n$.