Olympiad problems

2002 All-Russian Olympiad, 2

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?

2003 Manhattan Mathematical Olympiad, 2

Tags: pigeonhole principle

A tennis net is made of strings tied up together which make a grid consisting of small congruent squares as shown below. [asy] size(500); xaxis(-50,50); yaxis(-5,5); add(shift(-50,-5)*grid(100,10));[/asy] The size of the net is $100\times 10$ small squares. What is the maximal number of edges of small squares which can be cut without breaking the net into two pieces? (If an edge is cut, the cut is made in the middle, not at the ends.)

2011 Preliminary Round - Switzerland, 3

Tags: pigeonhole principle , modular arithmetic , combinatorics

On a blackboard, there are $11$ positive integers. Show that one can choose some (maybe all) of these numbers and place "$+$" and "$-$" in between such that the result is divisible by $2011$.

2024 Auckland Mathematical Olympiad, 10

Tags: geometry , rectangle , pigeonhole principle

Prove that circles constructed on the sides of a convex quadrilateral as diameters completely cover this quadrilateral.

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.

2000 Mediterranean Mathematics Olympiad, 1

Tags: pigeonhole principle , combinatorics

Let $F=\{1,2,...,100\}$ and let $G$ be any $10$-element subset of $F$. Prove that there exist two disjoint nonempty subsets $S$ and $T$ of $G$ with the same sum of elements.

2009 China Team Selection Test, 2

Tags: ceiling function , pigeonhole principle , induction , graph theory , combinatorics

Let $ n,k$ be given positive integers satisfying $ k\le 2n \minus{} 1$. On a table tennis tournament $ 2n$ players take part, they play a total of $ k$ rounds match, each round is divided into $ n$ groups, each group two players match. The two players in different rounds can match on many occasions. Find the greatest positive integer $ m \equal{} f(n,k)$ such that no matter how the tournament processes, we always find $ m$ players each of pair of which didn't match each other.

1978 USAMO, 5

Tags: pigeonhole principle , floor function , ramsey theory

Nine mathematicians meet at an international conference and discover that among any three of them, at least two speak a common language. If each of the mathematicians speak at most three languages, prove that there are at least three of the mathematicians who can speak the same language.

2008 Romanian Master of Mathematics, 4

Tags: pigeonhole principle , perimeter , combinatorial geometry , combinatorics , geometry

Consider a square of sidelength $ n$ and $ (n\plus{}1)^2$ interior points. Prove that we can choose $ 3$ of these points so that they determine a triangle (eventually degenerated) of area at most $ \frac12$.

1985 IMO Longlists, 49

Tags: pigeonhole principle , combinatorics , mean

Given a set $M$ of $1985$ positive integers, none of which has a prime divisor larger than $26$, prove that the set has four distinct elements whose geometric mean is an integer.

2013 Bogdan Stan, 4

Tags: geometric inequality , combinatorics , pigeonhole , pigeonhole principle

Consider $ 16 $ pairwise distinct natural numbers smaller than $ 1597. $ [b]a)[/b] Prove that among these, there are three numbers having the property that the sum of any two of them is bigger than the third. [b]b)[/b] If one of these numbers is $ 1597, $ is still true the fact from subpoint [b]a)[/b]? [i]Teodor Radu[/i]

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

2009 Argentina Team Selection Test, 1

Tags: induction , pigeonhole principle , combinatorics

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.

1971 IMO Longlists, 10

Tags: pigeonhole principle , geometry , combinatorics

In how many different ways can three knights be placed on a chessboard so that the number of squares attacked would be maximal?

1997 Moldova Team Selection Test, 3

Tags: pigeonhole principle , decimal representation , divisibility , multiple , digit , number theory

Prove that every integer $ k$ greater than 1 has a multiple that is less than $ k^4$ and can be written in the decimal system with at most four different digits.

1993 Flanders Math Olympiad, 1

Tags: pigeonhole principle

The 20 pupils in a class each send 10 cards to 10 (different) class members. [size=92][i][note: you cannot send a card to yourself.][/i][/size] (a) Show at least 2 pupils sent each other a card. (b) Now suppose we had $n$ pupils sending $m$ cards each. For which $(m,n)$ is the above true? (That is, find minimal $m(n)$ or maximal $n(m)$)

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]

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.

2006 Poland - Second Round, 1

Tags: pigeonhole principle , number theory

Let $c$ be fixed natural number. Sequence $(a_n)$ is defined by: $a_1=1$, $a_{n+1}=d(a_n)+c$ for $n=1,2,...$. where $d(m)$ is number of divisors of $m$. Prove that there exist $k$ natural such that sequence $a_k,a_{k+1},...$ is periodic.

2014 APMO, 4

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

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]

2009 Polish MO Finals, 2

Tags: analytic geometry , geometry , pigeonhole principle , modular arithmetic , least common multiple , combinatorics , number theory

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 .

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

1980 Putnam, A4

Tags: pigeonhole principle , putnam pigeonhole

a) Prove that there exist integers $a, b, c$ not all zero and each of absolute value less than one million, such that $$ |a +b \sqrt{2} +c \sqrt{3} | <10^{-11} .$$ b) Let $ a, b, c$ be integers, not all zero and each of absolute value less than one million. Prove that $$ |a +b \sqrt{2} +c \sqrt{3} | >10^{-21} .$$

2005 USAMO, 5

Tags: geometry , induction , discrete continuity , pigeonhole principle , minimal maximal principal

Let $n$ be an integer greater than 1. Suppose $2n$ points are given in the plane, no three of which are collinear. Suppose $n$ of the given $2n$ points are colored blue and the other $n$ colored red. A line in the plane is called a [i]balancing line[/i] if it passes through one blue and one red point and, for each side of the line, the number of blue points on that side is equal to the number of red points on the same side. Prove that there exist at least two balancing lines.