Found problems: 1800
2007 Tournament Of Towns, 4
Attached to each of a number of objects is a tag which states the correct mass of the object. The tags have fallen off and have been replaced on the objects at random. We wish to determine if by chance all tags are in fact correct. We may use exactly once a horizontal lever which is supported at its middle. The objects can be hung from the lever at any point on either side of the support. The lever either stays horizontal or tilts to one side. Is this task always possible?
2013 North Korea Team Selection Test, 2
Let $ a_1 , a_2 , \cdots , a_k $ be numbers such that $ a_i \in \{ 0,1,2,3 \} ( i= 1, 2, \cdots ,k) $. Let $ z = ( x_k , x_{k-1} , \cdots , x_1 )_4 $ be a base 4 expansion of $ z \in \{ 0, 1, 2, \cdots , 4^k -1 \} $. Define $ A $ as follows:
\[ A = \{ z | p(z)=z, z=0, 1, \cdots ,4^k-1 \}\]
where
\[ p(z) = \sum_{i=1}^{k} a_i x_i 4^{i-1} . \]
Prove that the number of elements in $ X $ is a power of 2.
2014 Contests, 1
Each of the integers from 1 to 4027 has been colored either green or red. Changing the color of a number is making it red if it was green and making it green if it was red. Two positive integers $m$ and $n$ are said to be [i]cuates[/i] if either $\frac{m}{n}$ or $\frac{n}{m}$ is a prime number. A [i]step[/i] consists in choosing two numbers that are cuates and changing the color of each of them. Show it is possible to apply a sequence of steps such that every integer from 1 to 2014 is green.
2010 Olympic Revenge, 5
Secco and Ramon are drunk in the real line over the integer points $a$ and $b$, respectively. Our real line is a little bit special, though: the interval $(-\infty, 0)$ is covered by a sea of lava. Being aware of this fact, and also because they are drunk, they decided to play the following game: initially they choose an integer number $k>1$ using a fair dice as large as desired, and therefore they start the game. In the first round, each player writes the point $h$ for which it wants to go.
After that, they throw a coin: if the result is heads, they go to the desired points; otherwise, they go to the points $2g - h$, where $g$ is the point where each of the players were in the precedent round (that is, in the first round $g = a$ for Secco and $g = b$ for Ramon). They repeat this procedure in the other rounds, and the game finishes when some of the player is over a point exactly $k$ times bigger than the other (if both of the player end up in the point $0$, the game finishes as well).
Determine, in values of $k$, the initial values $a$ and $b$ such that Secco and Ramon has a winning strategy to finish the game alive.
[i]Observation: If any of the players fall in the lave, he dies and both of them lose the game[/i]
2009 Middle European Mathematical Olympiad, 2
Suppose that we have $ n \ge 3$ distinct colours. Let $ f(n)$ be the greatest integer with the property that every side and every diagonal of a convex polygon with $ f(n)$ vertices can be coloured with one of $ n$ colours in the following way:
(i) At least two colours are used,
(ii) any three vertices of the polygon determine either three segments of the same colour or of three different colours.
Show that $ f(n) \le (n\minus{}1)^2$ with equality for infintely many values of $ n$.
1971 Bundeswettbewerb Mathematik, 2
The inhabitants of a planet speak a language only using the letters $A$ and $O$. To avoid mistakes, any two words of equal length differ at least on three positions. Show that there are not more than $\frac{2^n}{n+1}$ words with $n$ letters.
1997 All-Russian Olympiad, 4
An $n\times n\times n$ cube is divided into unit cubes. We are given a closed non-self-intersecting polygon (in space), each of whose sides joins the centers of two unit cubes sharing a common face. The faces of unit cubes which intersect the polygon are said to be distinguished. Prove that the edges of the unit cubes may be colored in two colors so that each distinguished face has an odd number of edges of each color, while each nondistinguished face has an even number of edges of each color.
[i]M. Smurov[/i]
2001 Hungary-Israel Binational, 3
Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$.
If $e(G_{n}) \geq\frac{n\sqrt{n}}{2}+\frac{n}{4}$ ,prove that $G_{n}$ contains $C_{4}$ .
2012 ELMO Problems, 2
Find all ordered pairs of positive integers $(m,n)$ for which there exists a set $C=\{c_1,\ldots,c_k\}$ ($k\ge1$) of colors and an assignment of colors to each of the $mn$ unit squares of a $m\times n$ grid such that for every color $c_i\in C$ and unit square $S$ of color $c_i$, exactly two direct (non-diagonal) neighbors of $S$ have color $c_i$.
[i]David Yang.[/i]
2009 Iran Team Selection Test, 6
We have a closed path on a vertices of a $ n$×$ n$ square which pass from each vertice exactly once . prove that we have two adjacent vertices such that if we cut the path from these points then length of each pieces is not less than quarter of total path .
2007 Italy TST, 1
We have a complete graph with $n$ vertices. We have to color the vertices and the edges in a way such that: no two edges pointing to the same vertice are of the same color; a vertice and an edge pointing him are coloured in a different way. What is the minimum number of colors we need?
1997 All-Russian Olympiad, 4
A polygon can be divided into 100 rectangles, but not into 99. Prove that it cannot be divided into 100 triangles.
[i]A. Shapovalov[/i]
2006 Iran MO (3rd Round), 6
The National Foundation of Happiness (NFoH) wants to estimate the happiness of people of country. NFoH selected $n$ random persons, and on every morning asked from each of them whether she is happy or not. On any two distinct days, exactly half of the persons gave the same answer. Show that after $k$ days, there were at most $n-\frac{n}{k}$ persons whose “yes” answers equals their “no” answers.
2004 Iran MO (3rd Round), 23
$ \mathcal F$ is a family of 3-subsets of set $ X$. Every two distinct elements of $ X$ are exactly in $ k$ elements of $ \mathcal F$. It is known that there is a partition of $ \mathcal F$ to sets $ X_1,X_2$ such that each element of $ \mathcal F$ has non-empty intersection with both $ X_1,X_2$. Prove that $ |X|\leq4$.
2009 All-Russian Olympiad Regional Round, 11.8
11 integers are placed along the circle. It is known that any two neighbors differ by at least 20 and sum of any two neighbors is no more than 100. Find the minimal possible sum of all numbers.
2011 Pre-Preparation Course Examination, 3
Calculate number of the hamiltonian cycles of the graph below: (15 points)
2004 Turkey MO (2nd round), 2
Two-way flights are operated between $80$ cities in such a way that each city is connected to at least $7$ other cities by a direct flight and any two cities are connected by a finite sequence of flights. Find the smallest $k$ such that for any such arrangement of flights it is possible to travel from any city to any other city by a sequence of at most $k$ flights.
2006 All-Russian Olympiad, 3
On a $49\times 69$ rectangle formed by a grid of lattice squares, all $50\cdot 70$ lattice points are colored blue. Two persons play the following game: In each step, a player colors two blue points red, and draws a segment between these two points. (Different segments can intersect in their interior.) Segments are drawn this way until all formerly blue points are colored red. At this moment, the first player directs all segments drawn - i. e., he takes every segment AB, and replaces it either by the vector $\overrightarrow{AB}$, or by the vector $\overrightarrow{BA}$. If the first player succeeds to direct all the segments drawn in such a way that the sum of the resulting vectors is $\overrightarrow{0}$, then he wins; else, the second player wins.
Which player has a winning strategy?
2014 Iran MO (3rd Round), 1
Denote by $g_n$ the number of connected graphs of degree $n$ whose vertices are labeled with numbers $1,2,...,n$. Prove that $g_n \ge (\frac{1}{2}).2^{\frac{n(n-1)}{2}}$.
[b][u]Note[/u][/b]:If you prove that for $c < \frac{1}{2}$, $g_n \ge c.2^{\frac{n(n-1)}{2}}$, you will earn some point!
[i]proposed by Seyed Reza Hosseini and Mohammad Amin Ghiasi[/i]
2010 Moldova Team Selection Test, 4
Let $ n\geq6$ be a even natural number. Prove that any cube can be divided in $ \dfrac{3n(n\minus{}2)}4\plus{}2$ cubes.
2009 Regional Competition For Advanced Students, 2
How many integer solutions $ (x_0$, $ x_1$, $ x_2$, $ x_3$, $ x_4$, $ x_5$, $ x_6)$ does the equation
\[ 2x_0^2\plus{}x_1^2\plus{}x_2^2\plus{}x_3^2\plus{}x_4^2\plus{}x_5^2\plus{}x_6^2\equal{}9\]
have?
2010 ELMO Shortlist, 8
A tree $T$ is given. Starting with the complete graph on $n$ vertices, subgraphs isomorphic to $T$ are erased at random until no such subgraph remains. For what trees does there exist a positive constant $c$ such that the expected number of edges remaining is at least $cn^2$ for all positive integers $n$?
[i]David Yang.[/i]
2007 Bulgaria National Olympiad, 2
Find the greatest positive integer $n$ such that we can choose $2007$ different positive integers from $[2\cdot 10^{n-1},10^{n})$ such that for each two $1\leq i<j\leq n$ there exists a positive integer $\overline{a_{1}a_{2}\ldots a_{n}}$ from the chosen integers for which $a_{j}\geq a_{i}+2$.
[i]A. Ivanov, E. Kolev[/i]
2010 China Western Mathematical Olympiad, 3
Determine all possible values of positive integer $n$, such that there are $n$ different 3-element subsets $A_1,A_2,...,A_n$ of the set $\{1,2,...,n\}$, with $|A_i \cap A_j| \not= 1$ for all $i \not= j$.
1979 IMO Longlists, 2
For a finite set $E$ of cardinality $n \geq 3$, let $f(n)$ denote the maximum number of $3$-element subsets of $E$, any two of them having exactly one common element. Calculate $f(n)$.