Found problems: 1488
1988 IMO Longlists, 19
Let $Z_{m,n}$ be the set of all ordered pairs $(i,j)$ with $i \in {1, \ldots, m}$ and $j \in {1, \ldots, n}.$ Also let $a_{m,n}$ be the number of all those subsets of $Z_{m,n}$ that contain no 2 ordered pairs $(i_1,j_1)$ and $(i_2,j_2)$ with $|i_1 - i_2| + |j_1 - j_2| = 1.$ Then show, for all positive integers $m$ and $k,$ that \[ a^2_{m, 2 \cdot k} \leq a_{m, 2 \cdot k - 1} \cdot a_{m, 2 \cdot k + 1}. \]
2006 Bulgaria National Olympiad, 3
The natural numbers are written in sequence, in increasing order, and by this we get an infinite sequence of digits. Find the least natural $k$, for which among the first $k$ digits of this sequence, any two nonzero digits have been written a different number of times.
[i]Aleksandar Ivanov, Emil Kolev [/i]
2006 Estonia Math Open Senior Contests, 4
Martin invented the following algorithm. Let two irreducible fractions $ \frac{s_1}{t_1}$ and $ \frac{s_2}{t_2}$ be given as inputs, with the numerators and denominators being positive integers. Divide $ s_1$ and $ s_2$ by their greatest common divisor $ c$ and obtain $ a_1$ and $ a_2$, respectively. Similarily, divide $ t_1$ and $ t_2$ by their greatest common divisor $ d$ and obtain $ b_1$ and $ b_2$, respectively. After that, form a new fraction $ \frac{a_1b_2 \plus{} a_2b_1}{t_1b_2}$, reduce it, and multiply the numerator of the result by $ c$. Martin claims that this algorithm always finds the sum of the original fractions as an irreducible fraction. Is his claim correct?
2009 Tournament Of Towns, 2
Mike has $1000$ unit cubes. Each has $2$ opposite red faces, $2$ opposite blue faces and $2$ opposite white faces. Mike assembles them into a $10 \times 10 \times 10$ cube. Whenever two unit cubes meet face to face, these two faces have the same colour. Prove that an entire face of the $10 \times 10 \times 10$ cube has the same colour.
[i](6 points)[/i]
2009 Croatia Team Selection Test, 2
Every natural number is coloured in one of the $ k$ colors. Prove that there exist four distinct natural numbers $ a, b, c, d$, all coloured in the same colour, such that $ ad \equal{} bc$, $ \displaystyle \frac b a$ is power of 2 and $ \displaystyle \frac c a$ is power of 3.
2013 CentroAmerican, 2
Around a round table the people $P_1, P_2,..., P_{2013}$ are seated in a clockwise order. Each person starts with a certain amount of coins (possibly none); there are a total of $10000$ coins. Starting with $P_1$ and proceeding in clockwise order, each person does the following on their turn:
[list][*]If they have an even number of coins, they give all of their coins to their neighbor to the left.
[*]If they have an odd number of coins, they give their neighbor to the left an odd number of coins (at least $1$ and at most all of their coins) and keep the rest.[/list]
Prove that, repeating this procedure, there will necessarily be a point where one person has all of the coins.
2011 India IMO Training Camp, 3
A set of $n$ distinct integer weights $w_1,w_2,\ldots, w_n$ is said to be [i]balanced[/i] if after removing any one of weights, the remaining $(n-1)$ weights can be split into two subcollections (not necessarily with equal size)with equal sum.
$a)$ Prove that if there exist [i]balanced[/i] sets of sizes $k,j$ then also a [i]balanced[/i] set of size $k+j-1$.
$b)$ Prove that for all [i]odd[/i] $n\geq 7$ there exist a [i]balanced[/i] set of size $n$.
2008 Kurschak Competition, 3
In a far-away country, travel between cities is only possible by bus or by train. One can travel by train or by bus between only certain cities, and there are not necessarily rides in both directions. We know that for any two cities $A$ and $B$, one can reach $B$ from $A$, [i]or[/i] $A$ from $B$ using only bus, or only train rides. Prove that there exists a city such that any other city can be reached using only one type of vehicle (but different cities may be reached with different vehicles).
2006 Korea - Final Round, 3
Three schools $A, B$ and $C$ , each with five players denoted $a_{i}, b_{i}, c_{i}$ respectively, take part in a chess tournament. The tournament is held following the rules:
(i) Players from each school have matches in order with respect to indices, and defeated players are eliminated; the first match is between $a_{1}$ and $b_{1}$.
(ii) If $y_{j}\in Y$ defeats $x_{i}\in X$ , his next opponent should be from the remaining school if not all of its players are eliminated; otherwise his next oponent is $x_{i+1}$ . The tournament is over when two schools are completely eliminated.
(iii) When $x_{i}$ wins a match, its school wins $10^{i-1}$ points.
At the end of the tournament, schools $A, B, C$ scored $P_{A}, P_{B}, P_{C}$ respectively. Find the remainder of the number of possible triples $(P_{A}, P_{B}, P_{C})$ upon division by $8.$
2001 China Western Mathematical Olympiad, 4
We call $ A_1, A_2, \ldots, A_n$ an $ n$-division of $ A$ if
(i) $ A_1 \cap A_2 \cap \cdots \cap A_n \equal{} A$,
(ii) $ A_i \cap A_j \neq \emptyset$.
Find the smallest positive integer $ m$ such that for any $ 14$-division $ A_1, A_2, \ldots, A_{14}$ of $ A \equal{} \{1, 2, \ldots, m\}$, there exists a set $ A_i$ ($ 1 \leq i \leq 14$) such that there are two elements $ a, b$ of $ A_i$ such that $ b < a \leq \frac {4}{3}b$.
2003 Tournament Of Towns, 3
In a tournament, each of $15$ teams played with each other exactly once. Let us call the game “[i]odd[/i]” if the total number of games previously played by both competing teams was odd.
[b](a)[/b] Prove that there was at least one “[i]odd[/i]” game.
[b](b)[/b] Could it happen that there was exactly one “[i]odd[/i]” game?
2009 Tuymaada Olympiad, 3
An arrangement of chips in the squares of $ n\times n$ table is called [i]sparse[/i] if every $ 2\times 2$ square contains at most 3 chips. Serge put chips in some squares of the table (one in a square) and obtained a sparse arrangement. He noted however that if any chip is moved to any free square then the arrangement is no more sparce. For what $ n$ is this possible?
[i]Proposed by S. Berlov[/i]
2003 India IMO Training Camp, 6
A zig-zag in the plane consists of two parallel half-lines connected by a line segment. Find $z_n$, the maximum number of regions into which $n$ zig-zags can divide the plane. For example, $z_1=2,z_2=12$(see the diagram). Of these $z_n$ regions how many are bounded? [The zig-zags can be as narrow as you please.] Express your answers as polynomials in $n$ of degree not exceeding $2$.
[asy]
draw((30,0)--(-70,0), Arrow);
draw((30,0)--(-20,-40));
draw((-20,-40)--(80,-40), Arrow);
draw((0,-60)--(-40,20), dashed, Arrow);
draw((0,-60)--(0,15), dashed);
draw((0,15)--(40,-65),dashed, Arrow);
[/asy]
2000 All-Russian Olympiad, 6
On some cells of a $2n \times 2n$ board are placed white and black markers (at most one marker on every cell). We first remove all black markers which are in the same column with a white marker, then remove all white markers which are in the same row with a black one. Prove that either the number of remaining white markers or that of remaining black markers does not exceed $n^2$.
1998 All-Russian Olympiad Regional Round, 9.8
The endpoints of a compass are at two lattice points of an infinite unit square
grid. It is allowed to rotate the compass around one of its endpoints, not varying
its radius, and thus move the other endpoint to another lattice point. Can the
endpoints of the compass change places after several such steps?
2010 Mexico National Olympiad, 1
Let $n$ be a positive integer. In an $n\times4$ table, each row is equal to
\[\begin{tabular}{| c | c | c | c |}
\hline
2 & 0 & 1 & 0 \\
\hline
\end{tabular}\]
A [i]change[/i] is taking three consecutive boxes in the same row with different digits in them and changing the digits in these boxes as follows:
\[0\to1\text{, }1\to2\text{, }2\to0\text{.}\]
For example, a row $\begin{tabular}{| c | c | c | c |}\hline 2 & 0 & 1 & 0 \\ \hline\end{tabular}$ can be changed to the row $\begin{tabular}{| c | c | c | c |}\hline 0 & 1 & 2 & 0 \\ \hline\end{tabular}$ but not to $\begin{tabular}{| c | c | c | c |}\hline 2 & 1 & 2 & 1 \\ \hline\end{tabular}$ because $0$, $1$, and $0$ are not distinct.
Changes can be applied as often as wanted, even to items already changed. Show that for $n<12$, it is not possible to perform a finite number of changes so that the sum of the elements in each column is equal.
1999 Finnish National High School Mathematics Competition, 5
An ordinary domino tile can be identifi ed as a pair $(k,m)$ where numbers $k$ and $m$ can get values $0, 1, 2, 3, 4, 5$ and $6.$
Pairs $(k,m)$ and $(m, k)$ determine the same tile. In particular, the pair $(k, k)$ determines one tile.
We say that two domino tiles [i]match[/i], if they have a common component.
[i]Generalized n-domino tiles[/i] $m$ and $k$ can get values $0, 1,... , n.$
What is the probability that two randomly chosen $n$-domino tiles match?
2005 China Team Selection Test, 3
Let $n$ be a positive integer, set $S_n = \{ (a_1,a_2,\cdots,a_{2^n}) \mid a_i=0 \ \text{or} \ 1, 1 \leq i \leq 2^n\}$. For any two elements $a=(a_1,a_2,\cdots,a_{2^n})$ and $b=(b_1,b_2,\cdots,b_{2^n})$ of $S_n$, define
\[ d(a,b)= \sum_{i=1}^{2^n} |a_i - b_i| \]
We call $A \subseteq S_n$ a $\textsl{Good Subset}$ if $d(a,b) \geq 2^{n-1}$ holds for any two distinct elements $a$ and $b$ of $A$. How many elements can the $\textsl{Good Subset}$ of $S_n$ at most have?
2007 All-Russian Olympiad, 3
Two players by turns draw diagonals in a regular $(2n+1)$-gon ($n>1$). It is forbidden to draw a diagonal, which was already drawn, or intersects an odd number of already drawn diagonals. The player, who has no legal move, loses. Who has a winning strategy?
[i]K. Sukhov[/i]
2003 China Team Selection Test, 1
Let $S$ be the set of points inside and on the boarder of a regular haxagon with side length 1. Find the least constant $r$, such that there exists one way to colour all the points in $S$ with three colous so that the distance between any two points with same colour is less than $r$.
2010 Tuymaada Olympiad, 4
In a country there are $4^9$ schoolchildren living in four cities. At the end of the school year a state examination was held in 9 subjects. It is known that any two students have different marks at least in one subject. However, every two students from the same city got equal marks at least in one subject. Prove that there is a subject such that every two children living in the same city have equal marks in this subject.
[i]Fedor Petrov[/i]
2003 Tournament Of Towns, 1
Two players in turns color the sides of an $n$-gon. The first player colors any side that has $0$ or $2$ common vertices with already colored sides. The second player colors any side that has exactly $1$ common vertex with already colored sides. The player who cannot move, loses. For which $n$ the second player has a winning strategy?
2014 Miklós Schweitzer, 1
Let $n$ be a positive integer. Let $\mathcal{F}$ be a family of sets that contains more than half of all subsets of an $n$-element set $X$. Prove that from $\mathcal{F}$ we can select $\lceil \log_2 n \rceil + 1$ sets that form a separating family on $X$, i.e., for any two distinct elements of $X$ there is a selected set containing exactly one of the two elements.
Moderator says: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=614827&hilit=Schweitzer+2014+separating
2011 Mediterranean Mathematics Olympiad, 2
Let $A$ be a finite set of positive reals, let $B = \{x/y\mid x,y\in A\}$ and let $C = \{xy\mid x,y\in A\}$.
Show that $|A|\cdot|B|\le|C|^2$.
[i](Proposed by Gerhard Woeginger, Austria)[/i]
2009 Peru IMO TST, 2
300 bureaucrats are split into three comissions of 100 people. Each two bureaucrats are either familiar to each other or non familiar to each other. Prove that there exists two bureaucrats from two distinct commissions such that the third commission contains either 17 bureaucrats familiar to both of them, or 17 bureaucrats familiar to none of them.
_________________________________________
This problem is taken from Russian Olympiad 2007-2008 district round 9.8
$ Tipe$