Found problems: 1488
2014 Postal Coaching, 3
Fix positive integers $k$ and $n$.Derive a simple expression involving Fibonacci numbers for the number of sequences $(T_1,T_2,\ldots,T_k)$ of subsets $T_i$ of $[n]$ such that $T_1\subseteq T_2\supseteq T_3\subseteq T_4\supseteq\ldots$.
[color=#008000]Moderator says: and the original source for this one is Richard Stanley, [i]Enumerative Combinatorics[/i] vol. 1 (1st edition), exercise 1.15.[/color]
1994 Turkey MO (2nd round), 3
Let $n$ blue lines, no two of which are parallel and no three concurrent, be drawn on a plane. An intersection of two blue lines is called a blue point. Through any two blue points that have not already been joined by a blue line, a red line is drawn. An intersection of two red lines is called a red point, and an intersection of red line and a blue line is called a purple point. What is the maximum possible number of purple points?
2001 Kurschak Competition, 1
$3n-1$ points are given in the plane, no three are collinear. Prove that one can select $2n$ of them whose convex hull is not a triangle.
2002 Tournament Of Towns, 7
Some domino pieces are placed in a chain according to standard rules. In each move, we may remove a sub-chain with equal numbers at its ends, turn the whole sub-chain around, and put it back in the same place. Prove that for every two legal chains formed from the same pieces and having the same numbers at their ends, we can transform one to another in a finite sequence of moves.
2013 Baltic Way, 9
In a country there are $2014$ airports, no three of them lying on a line. Two airports are connected by a direct flight if and only if the line passing through them divides the country in two parts, each with $1006$ airports in it. Show that there are no two airports such that one can travel from the first to the second, visiting each of the $2014$ airports exactly once.
1976 IMO Longlists, 32
We consider the infinite chessboard covering the whole plane. In every field of the chessboard there is a nonnegative real number. Every number is the arithmetic mean of the numbers in the four adjacent fields of the chessboard. Prove that the numbers occurring in the fields of the chessboard are all equal.
2006 MOP Homework, 4
A $k$-coloring of a graph $G$ is a coloring of its vertices using $k$ possible colors such that the end points of any edge have different colors. We say a graph $G$ is uniquely $k$-colorable if one hand it has a $k$-coloring, on the other hand there do not exist vertices $u$ and $v$ such that $u$ and $v$ have the same color in one $k$-coloring and $u$ and $v$ have different colors in another $k$-coloring. Prove that if a graph $G$ with $n$ vertices $(n \ge 3)$ is uniquely $3$-colorable, then it has at least $2n-3$ edges.
1958 November Putnam, B2
Hi everybody!
I've an interesting problem!
Can you solve it?
Prove [b]Erdös-Ginzburg-Ziv Theorem[/b]: [i]"Among any $2n-1$ integers, there are some $n$ whose sum is divisible by $n$."[/i]
2019 Tournament Of Towns, 5
In each cell, a strip of length $100$ is worth a chip. You can change any $2$ neighboring chips and pay $1$ rouble, and you can also swap any $2$ chips for free, between which there are exactly $4$ chips. For what is the smallest amount of rubles you can rearrange chips in reverse order?
1998 All-Russian Olympiad, 4
A maze is an $8 \times 8$ board with some adjacent squares separated by walls, so that any two squares can be connected by a path not meeting any wall. Given a command LEFT, RIGHT, UP, DOWN, a pawn makes a step in the corresponding direction unless it encounters a wall or an edge of the chessboard. God writes a program consisting of a finite sequence of commands and gives it to the Devil, who then constructs a maze and places the pawn on one of the squares. Can God write a program which guarantees the pawn will visit every square despite the Devil's efforts?
2004 Tuymaada Olympiad, 1
50 knights of King Arthur sat at the Round Table. A glass of white or red wine stood before each of them. It is known that at least one glass of red wine and at least one glass of white wine stood on the table. The king clapped his hands twice. After the first clap every knight with a glass of red wine before him took a glass from his left neighbour. After the second clap every knight with a glass of white wine (and possibly something more) before him gave this glass to the left neughbour of his left neighbour. Prove that some knight was left without wine.
[i]Proposed by A. Khrabrov, incorrect translation from Hungarian[/i]
1989 China National Olympiad, 5
Given $1989$ points in the space, any three of them are not collinear. We divide these points into $30$ groups such that the numbers of points in these groups are different from each other. Consider those triangles whose vertices are points belong to three different groups among the $30$. Determine the numbers of points of each group such that the number of such triangles attains a maximum.
2007 All-Russian Olympiad, 3
Arutyun and Amayak show another effective trick. A spectator writes down on a board a sequence of $N$ (decimal) digits. Amayak closes two adjacent digits by a black disc. Then Arutyun comes and says both closed digits (and their order). For which minimal $N$ they may show such a trick?
[i]K. Knop, O. Leontieva[/i]
2009 Brazil National Olympiad, 3
There are $ 2009$ pebbles in some points $ (x,y)$ with both coordinates integer. A operation consists in choosing a point $ (a,b)$ with four or more pebbles, removing four pebbles from $ (a,b)$ and putting one pebble in each of the points
\[ (a,b\minus{}1),\ (a,b\plus{}1),\ (a\minus{}1,b),\ (a\plus{}1,b)\]
Show that after a finite number of operations each point will necessarily have at most three pebbles. Prove that the final configuration doesn't depend on the order of the operations.
1974 IMO Longlists, 52
A fox stands in the centre of the field which has the form of an equilateral triangle, and a rabbit stands at one of its vertices. The fox can move through the whole field, while the rabbit can move only along the border of the field. The maximal speeds of the fox and rabbit are equal to $u$ and $v$, respectively. Prove that:
(a) If $2u>v$, the fox can catch the rabbit, no matter how the rabbit moves.
(b) If $2u\le v$, the rabbit can always run away from the fox.
1996 Baltic Way, 18
The jury of an Olympiad has $30$ members in the beginning. Each member of the jury thinks that some of his colleagues are competent, while all the others are not, and these opinions do not change. At the beginning of every session a voting takes place, and those members who are not competent in the opinion of more than one half of the voters are excluded from the jury for the rest of the olympiad. Prove that after at most $15$ sessions there will be no more exclusions. (Note that nobody votes about his own competence.)
1988 Vietnam National Olympiad, 3
The plane is partitioned into congruent equilateral triangles such that any two of them which are not disjoint have either a common vertex or a common side. Is there a circle containing exactly 1988 points in its interior?
2010 Indonesia MO, 5
$m$ boys and $n$ girls ($m>n$) sat across a round table, supervised by a teacher, and they did a game, which went like this. At first, the teacher pointed a boy to start the game. The chosen boy put a coin on the table. Then, consecutively in a clockwise order, everyone did his turn. If the next person is a boy, he will put a coin to the existing pile of coins. If the next person is a girl, she will take a coin from the existing pile of coins. If there is no coin on the table, the game ends. Notice that depending on the chosen boy, the game could end early, or it could go for a full turn. If the teacher wants the game to go for at least a full turn, how many possible boys could be chosen?
[i]Hendrata Dharmawan, Boston, USA[/i]
2010 ISI B.Stat Entrance Exam, 10
There are $100$ people in a queue waiting to enter a hall. The hall has exactly $100$ seats numbered from $1$ to $100$. The first person in the queue enters the hall, chooses any seat and sits there. The $n$-th person in the queue, where $n$ can be $2, . . . , 100$, enters the hall after $(n-1)$-th person is seated. He sits in seat number $n$ if he finds it vacant; otherwise he takes any unoccupied seat. Find the total number of ways in which $100$ seats can be filled up, provided the $100$-th person occupies seat number $100$.
2004 All-Russian Olympiad, 4
A rectangular array has 9 rows and 2004 columns. In the 9 * 2004 cells of the table we place the numbers from 1 to 2004, each 9 times. And we do this in such a way that two numbers, which stand in exactly the same column in and differ around at most by 3. Find the smallest possible sum of all numbers in the first row.
2008 China Girls Math Olympiad, 1
[i](a)[/i] Determine if the set $ \{1,2,\ldots,96\}$ can be partitioned into 32 sets of equal size and equal sum.
[i](b)[/i] Determine if the set $ \{1,2,\ldots,99\}$ can be partitioned into 33 sets of equal size and equal sum.
1986 China Team Selection Test, 4
Mark $4 \cdot k$ points in a circle and number them arbitrarily with numbers from $1$ to $4 \cdot k$. The chords cannot share common endpoints, also, the endpoints of these chords should be among the $4 \cdot k$ points.
[b]i.[/b] Prove that $2 \cdot k$ pairwisely non-intersecting chords can be drawn for each of whom its endpoints differ in at most $3 \cdot k - 1$.
[b]ii.[/b] Prove that the $3 \cdot k - 1$ cannot be improved.
1997 Kurschak Competition, 3
Prove that the vertices of any planar graph can be colored with $3$ colors such that there is no monochromatic cycle.
2013 Iran MO (3rd Round), 4
A polygon $A$ that doesn't intersect itself and has perimeter $p$ is called [b]Rotund[/b] if for each two points $x,y$ on the sides of this polygon which their distance on the plane is less than $1$ their distance on the polygon is at most $\frac{p}{4}$. (Distance on the polygon is the length of smaller path between two points on the polygon)
Now we shall prove that we can fit a circle with radius $\frac{1}{4}$ in any rotund polygon.
The mathematicians of two planets earth and Tarator have two different approaches to prove the statement. In both approaches by "inner chord" we mean a segment with both endpoints on the polygon, and "diagonal" is an inner chord with vertices of the polygon as the endpoints.
[b]Earth approach: Maximal Chord[/b]
We know the fact that for every polygon, there exists an inner chord $xy$ with a length of at most 1 such that for any inner chord $x'y'$ with length of at most 1 the distance on the polygon of $x,y$ is more than the distance on the polygon of $x',y'$. This chord is called the [b]maximal chord[/b].
On the rotund polygon $A_0$ there's two different situations for maximal chord:
(a) Prove that if the length of the maximal chord is exactly $1$, then a semicircle with diameter maximal chord fits completely inside $A_0$, so we can fit a circle with radius $\frac{1}{4}$ in $A_0$.
(b) Prove that if the length of the maximal chord is less than one we still can fit a circle with radius $\frac{1}{4}$ in $A_0$.
[b]Tarator approach: Triangulation[/b]
Statement 1: For any polygon that the length of all sides is less than one and no circle with radius $\frac{1}{4}$ fits completely inside it, there exists a triangulation of it using diagonals such that no diagonal with length more than $1$ appears in the triangulation.
Statement 2: For any polygon that no circle with radius $\frac{1}{4}$ fits completely inside it, can be divided into triangles that their sides are inner chords with length of at most 1.
The mathematicians of planet Tarator proved that if the second statement is true, for each rotund polygon there exists a circle with radius $\frac{1}{4}$ that fits completely inside it.
(c) Prove that if the second statement is true, then for each rotund polygon there exists a circle with radius $\frac{1}{4}$ that fits completely inside it.
They found out that if the first statement is true then the second statement is also true, so they put a bounty of a doogh on proving the first statement. A young earth mathematician named J.N., found a counterexample for statement 1, thus receiving the bounty.
(d) Find a 1392-gon that is counterexample for statement 1.
But the Tarators are not disappointed and they are still trying to prove the second statement.
(e) (Extra points) Prove or disprove the second statement.
Time allowed for this problem was 150 minutes.
2007 Irish Math Olympiad, 4
Air Michael and Air Patrick operate direct flights connecting Belfast, Cork, Dublin, Galway, Limerick, and Waterord. For each pair of cities exactly one of the airlines operates the route (in both directions) connecting the cities. Prove that there are four cities for which one of the airlines operates a round trip. (Note that a round trip of four cities $ P,Q,R,$ and $ S$, is a journey that follows the path $ P \rightarrow Q \rightarrow R \rightarrow S \rightarrow P$.)