Found problems: 1800
2014 Iran MO (3rd Round), 2
In a tennis tournament there are participants from $n$ different countries. Each team consists of a coach and a player whom should settle in a hotel. The rooms considered for the settlement of coaches are different from players' ones. Each player wants to be in a room whose roommates are [b][u]all[/u][/b] from countries which have a defense agreement with the player's country. Conversely, each coach wants to be in a room whose roommates are [b][u]all[/u][/b] from countries which don't have a defense agreement with the coach's country. Find the minimum number of the rooms such that we can [u][b]always[/b][/u] grant everyone's desire.
[i]proposed by Seyed Reza Hosseini and Mohammad Amin Ghiasi[/i]
1973 Bundeswettbewerb Mathematik, 1
In a square of sidelength $7$, $51$ points are given. Show that there's a disk of radius $1$ covering at least $3$ of these points.
1990 IberoAmerican, 5
$A$ and $B$ are two opposite vertices of an $n \times n$ board. Within each small square of the board, the diagonal parallel to $AB$ is drawn, so that the board is divided in $2n^{2}$ equal triangles. A coin moves from $A$ to $B$ along the grid, and for every segment of the grid that it visits, a seed is put in each triangle that contains the segment as a side. The path followed by the coin is such that no segment is visited more than once, and after the coins arrives at $B$, there are exactly two seeds in each of the $2n^{2}$ triangles of the board. Determine all the values of $n$ for which such scenario is possible.
1997 Balkan MO, 2
Let $S = \{A_1,A_2,\ldots ,A_k\}$ be a collection of subsets of an $n$-element set $A$. If for any two elements $x, y \in A$ there is a subset $A_i \in S$ containing exactly one of the two elements $x$, $y$, prove that $2^k\geq n$.
[i]Yugoslavia[/i]
2011 All-Russian Olympiad, 3
A convex 2011-gon is drawn on the board. Peter keeps drawing its diagonals in such a way, that each newly drawn diagonal intersected no more than one of the already drawn diagonals. What is the greatest number of diagonals that Peter can draw?
2008 Junior Balkan Team Selection Tests - Romania, 1
From numbers $ 1,2,3,...,37$ we randomly choose 10 numbers. Prove that among these exist four distinct numbers, such that sum of two of them equals to the sum of other two.
2009 Italy TST, 3
Two persons, A and B, set up an incantation contest in which they spell incantations (i.e. a finite sequence of letters) alternately. They must obey the following rules:
i) Any incantation can appear no more than once;
ii) Except for the first incantation, any incantation must be obtained by permuting the letters of the last one before it, or deleting one letter from the last incantation before it;
iii)The first person who cannot spell an incantation loses the contest. Answer the following questions:
a) If A says '$STAGEPREIMO$' first, then who will win?
b) Let $M$ be the set of all possible incantations whose lengths (i.e. the numbers of letters in them) are $2009$ and containing only four letters $A,B,C,D$, each of them appearing at least once. Find the first incantation (arranged in dictionary order) in $M$ such that A has a winning strategy by starting with it.
2008 All-Russian Olympiad, 4
There are several scientists collaborating in Niichavo. During an $ 8$-hour working day, the scientists went to cafeteria, possibly several times.It is known that for every two scientist, the total time in which exactly one of them was in cafeteria is at least $ x$ hours ($ x>4$).
What is the largest possible number of scientist that could work in Niichavo that day,in terms of $ x$?
1987 IMO Longlists, 13
Let $A$ be an infinite set of positive integers such that every $n \in A$ is the product of at most $1987$ prime numbers. Prove that there is an infinite set $B \subset A$ and a number $p$ such that the greatest common divisor of any two distinct numbers in $B$ is $p.$
2021 Baltic Way, 8
We are given a collection of $2^{2^k}$ coins, where $k$ is a non-negative integer. Exactly one coin is fake.
We have an unlimited number of service dogs. One dog is sick but we do not know which one.
A test consists of three steps: select some coins from the collection of all coins; choose a service dog; the dog smells all of the selected coins at once.
A healthy dog will bark if and only if the fake coin is amongst them. Whether the sick dog will bark or not is random. \\
Devise a strategy to find the fake coin, using at most $2^k+k+2$ tests, and prove that it works.
2013 ELMO Shortlist, 9
Let $f_0$ be the function from $\mathbb{Z}^2$ to $\{0,1\}$ such that $f_0(0,0)=1$ and $f_0(x,y)=0$ otherwise. For each positive integer $m$, let $f_m(x,y)$ be the remainder when \[ f_{m-1}(x,y) + \sum_{j=-1}^{1} \sum_{k=-1}^{1} f_{m-1}(x+j,y+k) \] is divided by $2$.
Finally, for each nonnegative integer $n$, let $a_n$ denote the number of pairs $(x,y)$ such that $f_n(x,y) = 1$.
Find a closed form for $a_n$.
[i]Proposed by Bobby Shen[/i]
2006 Australia National Olympiad, 4
There are $n$ points on a circle, such that each line segment connecting two points is either red or blue.
$P_iP_j$ is red if and only if $P_{i+1} P_{j+1}$ is blue, for all distinct $i, j$ in $\left\{1, 2, ..., n\right\}$.
(a) For which values of $n$ is this possible?
(b) Show that one can get from any point on the circle to any other point, by doing a maximum of 3 steps, where one step is moving from a point to another point through a red segment connecting these points.
2011 APMO, 2
Five points $A_1,A_2,A_3,A_4,A_5$ lie on a plane in such a way that no three among them lie on a same straight line. Determine the maximum possible value that the minimum value for the angles $\angle A_iA_jA_k$ can take where $i, j, k$ are distinct integers between $1$ and $5$.
2001 Tuymaada Olympiad, 4
Unit square $ABCD$ is divided into $10^{12}$ smaller squares (not necessarily equal). Prove that the sum of perimeters of all the smaller squares having common points with diagonal $AC$ does not exceed 1500.
[i]Proposed by A. Kanel-Belov[/i]
2009 Miklós Schweitzer, 2
Let $ p_1,\dots,p_k$ be prime numbers, and let $ S$ be the set of those integers whose all prime divisors are among $ p_1,\dots,p_k$. For a finite subset $ A$ of the integers let us denote by $ \mathcal G(A)$ the graph whose vertices are the elements of $ A$, and the edges are those pairs $ a,b\in A$ for which $ a \minus{} b\in S$. Does there exist for all $ m\geq 3$ an $ m$-element subset $ A$ of the integers such that
(i) $ \mathcal G(A)$ is complete?
(ii) $ \mathcal G(A)$ is connected, but all vertices have degree at most 2?
2013 JBMO TST - Macedonia, 4
A regular hexagon with side length $ 1 $ is given. There are $ m $ points in its interior such that no $ 3 $ are collinear. The hexagon is divided into triangles (triangulated), such that every point of the $ m $ given and every vertex of the hexagon is a vertex of such a triangle. The triangles don't have common interior points. Prove that there exists a triangle with area not greater than $ \frac{3 \sqrt{3}}{4(m+2)}$.
2018 Serbia JBMO TST, 4
Two players are playing the following game.
They are alternatively putting blue and red coins on the board $2018$ by $2018$. If first player creates $n$ blue coins in a row or column, he wins. Second player wins if he can prevent it. Who will win if:
$a)n=4$;
$b)n=5$?
Note: first player puts only blue coins, and second only red.
2012 Indonesia MO, 4
Given $2012$ distinct points $A_1,A_2,\dots,A_{2012}$ on the Cartesian plane. For any permutation $B_1,B_2,\dots,B_{2012}$ of $A_1,A_2,\dots,A_{2012}$ define the [i]shadow[/i] of a point $P$ as follows: [i]Point $P$ is rotated by $180^{\circ}$ around $B_1$ resulting $P_1$, point $P_1$ is rotated by $180^{\circ}$ around $B_2$ resulting $P_2$, ..., point $P_{2011}$ is rotated by $180^{\circ}$ around $B_{2012}$ resulting $P_{2012}$. Then, $P_{2012}$ is called the shadow of $P$ with respect to the permutation $B_1,B_2,\dots,B_{2012}$.[/i]
Let $N$ be the number of different shadows of $P$ up to all permutations of $A_1,A_2,\dots,A_{2012}$. Determine the maximum value of $N$.
[i]Proposer: Hendrata Dharmawan[/i]
2006 Iran Team Selection Test, 1
We have $n$ points in the plane, no three on a line.
We call $k$ of them good if they form a convex polygon and there is no other point in the convex polygon.
Suppose that for a fixed $k$ the number of $k$ good points is $c_k$.
Show that the following sum is independent of the structure of points and only depends on $n$ :
\[ \sum_{i=3}^n (-1)^i c_i \]
2012 Indonesia TST, 2
The positive integers are colored with black and white such that:
- There exists a bijection from the black numbers to the white numbers,
- The sum of three black numbers is a black number, and
- The sum of three white numbers is a white number.
Find the number of possible colorings that satisfies the above conditions.
2014 China Team Selection Test, 5
Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord.
Note: The cycle of graph $G(V,E)$ is a set of distinct vertices ${v_1,v_2...,v_n}\subseteq V$, $v_iv_{i+1}\in E$ for all $1\leq i\leq n$ $(n\geq 3, v_{n+1}=v_1)$; a cycle containing a chord is the cycle ${v_1,v_2...,v_n}$, such that there exist $i,j, 1< i-j< n-1$, satisfying $v_iv_j\in E$.
2014 India National Olympiad, 6
Let $n>1$ be a natural number. Let $U=\{1,2,...,n\}$, and define $A\Delta B$ to be the set of all those elements of $U$ which belong to exactly one of $A$ and $B$. Show that $|\mathcal{F}|\le 2^{n-1}$, where $\mathcal{F}$ is a collection of subsets of $U$ such that for any two distinct elements of $A,B$ of $\mathcal{F}$ we have $|A\Delta B|\ge 2$. Also find all such collections $\mathcal{F}$ for which the maximum is attained.
2019 IMEO, 2
Consider some graph $G$ with $2019$ nodes. Let's define [i]inverting[/i] a vertex $v$ the following process: for every other vertex $u$, if there was an edge between $v$ and $u$, it is deleted, and if there wasn't, it is added. We want to minimize the number of edges in the graph by several [i]invertings[/i] (we are allowed to invert the same vertex several times). Find the smallest number $M$ such that we can always make the number of edges in the graph not larger than $M$, for any initial choice of $G$.
[i]Proposed by Arsenii Nikolaev, Anton Trygub (Ukraine)[/i]
2014 All-Russian Olympiad, 4
Given are $n$ pairwise intersecting convex $k$-gons on the plane. Any of them can be transferred to any other by a homothety with a positive coefficient. Prove that there is a point in a plane belonging to at least $1 +\frac{n-1}{2k}$ of these $k$-gons.
2005 Vietnam National Olympiad, 3
Let $A_1A_2A_3A_4A_5A_6A_7A_8$ be convex 8-gon (no three diagonals concruent).
The intersection of arbitrary two diagonals will be called "button".Consider the convex quadrilaterals formed by four vertices of $A_1A_2A_3A_4A_5A_6A_7A_8$ and such convex quadrilaterals will be called "sub quadrilaterals".Find the smallest $n$ satisfying:
We can color n "button" such that for all $i,k \in\{1,2,3,4,5,6,7,8\},i\neq k,s(i,k)$ are the same where $s(i,k)$ denote the number of the "sub quadrilaterals" has $A_i,A_k$ be the vertices and the intersection of two its diagonals is "button".