Found problems: 1488
2004 India IMO Training Camp, 3
The game of $pebbles$ is played on an infinite board of lattice points $(i,j)$. Initially there is a $pebble$ at $(0,0)$. A move consists of removing a $pebble$ from point $(i,j)$and placing a $pebble$ at each of the points $(i+1,j)$ and $(i,j+1)$ provided both are vacant. Show taht at any stage of the game there is a $pebble$ at some lattice point $(a,b)$ with $0 \leq a+b \leq 3$
2002 Turkey MO (2nd round), 3
Graph Airlines $ (GA)$ operates flights between some of the cities of the Republic of Graphia. There are at least three $ GA$ flights from each city, and it is possible to travel from any city in Graphia to any city in Graphia using $ GA$ flights. $ GA$ decides to discontinue some of its flights. Show that this can be done in such a way that it is still possible to travel between any two cities using $ GA$ flights, yet at least $ 2/9$ of the cities have only one flight.
2011 Kyrgyzstan National Olympiad, 6
[b]a)[/b] Among the $21$ pairwise distances between the $7$ points of the plane, prove that one and the same number occurs not more than $12$ times.
[b]b)[/b] Find a maximum number of times may meet the same number among the $15$ pairwise distances between $6$ points of the plane.
2007 ISI B.Stat Entrance Exam, 8
The following figure shows a $3^2 \times 3^2$ grid divided into $3^2$ subgrids of size $3 \times 3$. This grid has $81$ cells, $9$ in each subgrid.
[asy]
draw((0,0)--(9,0)--(9,9)--(0,9)--cycle, linewidth(2));
draw((0,1)--(9,1));
draw((0,2)--(9,2));
draw((0,3)--(9,3), linewidth(2));
draw((0,4)--(9,4));
draw((0,5)--(9,5));
draw((0,6)--(9,6), linewidth(2));
draw((0,7)--(9,7));
draw((0,8)--(9,8));
draw((1,0)--(1,9));
draw((2,0)--(2,9));
draw((3,0)--(3,9), linewidth(2));
draw((4,0)--(4,9));
draw((5,0)--(5,9));
draw((6,0)--(6,9), linewidth(2));
draw((7,0)--(7,9));
draw((8,0)--(8,9));
[/asy]
Now consider an $n^2 \times n^2$ grid divided into $n^2$ subgrids of size $n \times n$. Find the number of ways in which you can select $n^2$ cells from this grid such that there is exactly one cell coming from each subgrid, one from each row and one from each column.
1999 Kurschak Competition, 3
We are given more than $2^k$ integers, where $k\in\mathbb{N}$. Prove that we can choose $k+2$ of them such that if some of our selected numbers satisfy
\[x_1+x_2+\dots+x_m=y_1+y_2+\dots+y_m\]
where $x_1<\dots<x_m$ and $y_1<\dots<y_m$, then $x_i=y_i$ for any $1\le i\le m$.
2012 Korea - Final Round, 3
Let $M$ be the set of positive integers which do not have a prime divisor greater than 3. For any infinite family of subsets of $M$, say $A_1,A_2,\ldots $, prove that there exist $i\ne j$ such that for each $x\in A_i$ there exists some $y\in A_j $ such that $y\mid x$.
2003 Tournament Of Towns, 2
Smallville is populated by unmarried men and women, some of them are acquainted. Two city’s matchmakers are aware of all acquaintances. Once, one of matchmakers claimed: “I could arrange that every brunette man would marry a woman he was acquainted with”. The other matchmaker claimed “I could arrange that every blonde woman would marry a man she was acquainted with”. An amateur mathematician overheard their conversation and said “Then both arrangements could be done at the same time! ” Is he right?
1999 Vietnam Team Selection Test, 3
Let a regular polygon with $p$ vertices be given, where $p$ is an odd prime number. At every vertex there is one monkey. An owner of monkeys takes $p$ peanuts, goes along the perimeter of polygon clockwise and delivers to the monkeys by the following rule: Gives the first peanut for the leader, skips the two next vertices and gives the second peanut to the monkey at the next vertex; skip four next vertices gives the second peanut for the monkey at the next vertex ... after giving the $k$-th peanut, he skips the $2 \cdot k$ next vertices and gives $k+1$-th for the monkey at the next vertex. He does so until all $p$ peanuts are delivered.
[b]I.[/b] How many monkeys are there which does not receive peanuts?
[b]II.[/b] How many edges of polygon are there which satisfying condition: both two monkey at its vertex received peanut(s)?
1986 IMO Longlists, 39
Let $S$ be a $k$-element set.
[i](a)[/i] Find the number of mappings $f : S \to S$ such that
\[\text{(i) } f(x) \neq x \text{ for } x \in S, \quad \text{(ii) } f(f(x)) = x \text{ for }x \in S.\]
[i](b)[/i] The same with the condition $\text{(i)}$ left out.
2014 Contests, 1
Numbers $1$ through $2014$ are written on a board. A valid operation is to erase two numbers $a$ and $b$ on the board and replace them with the greatest common divisor and the least common multiple of $a$ and $b$.
Prove that, no matter how many operations are made, the sum of all the numbers that remain on the board is always larger than $2014$ $\times$ $\sqrt[2014]{2014!}$
2004 USAMO, 4
Alice and Bob play a game on a 6 by 6 grid. On his or her turn, a player chooses a rational number not yet appearing in the grid and writes it in an empty square of the grid. Alice goes first and then the players alternate. When all squares have numbers written in them, in each row, the square with the greatest number in that row is colored black. Alice wins if she can then draw a line from the top of the grid to the bottom of the grid that stays in black squares, and Bob wins if she can't. (If two squares share a vertex, Alice can draw a line from one to the other that stays in those two squares.) Find, with proof, a winning strategy for one of the players.
1988 IMO Longlists, 5
Let $k$ be a positive integer and $M_k$ the set of all the integers that are between $2 \cdot k^2 + k$ and $2 \cdot k^2 + 3 \cdot k,$ both included. Is it possible to partition $M_k$ into 2 subsets $A$ and $B$ such that
\[ \sum_{x \in A} x^2 = \sum_{x \in B} x^2. \]
2003 Vietnam Team Selection Test, 2
Let $A$ be the set of all permutations $a = (a_1, a_2, \ldots, a_{2003})$ of the 2003 first positive integers such that each permutation satisfies the condition: there is no proper subset $S$ of the set $\{1, 2, \ldots, 2003\}$ such that $\{a_k | k \in S\} = S.$
For each $a = (a_1, a_2, \ldots, a_{2003}) \in A$, let $d(a) = \sum^{2003}_{k=1} \left(a_k - k \right)^2.$
[b]I.[/b] Find the least value of $d(a)$. Denote this least value by $d_0$.
[b]II.[/b] Find all permutations $a \in A$ such that $d(a) = d_0$.
2007 Korea National Olympiad, 1
Consider the string of length $ 6$ composed of three characters $ a$, $ b$, $ c$. For each string, if two $ a$s are next to each other, or two $ b$s are next to each other, then replace $ aa$ by $ b$, and replace $ bb$ by $ a$. Also, if $ a$ and $ b$ are next to each other, or two $ c$s are next to each other, remove all two of them (i.e. delete $ ab$, $ ba$, $ cc$). Determine the number of strings that can be reduced to $ c$, the string of length 1, by the reducing processes mentioned above.
2003 APMO, 5
Given two positive integers $m$ and $n$, find the smallest positive integer $k$ such that among any $k$ people, either there are $2m$ of them who form $m$ pairs of mutually acquainted people or there are $2n$ of them forming $n$ pairs of mutually unacquainted people.
2008 Germany Team Selection Test, 2
Tracey baked a square cake whose surface is dissected in a $ 10 \times 10$ grid. In some of the fields she wants to put a strawberry such that for each four fields that compose a rectangle whose edges run in parallel to the edges of the cake boundary there is at least one strawberry. What is the minimum number of required strawberries?
1990 IMO Longlists, 50
During the class interval, $n$ children sit in a circle and play the game described below. The teacher goes around the children clockwisely and hands out candies to them according to the following regulations: Select a child, give him a candy; and give the child next to the first child a candy too; then skip over one child and give next child a candy; then skip over two children; give the next child a candy; then skip over three children; give the next child a candy;...
Find the value of $n$ for which the teacher can ensure that every child get at least one candy eventually (maybe after many circles).
1995 Polish MO Finals, 1
How many subsets of $\{1, 2, ... , 2n\}$ do not contain two numbers with sum $2n+1$?
2016 239 Open Mathematical Olympiad, 8
There are $n$ triangles inscribed in a circle and all $3n$ of their vertices are different. Prove that it is possible to put a boy in one of the vertices in each triangle, and a girl in the other, so that boys and girls alternate on a circle.
1996 Irish Math Olympiad, 5
The following game is played on a rectangular chessboard $ 5 \times 9$ (with five rows and nine columns). Initially, a number of discs are randomly placed on some of the squares of the chessboard, with at most one disc on each square. A complete move consists of the moving every disc subject to the following rules:
$ (1)$ Each disc may be moved one square up, down, left or right;
$ (2)$ If a particular disc is moved up or down as part of a complete move, then it must be moved left or right in the next complete move;
$ (3)$ If a particular disc is moved left or right as part of a complete move, then it must be moved up or down in the next complete move;
$ (4)$ At the end of a complete move, no two discs can be on the same square.
The game stops if it becomes impossible to perform a complete move. Prove that if initially $ 33$ discs are placed on the board then the game must eventually stop. Prove also that it is possible to place $ 32$ discs on the boards in such a way that the game could go on forever.
1991 China National Olympiad, 3
There are $10$ birds on the ground. For any $5$ of them, there are at least $4$ birds on a circle. Determine the least possible number of birds on the circle with the most birds.
2014 China Girls Math Olympiad, 3
There are $ n$ students; each student knows exactly $d $ girl students and $d $ boy students ("knowing" is a symmetric relation). Find all pairs $ (n,d) $ of integers .
2014 Iran Team Selection Test, 5
Given a set $X=\{x_1,\ldots,x_n\}$ of natural numbers in which for all $1< i \leq n$ we have $1\leq x_i-x_{i-1}\leq 2$, call a real number $a$ [b]good[/b] if there exists $1\leq j \leq n$ such that $2|x_j-a|\leq 1$. Also a subset of $X$ is called [b]compact[/b] if the average of its elements is a good number.
Prove that at least $2^{n-3}$ subsets of $X$ are compact.
[i]Proposed by Mahyar Sefidgaran[/i]
2008 Kyiv Mathematical Festival, 2
Aladdin has a set of coins with weights $ 1, 2, \ldots, 20$ grams. He can ask Genie about any two coins from the set which one is heavier, but he should pay Genie some other coin from the set before. (So, with every question the set of coins becomes smaller.) Can Aladdin find two coins from the set with total weight at least $ 28$ grams?
2000 IberoAmerican, 3
A convex hexagon is called [i]pretty[/i] if it has four diagonals of length 1, such that their endpoints are all the vertex of the hexagon.
($a$) Given any real number $k$ with $0<k<1$ find a [i]pretty[/i] hexagon with area equal to $k$
($b$) Show that the area of any [i]pretty[/i] hexagon is less than 1.