Found problems: 1800
2008 Iran Team Selection Test, 6
Prove that in a tournament with 799 teams, there exist 14 teams, that can be partitioned into groups in a way that all of the teams in the first group have won all of the teams in the second group.
2005 Baltic Way, 6
Let $N$ and $K$ be positive integers satisfying $1 \leq K \leq N$. A deck of $N$ different playing cards is shuffled by repeating the operation of reversing the order of $K$ topmost cards and moving these to the bottom of the deck. Prove that the deck will be back in its initial order after a number of operations not greater than $(2N/K)^2$.
2011 Mexico National Olympiad, 5
A $(2^n - 1) \times (2^n +1)$ board is to be divided into rectangles with sides parallel to the sides of the board and integer side lengths such that the area of each rectangle is a power of 2. Find the minimum number of rectangles that the board may be divided into.
2014 China Team Selection Test, 3
$A$ is the set of points of a convex $n$-gon on a plane. The distinct pairwise distances between any $2$ points in $A$ arranged in descending order is $d_1>d_2>...>d_m>0$. Let the number of unordered pairs of points in $A$ such that their distance is $d_i$ be exactly $\mu _i$, for $i=1, 2,..., m$.
Prove: For any positive integer $k\leq m$, $\mu _1+\mu _2+...+\mu _k\leq (3k-1)n$.
2014 District Olympiad, 4
A $10$ digit positive integer is called a $\emph{cute}$ number if its digits are from
the set $\{1,2,3\}$ and every two consecutive digits differ by $1$.
[list=a]
[*]Prove that exactly $5$ digits of a cute number are equal to $2$.
[*]Find the total number of cute numbers.
[*]Prove that the sum of all cute numbers is divisible by $1408$.[/list]
2003 Turkey Team Selection Test, 1
Let $M = \{(a,b,c,d)|a,b,c,d \in \{1,2,3,4\} \text{ and } abcd > 1\}$. For each $n\in \{1,2,\dots, 254\}$, the sequence $(a_1, b_1, c_1, d_1)$, $(a_2, b_2, c_2, d_2)$, $\dots$, $(a_{255}, b_{255},c_{255},d_{255})$ contains each element of $M$ exactly once and the equality \[|a_{n+1} - a_n|+|b_{n+1} - b_n|+|c_{n+1} - c_n|+|d_{n+1} - d_n| = 1\] holds. If $c_1 = d_1 = 1$, find all possible values of the pair $(a_1,b_1)$.
2008 Iran Team Selection Test, 3
Suppose that $ T$ is a tree with $ k$ edges. Prove that the $ k$-dimensional cube can be partitioned to graphs isomorphic to $ T$.
1992 Brazil National Olympiad, 8
In a chess tournament each player plays every other player once. A player gets 1 point for a win, 0.5 point for a draw and 0 for a loss. Both men and women played in the tournament and each player scored the same total of points against women as against men. Show that the total number of players must be a square.
2008 Mongolia Team Selection Test, 2
Let $ a_1,a_2,...,a_n$ is permutaion of $ 1,2,...,n$. For this permutaion call the pair $ (a_i,a_j)$ [i]wrong pair [/i]if $ i<j$ and $ a_i >a_j$.Let [i]number of inversion [/i] is number of [i]wrong pair [/i] of permutation $ a_1,a_2,a_3,..,a_n$. Let $ n \ge 2$ is positive integer. Find the number of permutation of $ 1,2,..,n$ such that its [i]number of inversion [/i]is divisible by $ n$.
2006 Iran MO (2nd round), 3
In the night, stars in the sky are seen in different time intervals. Suppose for every $k$ stars ($k>1$), at least $2$ of them can be seen in one moment. Prove that we can photograph $k-1$ pictures from the sky such that each of the mentioned stars is seen in at least one of the pictures.
(The number of stars is finite. Define the moments that the $n^{th}$ star is seen as $[a_n,b_n]$ that $a_n<b_n$.)
2006 All-Russian Olympiad, 8
A $3000\times 3000$ square is tiled by dominoes (i. e. $1\times 2$ rectangles) in an arbitrary way. Show that one can color the dominoes in three colors such that the number of the dominoes of each color is the same, and each dominoe $d$ has at most two neighbours of the same color as $d$. (Two dominoes are said to be [i]neighbours[/i] if a cell of one domino has a common edge with a cell of the other one.)
2006 MOP Homework, 1
In how many ways can the set $N ={1, 2, \cdots, n}$ be partitioned in the form $p(N) = A_{1}\cup A_{2}\cup \cdots \cup A_{k},$ where $A_{i}$ consists of elements forming arithmetic progressions, all with the same common positive difference $d_{p}$ and of length at least one? At least two?
[hide="Solution"]
[b]Part 1[/b]
Claim: There are $2^{n}-2$ ways of performing the desired partitioning.
Let $d(k)$ equal the number of ways $N$ can be partitioned as above with common difference $k.$ We are thus trying to evaluate
$\sum_{i=1}^{n-1}d(i)$
[b]Lemma: $d(i) = 2^{n-i}$[/b]
We may divide $N$ into various rows where the first term of each row denotes a residue $\bmod{i}.$ The only exception is the last row, as no row starts with $0$; the last row will start with $i.$ We display the rows as such:
$1, 1+i, 1+2i, 1+3i, \cdots$
$2, 2+i, 2+2i, 2+3i, \cdots$
$\cdots$
$i, 2i, 3i, \cdots$
Since all numbers have one lowest remainder $\bmod{i}$ and we have covered all possible remainders, all elements of $N$ occur exactly once in these rows.
Now, we can take $k$ line segments and partition a given row above; all entries within two segments would belong to the same set. For example, we can have:
$1| 1+i, 1+2i, 1+3i | 1+4i | 1+5i, 1+6i, 1+7i, 1+8i,$
which would result in the various subsets: ${1},{1+i, 1+2i, 1+3i},{1+4i},{1+5i, 1+6i, 1+7i, 1+8i}.$ For any given row with $k$ elements, we can have at most $k-1$ segments. Thus, we can arrange any number of segments where the number lies between $0$ and $k-1$, inclusive, in:
$\binom{k-1}{0}+\binom{k-1}{1}+\cdots+\binom{k-1}{k-1}= 2^{k-1}$
ways. Applying the same principle to the other rows and multiplying, we see that the result always gives us $2^{n-i},$ as desired.
We now proceed to the original proof.
Since $d(i) = 2^{n-i}$ by the above lemma, we have:
$\sum_{i=1}^{n-1}d(i) = \sum_{i=1}^{n-1}2^{n-i}= 2^{n}-2$
Thus, there are $2^{n}-2$ ways of partitioning the set as desired.
[b]Part 2[/b]
Everything is the same as above, except the lemma slightly changes to $d(i) = 2^{n-i}-i.$ Evaluating the earlier sum gives us:
$\sum_{i=1}^{n-1}d(i) = \sum_{i=1}^{n-1}2^{n-i}-i = 2^{n}-\frac{n(n-1)}{2}-2$
[/hide]
1989 Flanders Math Olympiad, 1
Show that every subset of {1,2,...,99,100} with 55 elements contains at least 2 numbers with a difference of 9.
2004 Iran MO (3rd Round), 22
Suppose that $ \mathcal F$ is a family of subsets of $ X$. $ A,B$ are two subsets of $ X$ s.t. each element of $ \mathcal{F}$ has non-empty intersection with $ A, B$. We know that no subset of $ X$ with $ n \minus{} 1$ elements has this property. Prove that there is a representation $ A,B$ in the form $ A \equal{} \{a_1,\dots,a_n\}$ and $ B \equal{} \{b_1,\dots,b_n\}$, such that for each $ 1\leq i\leq n$, there is an element of $ \mathcal F$ containing both $ a_i, b_i$.
2013 Stars Of Mathematics, 4
Given a (fixed) positive integer $N$, solve the functional equation
\[f \colon \mathbb{Z} \to \mathbb{R}, \ f(2k) = 2f(k) \textrm{ and } f(N-k) = f(k), \ \textrm{for all } k \in \mathbb{Z}.\]
[i](Dan Schwarz)[/i]
2006 Baltic Way, 8
The director has found out that six conspiracies have been set up in his department, each of them involving exactly $3$ persons. Prove that the director can split the department in two laboratories so that none of the conspirative groups is entirely in the same laboratory.
2001 Baltic Way, 1
A set of $8$ problems was prepared for an examination. Each student was given $3$ of them. No two students received more than one common problem. What is the largest possible number of students?
2008 Mongolia Team Selection Test, 1
How many ways to fill the board $ 4\times 4$ by nonnegative integers, such that sum of the numbers of each row and each column is 3?
2011 Iran Team Selection Test, 9
We have $n$ points in the plane such that they are not all collinear. We call a line $\ell$ a 'good' line if we can divide those $n$ points in two sets $A,B$ such that the sum of the distances of all points in $A$ to $\ell$ is equal to the sum of the distances of all points in $B$ to $\ell$. Prove that there exist infinitely many points in the plane such that for each of them we have at least $n+1$ good lines passing through them.
2006 Pre-Preparation Course Examination, 3
The bell number $b_n$ is the number of ways to partition the set $\{1,2,\ldots,n\}$. For example $b_3=5$. Find a recurrence for $b_n$ and show that $b_n=e^{-1}\sum_{k\geq 0} \frac{k^n}{k!}$. Using a combinatorial proof show that the number of ways to partition $\{1,2,\ldots,n\}$, such that now two consecutive numbers are in the same block, is $b_{n-1}$.
2010 Contests, 1
Three coins lie on integer points on the number line. A move consists of choosing and moving two coins, the first one $ 1$ unit to the right and the second one $ 1$ unit to the left.
Under which initial conditions is it possible to move all coins to one single point?
1999 Baltic Way, 11
Prove that for any four points in the plane, no three of which are collinear, there exists a circle such that three of the four points are on the circumference and the fourth point is either on the circumference or inside the circle.
2013 North Korea Team Selection Test, 4
Positive integers 1 to 9 are written in each square of a $ 3 \times 3 $ table. Let us define an operation as follows: Take an arbitrary row or column and replace these numbers $ a, b, c$ with either non-negative numbers $ a-x, b-x, c+x $ or $ a+x, b-x, c-x$, where $ x $ is a positive number and can vary in each operation.
(1) Does there exist a series of operations such that all 9 numbers turn out to be equal from the following initial arrangement a)? b)?
\[ a) \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{array} )\]
\[ b) \begin{array}{ccc} 2 & 8 & 5 \\ 9 & 3 & 4 \\ 6 & 7 & 1 \end{array} )\]
(2) Determine the maximum value which all 9 numbers turn out to be equal to after some steps.
2005 Turkey Team Selection Test, 3
We are given 5040 balls in k different colors, where the number of balls of each color is the same. The balls are put into 2520 bags so that each bag contains two balls of different colors. Find the smallest k such that, however the balls are distributed into the bags, we can arrange the bags around a circle so that no two balls of the same color are in two neighboring bags.
2016 Indonesia TST, 4
We call a subset $B$ of natural numbers [i]loyal[/i] if there exists natural numbers $i\le j$ such that $B=\{i,i+1,\ldots,j\}$. Let $Q$ be the set of all [i]loyal[/i] sets. For every subset $A=\{a_1<a_2<\ldots<a_k\}$ of $\{1,2,\ldots,n\}$ we set
\[f(A)=\max_{1\le i \le k-1}{a_{i+1}-a_i}\qquad\text{and}\qquad g(A)=\max_{B\subseteq A, B\in Q} |B|.\] Furthermore, we define \[F(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} f(A)\qquad\text{and}\qquad G(n)=\sum_{A\subseteq \{1,2,\ldots,n\}} g(A).\] Prove that there exists $m\in \mathbb N$ such that for each natural number $n>m$ we have $F(n)>G(n)$. (By $|A|$ we mean the number of elements of $A$, and if $|A|\le 1$, we define $f(A)$ to be zero).
[i]Proposed by Javad Abedi[/i]