Olympiad problems

2012 USA TSTST, 5

A rational number $x$ is given. Prove that there exists a sequence $x_0, x_1, x_2, \ldots$ of rational numbers with the following properties: (a) $x_0=x$; (b) for every $n\ge1$, either $x_n = 2x_{n-1}$ or $x_n = 2x_{n-1} + \textstyle\frac{1}{n}$; (c) $x_n$ is an integer for some $n$.

1977 IMO Longlists, 11

Tags: pigeonhole principle , modular arithmetic , number theory

Let $n$ and $z$ be integers greater than $1$ and $(n,z)=1$. Prove: (a) At least one of the numbers $z_i=1+z+z^2+\cdots +z^i,\ i=0,1,\ldots ,n-1,$ is divisible by $n$. (b) If $(z-1,n)=1$, then at least one of the numbers $z_i$ is divisible by $n$.

2009 China Western Mathematical Olympiad, 3

Tags: pigeonhole principle , floor function , combinatorics

A total of $n$ people compete in a mathematical match which contains $15$ problems where $n>12$. For each problem, $1$ point is given for a right answer and $0$ is given for a wrong answer. Analysing each possible situation, we find that if the sum of points every group of $12$ people get is no less than $36$, then there are at least $3$ people that got the right answer of a certain problem, among the $n$ people. Find the least possible $n$.

1996 Romania Team Selection Test, 16

Tags: function , algebra , pigeonhole principle

Let $ n\geq 3 $ be an integer and let $ \mathcal{S} \subset \{1,2,\ldots, n^3\} $ be a set with $ 3n^2 $ elements. Prove that there exist nine distinct numbers $ a_1,a_2,\ldots,a_9 \in \mathcal{S} $ such that the following system has a solution in nonzero integers: \begin{eqnarray*} a_1x + a_2y +a_3 z &=& 0 \\ a_4x + a_5 y + a_6 z &=& 0 \\ a_7x + a_8y + a_9z &=& 0. \end{eqnarray*} [i]Marius Cavachi[/i]

2015 India National Olympiad, 4

Tags: analytic geometry , pigeonhole principle , recursion , combinatorics

There are four basketball players $A,B,C,D$. Initially the ball is with $A$. The ball is always passed from one person to a different person. In how many ways can the ball come back to $A$ after $\textbf{seven}$ moves? (for example $A\rightarrow C\rightarrow B\rightarrow D\rightarrow A\rightarrow B\rightarrow C\rightarrow A$, or $A\rightarrow D\rightarrow A\rightarrow D\rightarrow C\rightarrow A\rightarrow B\rightarrow A)$.

2011 India National Olympiad, 4

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

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.

2014 Junior Balkan Team Selection Tests - Romania, 2

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

2009 Brazil Team Selection Test, 3

Tags: pigeonhole principle , geometry , combinatorics , extremal combinatorics , point set , bezout s identity

In the coordinate plane consider the set $ S$ of all points with integer coordinates. For a positive integer $ k$, two distinct points $A$, $ B\in S$ will be called $ k$-[i]friends[/i] if there is a point $ C\in S$ such that the area of the triangle $ ABC$ is equal to $ k$. A set $ T\subset S$ will be called $ k$-[i]clique[/i] if every two points in $ T$ are $ k$-friends. Find the least positive integer $ k$ for which there exits a $ k$-clique with more than 200 elements. [i]Proposed by Jorge Tipe, Peru[/i]

2003 Romania Team Selection Test, 11

Tags: trigonometry , pigeonhole principle , area of a triangle , geometry

In a square of side 6 the points $A,B,C,D$ are given such that the distance between any two of the four points is at least 5. Prove that $A,B,C,D$ form a convex quadrilateral and its area is greater than 21. [i]Laurentiu Panaitopol[/i]

2001 Austrian-Polish Competition, 2

Tags: limit , system of equations , pigeonhole principle , algebra

Let $n$ be a positive integer greater than $2$. Solve in nonnegative real numbers the following system of equations \[x_{k}+x_{k+1}=x_{k+2}^{2}\quad , \quad k=1,2,\cdots,n\] where $x_{n+1}=x_{1}$ and $x_{n+2}=x_{2}$.

2007 Nicolae Păun, 4

Tags: geometry , combinatorics , pigeonhole principle

$ 20 $ discs of radius $ 1 $ are bounded by a circle of radius $ 10. $ Show that in the interior of this circle is sufficient space to insert $ 7 $ discs of radius $ \frac{1}{3} $ that doesn't touch any other disc. [i]Flavian Georgescu[/i]

1972 IMO Longlists, 44

Tags: combinatorics , pigeonhole principle

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.

1993 Iran MO (2nd round), 3

Tags: pigeonhole principle , number theory

