Found problems: 1488
1991 Polish MO Finals, 2
Let $X$ be the set of all lattice points in the plane (points $(x, y)$ with $x, y \in \mathbb{Z}$). A path of length $n$ is a chain $(P_0, P_1, ... , P_n)$ of points in $X$ such that $P_{i-1}P_i = 1$ for $i = 1, ... , n$. Let $F(n)$ be the number of distinct paths beginning in $P_0=(0,0)$ and ending in any point $P_n$ on line $y = 0$. Prove that $F(n) = \binom{2n}{n}$
1992 Vietnam Team Selection Test, 3
In a scientific conference, all participants can speak in total $2 \cdot n$ languages ($n \geq 2$). Each participant can speak exactly two languages and each pair of two participants can have at most one common language. It is known that for every integer $k$, $1 \leq k \leq n-1$ there are at most $k-1$ languages such that each of these languages is spoken by at most $k$ participants. Show that we can choose a group from $2 \cdot n$ participants which in total can speak $2 \cdot n$ languages and each language is spoken by exactly two participants from this group.
2009 Mexico National Olympiad, 3
At a party with $n$ people, it is known that among any $4$ people, there are either $3$ people who all know one another or $3$ people none of which knows another. Show that the $n$ people can be separated into two rooms, so that everyone in one room knows one another and no two people in the other room know each other.
2012 Mediterranean Mathematics Olympiad, 3
Consider a binary matrix $M$(all entries are $0$ or $1$) on $r$ rows and $c$ columns, where every row and every column contain at least one entry equal to $1$. Prove that there exists an entry $M(i,j) = 1$, such that the corresponding row-sum $R(i)$ and column-sum $C(j)$ satisfy $r R(i)\ge c C(j)$.
(Proposed by Gerhard Woeginger, Austria)
2001 Hungary-Israel Binational, 4
Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$.
(a) If $G_{n}$ does not contain $K_{2,3}$ , prove that $e(G_{n}) \leq\frac{n\sqrt{n}}{\sqrt{2}}+n$.
(b) Given $n \geq 16$ distinct points $P_{1}, . . . , P_{n}$ in the plane, prove that at most $n\sqrt{n}$ of the segments $P_{i}P_{j}$ have unit length.
2001 All-Russian Olympiad, 3
There are two families of convex polygons in the plane. Each family has a pair of disjoint polygons. Any polygon from one family intersects any polygon from the other family. Show that there is a line which intersects all the polygons.
2002 India IMO Training Camp, 12
Let $a,b$ be integers with $0<a<b$. A set $\{x,y,z\}$ of non-negative integers is [i]olympic[/i] if $x<y<z$ and if $\{z-y,y-x\}=\{a,b\}$. Show that the set of all non-negative integers is the union of pairwise disjoint olympic sets.
2004 CHKMO, 2
Let $ABCDEF$ regular hexagon of side length $1$ and $O$ is its center. In addition to the sides of the hexagon, line segments from $O$ to the every vertex are drawn, making as total of $12$ unit segments. Find the number paths of length $2003$ along these segments that star at $O$ and terminate at $O$.
2005 South East Mathematical Olympiad, 3
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$.
2010 Singapore Senior Math Olympiad, 5
Let $p$ be a prime number and let $a_1,a_2,\dots,a_k$ be distinct integers chosen from $1,2,\dots,p-1$. For $1\le i \le k$, let $f_i^{(n)}$ denote the remainder of the integer $na_1$ upon division by $p$, so $0\le f_i^{(n)}<p$. Define
$S=\{n:1\le n \le p-1,f_1^{(n)}<\dots<f_k^{(n)}\}$
Show that $S$ has less than $\frac{2p}{k+1}$ elements.
2007 Estonia Math Open Junior Contests, 5
In a school tennis tournament with $ m \ge 2$ participants, each match consists of 4 sets. A player who wins more than half of all sets during a match gets 2 points for this match. A player who wins exactly half of all sets during the match gets 1 point, and a player who wins less than half of all sets gets 0 points. During the tournament, each participant plays exactly one match against each remaining player. Find the least number of participants m for which it is possible that some participant wins more sets than any other participant but obtains less points than any other participant.
2007 Federal Competition For Advanced Students, Part 1, 3
Let $ M(n )\equal{}\{\minus{}1,\minus{}2,\ldots,\minus{}n\}$. For every non-empty subset of $ M(n )$ we consider the product of its elements. How big is the sum over all these products?
2013 Iran MO (3rd Round), 1
Assume that the following generating function equation is correct, prove the following statement:
$\Pi_{i=1}^{\infty} (1+x^{3i})\Pi_{j=1}^{\infty} (1-x^{6j+3})=1$
Statement: The number of partitions of $n$ to numbers not of the form $6k+1$ or $6k-1$ is equal to the number of partitions of $n$ in which each summand appears at least twice.
(10 points)
[i]Proposed by Morteza Saghafian[/i]
2009 Brazil National Olympiad, 1
Prove that there exists a positive integer $ n_0$ with the following property: for each integer $ n \geq n_0$ it is possible to partition a cube into $ n$ smaller cubes.
1989 China Team Selection Test, 3
$1989$ equal circles are arbitrarily placed on the table without overlap. What is the least number of colors are needed such that all the circles can be painted with any two tangential circles colored differently.
2013 ELMO Shortlist, 6
A $4\times4$ grid has its 16 cells colored arbitrarily in three colors. A [i]swap[/i] is an exchange between the colors of two cells. Prove or disprove that it always takes at most three swaps to produce a line of symmetry, regardless of the grid's initial coloring.
[i]Proposed by Matthew Babbitt[/i]
2007 Hong Kong TST, 4
[url=http://www.mathlinks.ro/Forum/viewtopic.php?t=107262]IMO 2007 HKTST 1[/url]
Problem 4
(a) Given five points on a plane such that no three of the points are collinear. Show that among the triangles which are drwan using any three of these five points as vertices, at least three of the triangles formed are not acute-angled triangles. (An acute-angled triangle is one in which all the three interior angles are acute angles.)
(b) Given any 100 points on a plane such that no three of the points are collinear. SHow that among the triangles which are drawn using any three of these 100 points as vertices, at least 30% of the trinagles are not acute-angled triangles.
2002 China Second Round Olympiad, 3
Before The World Cup tournament, the football coach of $F$ country will let seven players, $A_1, A_2, \ldots, A_7$, join three training matches (90 minutes each) in order to assess them. Suppose, at any moment during a match, one and only one of them enters the field, and the total time (which is measured in minutes) on the field for each one of $A_1, A_2, A_3$, and $A_4$ is divisible by $7$ and the total time for each of $A_5, A_6$, and $A_7$ is divisible by $13$. If there is no restriction about the number of substitutions of players during each match, then how many possible cases are there within the total time for every player on the field?
2007 Canada National Olympiad, 4
For two real numbers $ a$, $ b$, with $ ab\neq 1$, define the $ \ast$ operation by
\[ a\ast b=\frac{a+b-2ab}{1-ab}.\] Start with a list of $ n\geq 2$ real numbers whose entries $ x$ all satisfy $ 0<x<1$. Select any two numbers $ a$ and $ b$ in the list; remove them and put the number $ a\ast b$ at the end of the list, thereby reducing its length by one. Repeat this procedure until a single number remains.
$ a.$ Prove that this single number is the same regardless of the choice of pair at each stage.
$ b.$ Suppose that the condition on the numbers $ x$ is weakened to $ 0<x\leq 1$. What happens if the list contains exactly one $ 1$?
1995 Taiwan National Olympiad, 6
Let $a,b,c,d$ are integers such that $(a,b)=(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x_{1},x_{2})$ of rational numbers with $0\leq x_{1},x_{2}<1$ for which both $ax_{1}+bx_{2},cx_{1}+dx_{2}$ are integers.
2013 ELMO Shortlist, 10
Let $N\ge2$ be a fixed positive integer. There are $2N$ people, numbered $1,2,...,2N$, participating in a tennis tournament. For any two positive integers $i,j$ with $1\le i<j\le 2N$, player $i$ has a higher skill level than player $j$. Prior to the first round, the players are paired arbitrarily and each pair is assigned a unique court among $N$ courts, numbered $1,2,...,N$.
During a round, each player plays against the other person assigned to his court (so that exactly one match takes place per court), and the player with higher skill wins the match (in other words, there are no upsets). Afterwards, for $i=2,3,...,N$, the winner of court $i$ moves to court $i-1$ and the loser of court $i$ stays on court $i$; however, the winner of court 1 stays on court 1 and the loser of court 1 moves to court $N$.
Find all positive integers $M$ such that, regardless of the initial pairing, the players $2, 3, \ldots, N+1$ all change courts immediately after the $M$th round.
[i]Proposed by Ray Li[/i]
2013 Benelux, 1
Let $n \ge 3$ be an integer. A frog is to jump along the real axis, starting at the point $0$ and making $n$ jumps: one of length $1$, one of length $2$, $\dots$ , one of length $n$. It may perform these $n$ jumps in any order. If at some point the frog is sitting on a number $a \le 0$, its next jump must be to the right (towards the positive numbers). If at some point the frog is sitting on a number $a > 0$, its next jump must be to the left (towards the negative numbers). Find the largest positive integer $k$ for which the frog can perform its jumps in such an order that it never lands on any of the numbers $1, 2, \dots , k$.
2013 Iran MO (3rd Round), 3
$n$ cars are racing. At first they have a particular order. At each moment a car may overtake another car. No two overtaking actions occur at the same time, and except moments a car is passing another, the cars always have an order.
A set of overtaking actions is called "small" if any car overtakes at most once.
A set of overtaking actions is called "complete" if any car overtakes exactly once.
If $F$ is the set of all possible orders of the cars after a small set of overtaking actions and $G$ is the set of all possible orders of the cars after a complete set of overtaking actions, prove that
\[\mid F\mid=2\mid G\mid\]
(20 points)
[i]Proposed by Morteza Saghafian[/i]
2002 Vietnam Team Selection Test, 1
Let $n\geq 2$ be an integer and consider an array composed of $n$ rows and $2n$ columns. Half of the elements in the array are colored in red. Prove that for each integer $k$, $1<k\leq \dsp \left\lfloor \frac n2\right\rfloor+1$, there exist $k$ rows such that the array of size $k\times 2n$ formed with these $k$ rows has at least
\[ \frac { k! (n-2k+2) } {(n-k+1)(n-k+2)\cdots (n-1)} \] columns which contain only red cells.
2012 Regional Olympiad of Mexico Center Zone, 6
A board of $2n$ x $2n$ is colored chess style, a movement is the changing of colors of a $2$ x $2$ square. For what integers $n$ is possible to complete the board with one color using a finite number of movements?