Found problems: 1800
2010 ELMO Shortlist, 3
2010 MOPpers are assigned numbers 1 through 2010. Each one is given a red slip and a blue slip of paper. Two positive integers, A and B, each less than or equal to 2010 are chosen. On the red slip of paper, each MOPper writes the remainder when the product of A and his or her number is divided by 2011. On the blue slip of paper, he or she writes the remainder when the product of B and his or her number is divided by 2011. The MOPpers may then perform either of the following two operations:
[list]
[*] Each MOPper gives his or her red slip to the MOPper whose number is written on his or her blue slip.
[*] Each MOPper gives his or her blue slip to the MOPper whose number is written on his or her red slip.[/list]
Show that it is always possible to perform some number of these operations such that each MOPper is holding a red slip with his or her number written on it.
[i]Brian Hamrick.[/i]
1971 Miklós Schweitzer, 7
Let $ n \geq 2$ be an integer, let $ S$ be a set of $ n$ elements, and let $ A_i , \; 1\leq i \leq m$, be distinct subsets of $ S$ of size at least $ 2$ such that \[ A_i \cap A_j \not\equal{} \emptyset, A_i \cap A_k \not\equal{} \emptyset, A_j \cap A_k \not\equal{} \emptyset, \;\textrm{imply}\ \;A_i \cap A_j \cap A_k \not\equal{} \emptyset \ .\] Show that $ m \leq 2^{n\minus{}1}\minus{}1$.
[i]P. Erdos[/i]
2011 China National Olympiad, 3
Let $A$ be a set consist of finite real numbers,$A_1,A_2,\cdots,A_n$ be nonempty sets of $A$, such that
[b](a)[/b] The sum of the elements of $A$ is $0,$
[b](b)[/b] For all $x_i \in A_i(i=1,2,\cdots,n)$,we have $x_1+x_2+\cdots+x_n>0$.
Prove that there exist $1\le k\le n,$ and $1\le i_1<i_2<\cdots<i_k\le n$, such that
\[|A_{i_1}\bigcup A_{i_2} \bigcup \cdots \bigcup A_{i_k}|<\frac{k}{n}|A|.\]
Where $|X|$ denote the numbers of the elements in set $X$.
2008 China Team Selection Test, 3
Determine the greatest positive integer $ n$ such that in three-dimensional space, there exist n points $ P_{1},P_{2},\cdots,P_{n},$ among $ n$ points no three points are collinear, and for arbitary $ 1\leq i < j < k\leq n$, $ P_{i}P_{j}P_{k}$ isn't obtuse triangle.
2002 Iran Team Selection Test, 2
$n$ people (with names $1,2,\dots,n$) are around a table. Some of them are friends. At each step 2 friend can change their place. Find a necessary and sufficient condition for friendship relation between them that with these steps we can always reach to all of posiible permutations.
2012 All-Russian Olympiad, 2
A regular $2012$-gon is inscribed in a circle. Find the maximal $k$ such that we can choose $k$ vertices from given $2012$ and construct a convex $k$-gon without parallel sides.
2005 Italy TST, 1
A stage course is attended by $n \ge 4$ students. The day before the final exam, each group of three students conspire against another student to throw him/her out of the exam. Prove that there is a student against whom there are at least $\sqrt[3]{(n-1)(n- 2)} $conspirators.
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$.
2010 Contests, 2
Exactly $4n$ numbers in set $A= \{ 1,2,3,...,6n \} $ of natural numbers painted in red, all other in blue.
Proved that exist $3n$ consecutive natural numbers from $A$, exactly $2n$ of which numbers is red.
2012 Indonesia TST, 3
Let $S$ be a subset of $\{1,2,3,4,5,6,7,8,9,10\}$. If $S$ has the property that the sums of three elements of $S$ are all different, find the maximum number of elements of $S$.
2002 Iran MO (3rd Round), 25
An ant walks on the interior surface of a cube, he moves on a straight line. If ant reaches to an edge the he moves on a straight line on cube's net. Also if he reaches to a vertex he will return his path.
a) Prove that for each beginning point ant can has infinitely many choices for his direction that its path becomes periodic.
b) Prove that if if the ant starts from point $A$ and its path is periodic, then for each point $B$ if ant starts with this direction, then his path becomes periodic.
2011 Pre-Preparation Course Examination, 2
We say that a covering of a $m\times n$ rectangle with dominos has a wall if there exists a horizontal or vertical line that splits the rectangle into two smaller rectangles and doesn't cut any of the dominos. prove that if these three conditions are satisfied:
[b]a)[/b] $mn$ is an even number
[b]b)[/b] $m\ge 5$ and $n\ge 5$
[b]c)[/b] $(m,n)\neq(6,6)$
then we can cover the rectangle with dominos in such a way that we have no walls. (20 points)
2013 Canadian Mathematical Olympiad Qualification Repechage, 4
Four boys and four girls each bring one gift to a Christmas gift exchange. On a sheet of paper, each boy randomly writes down the name of one girl, and each girl randomly writes down the name of one boy. At the same time, each person passes their gift to the person whose name is written on their sheet. Determine the probability that [i]both[/i] of these events occur:
[list]
[*] (i) Each person receives exactly one gift;
[*] (ii) No two people exchanged presents with each other (i.e., if $A$ gave his gift to $B$, then $B$ did not give her gift to $A$).[/list]
1995 All-Russian Olympiad, 7
There are three boxes of stones. Sisyphus moves stones one by one between the boxes. Whenever he moves a stone, Zeus gives him the number of coins that is equal to the difference between the number of stones in the box the stone was put in, and that in the box the stone was taken from (the moved stone does not count). If this difference is negative, then Sisyphus returns the corresponding amount to Zeus (if Sisyphus cannot pay, generous Zeus allows him to make the move and pay later).
After some time all the stones lie in their initial boxes. What is the greatest possible earning of Sisyphus at that moment?
[i]I. Izmest’ev[/i]
2013 Canadian Mathematical Olympiad Qualification Repechage, 7
Consider the following layouts of nine triangles with the letters $A, B, C, D, E, F, G, H, I$ in its interior.
[asy]
/* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki, go to User:Azjps/geogebra */
import graph; size(200);
real labelscalefactor = 0.5; /* changes label-to-point distance */
pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */
pen dotstyle = black; /* point style */
real xmin = 1.740000000000003, xmax = 8.400000000000013, ymin = 3.500000000000005, ymax = 9.360000000000012; /* image dimensions */
draw((5.020000000000005,8.820000000000011)--(2.560000000000003,4.580000000000005)--(7.461947712046029,4.569577506690286)--cycle);
/* draw figures */
draw((5.020000000000005,8.820000000000011)--(2.560000000000003,4.580000000000005));
draw((2.560000000000003,4.580000000000005)--(7.461947712046029,4.569577506690286));
draw((7.461947712046029,4.569577506690286)--(5.020000000000005,8.820000000000011));
draw((3.382989341689345,5.990838871467448)--(4.193333333333338,4.580000000000005));
draw((4.202511849578174,7.405966442513598)--(5.828619600041468,4.573707435672692));
draw((5.841878190157451,7.408513542990484)--(4.193333333333338,4.580000000000005));
draw((6.656214943659867,5.990342259816768)--(5.828619600041468,4.573707435672692));
draw((4.202511849578174,7.405966442513598)--(5.841878190157451,7.408513542990484));
draw((3.382989341689345,5.990838871467448)--(6.656214943659867,5.990342259816768));
label("\textbf{A}",(4.840000000000007,8.020000000000010),SE*labelscalefactor,fontsize(22));
label("\textbf{B}",(3.980000000000006,6.640000000000009),SE*labelscalefactor,fontsize(22));
label("\textbf{C}",(4.820000000000007,7.000000000000010),SE*labelscalefactor,fontsize(22));
label("\textbf{D}",(5.660000000000008,6.580000000000008),SE*labelscalefactor,fontsize(22));
label("\textbf{E}",(3.160000000000005,5.180000000000006),SE*labelscalefactor,fontsize(22));
label("\textbf{F}",(4.020000000000006,5.600000000000008),SE*labelscalefactor,fontsize(22));
label("\textbf{G}",(4.800000000000007,5.200000000000007),SE*labelscalefactor,fontsize(22));
label("\textbf{H}",(5.680000000000009,5.620000000000007),SE*labelscalefactor,fontsize(22));
label("\textbf{I}",(6.460000000000010,5.140000000000006),SE*labelscalefactor,fontsize(22));
/* dots and labels */
clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle);
/* end of picture */[/asy]
A sequence of letters, each letter chosen from$ A, B, C, D, E, F, G, H, I$ is said to be [i]triangle-friendly[/i] if the first and last letter of the sequence is $C$, and for every letter except the first letter, the triangle containing this letter shares an edge with the triangle containing the previous letter in the sequence. For example, the letter after $C$ must be either $A, B$, or $D$. For example, $CBF BC$ is triangle-friendly, but $CBF GH$ and $CBBHC$ are not.
[list]
[*] (a) Determine the number of triangle-friendly sequences with $2012$ letters.
[*] (b) Determine the number of triangle-friendly sequences with exactly $2013$ letters.[/list]
2002 Iran MO (3rd Round), 12
We have a bipartite graph $G$ (with parts $X$ and $Y$). We orient each edge arbitrarily. [i]Hessam[/i] chooses a vertex at each turn and reverse the orientation of all edges that $v$ is one of their endpoint. Prove that with these steps we can reach to a graph that for each vertex $v$ in part $X$, $\deg^{+}(v)\geq \deg^{-}(v)$ and for each vertex in part $Y$, $\deg^{+}v\leq \deg^{-}v$
2005 Kyiv Mathematical Festival, 3
Two players by turn paint the circles on the given picture each with his colour. At the end, the rest of the area of each of small triangles is painted by the colour of the majority of vertices of this triangle. The winner is one who gets larger area of his colour (the area of circles is taken into account). Does any of them have winning strategy? If yes, then who wins?
\[ \begin{picture}(60,60) \put(5,3){\put(3,0){\line(6,0){8}} \put(17,0){\line(6,0){8}} \put(31,0){\line(6,0){8}} \put(45,0){\line(6,0){8}} \put(10,14){\line(6,0){8}} \put(24,14){\line(6,0){8}} \put(38,14){\line(6,0){8}} \put(17,28){\line(6,0){8}} \put(31,28){\line(6,0){8}} \put(24,42){\line(6,0){8}} \put(1,2){\line(1,2){5}} \put(15,2){\line(1,2){5}} \put(29,2){\line(1,2){5}} \put(43,2){\line(1,2){5}} \put(8,16){\line(1,2){5}} \put(22,16){\line(1,2){5}} \put(36,16){\line(1,2){5}} \put(15,30){\line(1,2){5}} \put(29,30){\line(1,2){5}} \put(22,44){\line(1,2){5}} \put(13,2){\line( \minus{} 1,2){5}} \put(27,2){\line( \minus{} 1,2){5}} \put(41,2){\line( \minus{} 1,2){5}} \put(55,2){\line( \minus{} 1,2){5}} \put(20,16){\line( \minus{} 1,2){5}} \put(34,16){\line( \minus{} 1,2){5}} \put(48,16){\line( \minus{} 1,2){5}} \put(27,30){\line( \minus{} 1,2){5}} \put(41,30){\line( \minus{} 1,2){5}} \put(34,44){\line( \minus{} 1,2){5}} \put(0,0){\circle{6}} \put(14,0){\circle{6}} \put(28,0){\circle{6}} \put(42,0){\circle{6}} \put(56,0){\circle{6}} \put(7,14){\circle{6}} \put(21,14){\circle{6}} \put(35,14){\circle{6}} \put(49,14){\circle{6}} \put(14,28){\circle{6}} \put(28,28){\circle{6}} \put(42,28){\circle{6}} \put(21,42){\circle{6}} \put(35,42){\circle{6}} \put(28,56){\circle{6}}} \end{picture}\]
2014 Contests, 3
For even positive integer $n$ we put all numbers $1,2,...,n^2$ into the squares of an $n\times n$ chessboard (each number appears once and only once).
Let $S_1$ be the sum of the numbers put in the black squares and $S_2$ be the sum of the numbers put in the white squares. Find all $n$ such that we can achieve $\frac{S_1}{S_2}=\frac{39}{64}.$
2010 ITAMO, 5
In the land of Cockaigne, people play the following solitaire. It starts from a finite string of zeros and ones, and are granted the following moves:
(i) cancel each two consecutive ones;
(ii) delete three consecutive zeros;
(iii) if the substring within the string is $01$, one may replace this by substring $100$.
The moves (i), (ii) and (iii) must be made one at a time. You win if you can reduce the string to a string formed by two digits or less.
(For example, starting from $0101$, one can win using move (iii) first in the last two digits, resulting in $01100$, then playing the move (i) on two 'ones', and finally the move (ii) on the three zeros, one will get the empty string.)
Among all the $1024$ possible strings of ten-digit binary numbers, how many are there from which it is not possible to win the solitary?
2003 Iran MO (2nd round), 2
In a village, there are $n$ houses with $n>2$ and all of them are not collinear. We want to generate a water resource in the village. For doing this, point $A$ is [i]better[/i] than point $B$ if the sum of the distances from point $A$ to the houses is less than the sum of the distances from point $B$ to the houses. We call a point [i]ideal[/i] if there doesn’t exist any [i]better[/i] point than it. Prove that there exist at most $1$ [i]ideal[/i] point to generate the resource.
2024 All-Russian Olympiad, 5
A neighborhood consists of $10 \times 10$ squares. On New Year's Eve it snowed for the first time and since then exactly $10$ cm of snow fell on each square every night (and snow fell only at night). Every morning, the janitor selects one row or column and shovels all the snow from there onto one of the adjacent rows or columns (from each cell to the adjacent side). For example, he can select the seventh column and from each of its cells shovel all the snow into the cell of the left of it. You cannot shovel snow outside the neighborhood. On the evening of the 100th day of the year, an inspector will come to the city and find the cell with the snowdrift of maximal height. The goal of the janitor is to ensure that this height is minimal. What height of snowdrift will the inspector find?
[i]Proposed by A. Solynin[/i]
Oliforum Contest II 2009, 5
Define the function $ g(\cdot): \mathbb{Z} \to \{0,1\}$ such that $ g(n) \equal{} 0$ if $ n < 0$, and $ g(n) \equal{} 1$ otherwise. Define the function $ f(\cdot): \mathbb{Z} \to \mathbb{Z}$ such that $ f(n) \equal{} n \minus{} 1024g(n \minus{} 1024)$ for all $ n \in \mathbb{Z}$. Define also the sequence of integers $ \{a_i\}_{i \in \mathbb{N}}$ such that $ a_0 \equal{} 1$ e $ a_{n \plus{} 1} \equal{} 2f(a_n) \plus{} \ell$, where $ \ell \equal{} 0$ if $ \displaystyle \prod_{i \equal{} 0}^n{\left(2f(a_n) \plus{} 1 \minus{} a_i\right)} \equal{} 0$, and $ \ell \equal{} 1$ otherwise. How many distinct elements are in the set $ S: \equal{} \{a_0,a_1,\ldots,a_{2009}\}$?
[i](Paolo Leonetti)[/i]
2011 Canadian Mathematical Olympiad Qualification Repechage, 4
Alphonse and Beryl play a game starting with a blank blackboard. Alphonse goes first and the two players alternate turns. On Alphonse's first turn, he writes the integer $10^{2011}$ on the blackboard. On each subsequent turn, each player can do exactly one of the following two things:
[b](i)[/b] replace any number $x$ that is currently on the blackboard with two integers a and b greater than $1$ such that $x = ab,$ or
[b](ii)[/b] erase one or two copies of a number $y$ that appears at least twice on the blackboard.
Thus, there may be many numbers on the board at any time. The first player who cannot do either of these things loses. Determine which player has a winning strategy and explain the strategy.
2014 Silk Road, 1
What is the maximum number of coins can be arranged in cells of the table $n \times n$ (each cell is not more of the one coin) so that any coin was not simultaneously below and to the right than any other?
1996 All-Russian Olympiad, 6
Three sergeants and several solders serve in a platoon. The sergeants take turns on duty. The commander has given the following orders:
(a) Each day, at least one task must be issued to a soldier.
(b) No soldier may have more than two task or receive more than one tasks in a single day.
(c) The lists of soldiers receiving tasks for two different days must not be the same.
(d) The first sergeant violating any of these orders will be jailed.
Can at least one of the sergeants, without conspiring with the others, give tasks according to these rules and avoid being jailed?
[i]M. Kulikov[/i]