Found problems: 1800
1998 Baltic Way, 17
Let $n$ and $k$ be positive integers. There are $nk$ objects (of the same size) and $k$ boxes, each of which can hold $n$ objects. Each object is coloured in one of $k$ different colours. Show that the objects can be packed in the boxes so that each box holds objects of at most two colours.
1985 IMO Longlists, 89
Given that $n$ elements $a_1, a_2,\dots, a_n$ are organized into $n$ pairs $P_1, P_2, \dots, P_n$ in such a way that two pairs $P_i, P_j$ share exactly one element when $(a_i, a_j)$ is one of the pairs, prove that every element is in exactly two of the pairs.
1993 All-Russian Olympiad, 4
Thirty people sit at a round table. Each of them is either smart or dumb. Each of them is asked: "Is your neighbor to the right smart or dumb?" A smart person always answers correctly, while a dumb person can answer both correctly and incorrectly. It is known that the number of dumb people does not exceed $F$. What is the largest possible value of $F$ such that knowing what the answers of the people are, you can point at at least one person, knowing he is smart?
2014 Dutch BxMO/EGMO TST, 5
Let $n$ be a positive integer. Daniel and Merlijn are playing a game. Daniel
has $k$ sheets of paper lying next to each other on a table, where $k$ is a
positive integer. On each of the sheets, he writes some of the numbers
from $1$ up to $n$ (he is allowed to write no number at all, or all numbers).
On the back of each of the sheets, he writes down the remaining numbers.
Once Daniel is finished, Merlijn can flip some of the sheets of paper (he is
allowed to flip no sheet at all, or all sheets). If Merlijn succeeds in making
all of the numbers from $1$ up to n visible at least once, then he wins.
Determine the smallest $k$ for which Merlijn can always win, regardless of
Daniel’s actions.
2012 Benelux, 4
Yesterday, $n\ge 4$ people sat around a round table. Each participant remembers only who his two neighbours were, but not necessarily which one sat on his left and which one sat on his right. Today, you would like the same people to sit around the same round table so that each participant has the same two neighbours as yesterday (it is possible that yesterday’s left-hand side neighbour is today’s right-hand side neighbour). You are allowed to query some of the participants: if anyone is asked, he will answer by pointing at his two neighbours from yesterday.
a) Determine the minimal number $f(n)$ of participants you have to query in order to be certain to succeed, if later questions must not depend on the outcome of the previous questions. That is, you have to choose in advance the list of people you are going to query, before effectively asking any question.
b) Determine the minimal number $g(n)$ of participants you have to query in order to be certain to succeed, if later questions may depend on the outcome of previous questions. That is, you can wait until you get the first answer to choose whom to ask the second question, and so on.
2009 Benelux, 3
Let $n\ge 1$ be an integer. In town $X$ there are $n$ girls and $n$ boys, and each girl knows each boy. In town $Y$ there are $n$ girls, $g_1,g_2,\ldots ,g_n$, and $2n-1$ boys, $b_1,b_2,\ldots ,b_{2n-1}$. For $i=1,2,\ldots ,n$, girl $g_i$ knows boys $b_1,b_2,\ldots ,b_{2i-1}$ and no other boys. Let $r$ be an integer with $1\le r\le n$. In each of the towns a party will be held where $r$ girls from that town and $r$ boys from the same town are supposed to dance with each other in $r$ dancing pairs. However, every girl only wants to dance with a boy she knows. Denote by $X(r)$ the number of ways in which we can choose $r$ dancing pairs from town $X$, and by $Y(r)$ the number of ways in which we can choose $r$ dancing pairs from town $Y$. Prove that $X(r)=Y(r)$ for $r=1,2,\ldots ,n$.
2012 Korea National Olympiad, 2
There are $n$ students $ A_1 , A_2 , \cdots , A_n $ and some of them shaked hands with each other. ($ A_i $ and $ A_j$ can shake hands more than one time.) Let the student $ A_i $ shaked hands $ d_i $ times. Suppose $ d_1 + d_2 + \cdots + d_n > 0 $. Prove that there exist $ 1 \le i < j \le n $ satisfying the following conditions:
(a) Two students $ A_i $ and $ A_j $ shaked hands each other.
(b) $ \frac{(d_1 + d_2 + \cdots + d_n ) ^2 }{n^2 } \le d_i d_j $
2009 Indonesia TST, 4
Sixteen people for groups of four people such that each two groups have at most two members in common. Prove that there exists a set of six people in which every group is not properly contained in it.
2009 Indonesia TST, 4
Sixteen people for groups of four people such that each two groups have at most two members in common. Prove that there exists a set of six people in which every group is not properly contained in it.
2006 Taiwan National Olympiad, 2
Ten test papers are to be prepared for the National Olympiad. Each paper has 4 problems, and no two papers have more than 1 problem in common. At least how many problems are needed?
2012 Iran MO (3rd Round), 4
Prove that from an $n\times n$ grid, one can find $\Omega (n^{\frac{5}{3}})$ points such that no four of them are vertices of a square with sides parallel to lines of the grid. Imagine yourself as Erdos (!) and guess what is the best exponent instead of $\frac{5}{3}$!
2009 Moldova Team Selection Test, 3
[color=darkblue]Weightlifter Ruslan has just finished the exercise with a weight, which has $ n$ small weights on one side and $ n$ on the another. At each stage he takes some weights from one of the sides, such that at any moment the difference of the numbers of weights on the sides does not exceed $ k$. What is the minimal number of stages (in function if $ n$ and $ k$), which Ruslan need to take off all weights..[/color]
1971 IMO Longlists, 40
Consider the set of grid points $(m,n)$ in the plane, $m,n$ integers. Let $\sigma$ be a finite subset and define
\[S(\sigma)=\sum_{(m,n)\in\sigma}(100-|m|-|n|) \]
Find the maximum of $S$, taken over the set of all such subsets $\sigma$.
2008 Romania Team Selection Test, 4
Prove that there exists a set $ S$ of $ n \minus{} 2$ points inside a convex polygon $ P$ with $ n$ sides, such that any triangle determined by $3$ vertices of $ P$ contains exactly one point from $ S$ inside or on the boundaries.
2019 Kazakhstan National Olympiad, 5
Given a checkered rectangle of size n × m. Is it always possible to mark $3$ or $4$ nodes of a rectangle so that at least one of the marked nodes lay on each straight line containing the side of the rectangle, and the non-self-intersecting polygon with vertices at these nodes has an area equal to
$$\dfrac{1}{2}\min \left ( \text{gcd}(n, m), \dfrac{n+m}{\text{gcd}(n, m)} \right)$$?
2004 Regional Olympiad - Republic of Srpska, 4
An $8\times8$ chessboard is completely tiled by $2\times1$ dominoes. Prove that there exist a king's tour
of that chessboard such that every cell of the board is visited exactly once and such that king goes domino by
domino, i.e. if king moves to the first cell of a domino, it must move to another cell in the next move. (King
doesn't have to come back to the initial cell. King is an usual chess piece.)
2010 Contests, 3
All sides and diagonals of a convex $n$-gon, $n\ge 3$, are coloured one of two colours. Show that there exist $\left[\frac{n+1}{3}\right]$ pairwise disjoint monochromatic segments.
[i](Two segments are disjoint if they do not share an endpoint or an interior point).[/i]
2002 Romania Team Selection Test, 3
There are $n$ players, $n\ge 2$, which are playing a card game with $np$ cards in $p$ rounds. The cards are coloured in $n$ colours and each colour is labelled with the numbers $1,2,\ldots ,p$. The game submits to the following rules:
[list]each player receives $p$ cards.
the player who begins the first round throws a card and each player has to discard a card of the same colour, if he has one; otherwise they can give an arbitrary card.
the winner of the round is the player who has put the greatest card of the same colour as the first one.
the winner of the round starts the next round with a card that he selects and the play continues with the same rules.
the played cards are out of the game.[/list]
Show that if all cards labelled with number $1$ are winners, then $p\ge 2n$.
[i]Barbu Berceanu[/i]
2014 Middle European Mathematical Olympiad, 3
Let $K$ and $L$ be positive integers. On a board consisting of $2K \times 2L$ unit squares an ant starts in the lower left corner square and walks to the upper right corner square. In each step it goes horizontally or vertically to a neighbouring square. It never visits a square twice. At the end some squares may remain unvisited.
In some cases the collection of all unvisited squares forms a single rectangle. In such cases, we call this rectangle [i]MEMOrable[/i].
Determine the number of different MEMOrable rectangles.
[i]Remark: Rectangles are different unless they consist of exactly the same squares.[/i]
2020 Baltic Way, 10
Alice and Bob are playing hide and seek. Initially, Bob chooses a secret fixed point $B$ in the unit square. Then Alice chooses a sequence of points $P_0, P_1, \ldots, P_N$ in the plane. After choosing $P_k$ (but before choosing $P_{k+1}$) for $k \geq 1$, Bob tells "warmer'' if $P_k$ is closer to $B$ than $P_{k-1}$, otherwise he says "colder''. After Alice has chosen $P_N$ and heard Bob's answer, Alice chooses a final point $A$. Alice wins if the distance $AB$ is at most $\frac 1 {2020}$, otherwise Bob wins. Show that if $N=18$, Alice cannot guarantee a win.
2020 Baltic Way, 8
Let $n$ be a given positive integer.
A restaurant offers a choice of $n$ starters, $n$ main dishes, $n$ desserts and $n$ wines.
A merry company dines at the restaurant, with each guest choosing a starter, a main dish, a dessert and a wine.
No two people place exactly the same order.
It turns out that there is no collection of $n$ guests such that their orders coincide in three of these aspects,
but in the fourth one they all differ. (For example, there are no $n$ people that order exactly the same three courses of food, but $n$ different wines.) What is the maximal number of guests?
2010 Contests, 1
For a finite non empty set of primes $P$, let $m(P)$ denote the largest possible number of consecutive positive integers, each of which is divisible by at least one member of $P$.
(i) Show that $|P|\le m(P)$, with equality if and only if $\min(P)>|P|$.
(ii) Show that $m(P)<(|P|+1)(2^{|P|}-1)$.
(The number $|P|$ is the size of set $P$)
[i]Dan Schwarz, Romania[/i]
2010 China Second Round Olympiad, 4
the code system of a new 'MO lock' is a regular $n$-gon,each vertex labelled a number $0$ or $1$ and coloured red or blue.it is known that for any two adjacent vertices,either their numbers or colours coincide.
find the number of all possible codes(in terms of $n$).
2011 Indonesia MO, 4
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.
2006 All-Russian Olympiad, 1
Given a $15\times 15$ chessboard. We draw a closed broken line without self-intersections such that every edge of the broken line is a segment joining the centers of two adjacent cells of the chessboard. If this broken line is symmetric with respect to a diagonal of the chessboard, then show that the length of the broken line is $\leq 200$.