Let $n, r$ be positive integers. Find the smallest positive integer $m$ satisfying the following condition. For each partition of the set $\{1, 2, \ldots ,m \}$ into $r$ subsets $A_1,A_2, \ldots ,A_r$, there exist two numbers $a$ and $b$ in some $A_i, 1 \leq i \leq r$, such that \[ 1 < \frac ab < 1 +\frac 1n.\]

2011 Indonesia MO, 4

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

An island has $10$ cities, where some of the possible pairs of cities are connected by roads. A [i]tour route[/i] is a route starting from a city, passing exactly eight out of the other nine cities exactly once each, and returning to the starting city. (In other words, it is a loop that passes only nine cities instead of all ten cities.) For each city, there exists a tour route that doesn't pass the given city. Find the minimum number of roads on the island.

2001 All-Russian Olympiad, 4

Tags: pigeonhole principle , combinatorics

Consider a convex $2000$-gon, no three of whose diagonals have a common point. Each of its diagonals is colored in one of $999$ colors. Prove that there exists a triangle all of whose sides lie on diagonals of the same color. (Vertices of the triangle need not be vertices of the original polygon.)

2008 APMO, 2

Tags: pigeonhole principle , combinatorics , algorithm

Students in a class form groups each of which contains exactly three members such that any two distinct groups have at most one member in common. Prove that, when the class size is $ 46$, there is a set of $ 10$ students in which no group is properly contained.

1996 Moscow Mathematical Olympiad, 6

Tags: pigeonhole principle , linear algebra , matrix

Eight students solved $8$ problems. a) It turned out that each problem was solved by $5$ students. Prove that there are two students such that each problem is solved by at least one of them. b) If it turned out that each problem was solved by $4$ students, it can happen that there is no pair of students such that each problem is solved by at least one of them. (Give an example.) Proposed by S. Tokarev

2000 Cono Sur Olympiad, 2

Tags: pigeonhole principle , combinatorics

The numbers $1,2,\ldots,64$ are written in the squares of an $8\times 8$ chessboard, one number to each square. Then $2\times 2$ tiles are placed on the chessboard (without overlapping) so that each tile covers exactly four squares whose numbers sum to less than $100$. Find, with proof, the maximum number of tiles that can be placed on the chessboard, and give an example of a distribution of the numbers $1,2,\ldots,64$ into the squares of the chessboard that admits this maximum number of tiles.

2014 Contests, 2

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.

2015 India National Olympiad, 6

Tags: quadratic , modular arithmetic , pigeonhole principle , number theory

Show that from a set of $11$ square integers one can select six numbers $a^2,b^2,c^2,d^2,e^2,f^2$ such that $a^2+b^2+c^2 \equiv d^2+e^2+f^2\pmod{12}$.

2009 Belarus Team Selection Test, 2

Tags: pigeonhole principle , geometry , combinatorics , extremal combinatorics , point set , bezout s identity

In the coordinate plane consider the set $ S$ of all points with integer coordinates. For a positive integer $ k$, two distinct points $A$, $ B\in S$ will be called $ k$-[i]friends[/i] if there is a point $ C\in S$ such that the area of the triangle $ ABC$ is equal to $ k$. A set $ T\subset S$ will be called $ k$-[i]clique[/i] if every two points in $ T$ are $ k$-friends. Find the least positive integer $ k$ for which there exits a $ k$-clique with more than 200 elements. [i]Proposed by Jorge Tipe, Peru[/i]

2005 South East Mathematical Olympiad, 3

Tags: induction , pigeonhole principle , combinatorics

Let $n$ be positive integer, set $M = \{ 1, 2, \ldots, 2n \}$. Find the minimum positive integer $k$ such that for any subset $A$ (with $k$ elements) of set $M$, there exist four pairwise distinct elements in $A$ whose sum is $4n + 1$.

1993 India National Olympiad, 7

Tags: pigeonhole principle , combinatorics

Let $A = \{ 1,2, 3 , \ldots, 100 \}$ and $B$ be a subset of $A$ having $53$ elements. Show that $B$ has 2 distinct elements $x$ and $y$ whose sum is divisible by $11$.

2010 USAJMO, 2

Tags: pigeonhole principle , arithmetic sequence , induction

Let $n > 1$ be an integer. Find, with proof, all sequences $x_1 , x_2 , \ldots , x_{n-1}$ of positive integers with the following three properties: (a). $x_1 < x_2 < \cdots < x_{n-1}$ ; (b). $x_i + x_{n-i} = 2n$ for all $i = 1, 2, \ldots , n - 1$; (c). given any two indices $i$ and $j$ (not necessarily distinct) for which $x_i + x_j < 2n$, there is an index $k$ such that $x_i + x_j = x_k$.

2007 South East Mathematical Olympiad, 4

Tags: pigeonhole principle , symmetry , combinatorics

A sequence of positive integers with $n$ terms satisfies $\sum_{i=1}^{n} a_i=2007$. Find the least positive integer $n$ such that there exist some consecutive terms in the sequence with their sum equal to $30$.