Found problems: 1800
2002 Iran MO (3rd Round), 22
15000 years ago Tilif ministry in Persia decided to define a code for $n\geq2$ cities. Each code is a sequence of $0,1$ such that no code start with another code. We know that from $2^{m}$ calls from foreign countries to Persia $2^{m-a_{i}}$ of them where from the $i$-th city (So $\sum_{i=1}^{n}\frac1{2^{a_{i}}}=1$). Let $l_{i}$ be length of code assigned to $i$-th city. Prove that $\sum_{i=1}^{n}\frac{l_{i}}{2^{i}}$ is minimum iff $\forall i,\ l_{i}=a_{i}$
2014 Contests, 2
Consider increasing integer sequences with elements from $1,\ldots,10^6$. Such a sequence is [i]Adriatic[/i] if its first element equals 1 and if every element is at least twice the preceding element. A sequence is [i]Tyrrhenian[/i] if its final element equals $10^6$ and if every element is strictly greater than the sum of all preceding elements.
Decide whether the number of Adriatic sequences is smaller than, equal to, or greater than the number of Tyrrhenian sequences.
(Proposed by Gerhard Woeginger, Austria)
2004 Pre-Preparation Course Examination, 3
For a subset $ S$ of vertices of graph $ G$, let $ \Lambda(S)$ be the subset of all edges of $ G$ such that at least one of their ends is in $ S$. Suppose that $ G$ is a graph with $ m$ edges. Let $ d^*: V(G)\longrightarrow\mathbb N\cup\{0\}$ be a function such that
a) $ \sum_{u}d^*(u)\equal{}m$.
b) For each subset $ S$ of $ V(G)$: \[ \sum_{u\in S}d^*(u)\leq|\Lambda(S)|\]
Prove that we can give directions to edges of $ G$ such that for each edge $ e$, $ d^\plus{}(e)\equal{}d^*(e)$.
2000 Iran MO (3rd Round), 3
In a deck of $n > 1$ cards, some digits from $1$ to$8$are written on each card.
A digit may occur more than once, but at most once on a certain card.
On each card at least one digit is written, and no two cards are denoted
by the same set of digits. Suppose that for every $k=1,2,\dots,7$ digits, the
number of cards that contain at least one of them is even. Find $n$.
2009 China Team Selection Test, 4
Let positive real numbers $ a,b$ satisfy $ b \minus{} a > 2.$ Prove that for any two distinct integers $ m,n$ belonging to $ [a,b),$ there always exists non-empty set $ S$ consisting of certain integers belonging to $ [ab,(a \plus{} 1)(b \plus{} 1))$ such that $ \frac {\displaystyle\prod_{x\in S}}{mn}$ is square of a rational number.
2007 China Northern MO, 4
For every point on the plane, one of $ n$ colors are colored to it such that:
$ (1)$ Every color is used infinitely many times.
$ (2)$ There exists one line such that all points on this lines are colored exactly by one of two colors.
Find the least value of $ n$ such that there exist four concyclic points with pairwise distinct colors.
2005 Bundeswettbewerb Mathematik, 1
Two players $A$ and $B$ have one stone each on a $100 \times 100$ chessboard. They move their stones one after the other, and a move means moving one's stone to a neighbouring field (horizontally or vertically, not diagonally). At the beginning of the game, the stone of $A$ lies in the lower left corner, and the one of $B$ in the lower right corner. Player $A$ starts.
Prove: Player $A$ is, independently from that what $B$ does, able to reach, after finitely many steps, the field $B$'s stone is lying on at that moment.
2009 South East Mathematical Olympiad, 5
Let $X=(x_1,x_2,......,x_9)$ be a permutation of the set $\{1,2,\ldots,9\}$ and let $A$ be the set of all such $X$ .
For any $X \in A$, denote $f(X)=x_1+2x_2+\cdots+9x_9$ and $ M=\{f(X)|X \in A \}$. Find $|M|$. ($|S|$ denotes number of members of the set $S$.)
2008 Hungary-Israel Binational, 2
For every natural number $ t$, $ f(t)$ is the probability that if a fair coin is tossed $ t$ times, the number of times we get heads is 2008 more than the number of tails. What is the value of $ t$ for which $ f(t)$ attains its maximum? (if there is more than one, describe all of them)
2004 Bulgaria National Olympiad, 4
In a word formed with the letters $a,b$ we can change some blocks: $aba$ in $b$ and back, $bba$ in $a$ and backwards. If the initial word is $aaa\ldots ab$ where $a$ appears 2003 times can we reach the word $baaa\ldots a$, where $a$ appears 2003 times.
1997 Baltic Way, 16
On a $5\times 5$ chessboard, two players play the following game: The first player places a knight on some square. Then the players alternately move the knight according to the rules of chess, starting with the second player. It is not allowed to move the knight to a square that was visited previously. The player who cannot move loses. Which of the two players has a winning strategy?
2013 ISI Entrance Examination, 4
In a badminton tournament, each of $n$ players play all the other $n-1$ players. Each game results in either a win, or a loss. The players then write down the names of those whom they defeated, and also of those who they defeated. For example, if $A$ beats $B$ and $B$ beats $C,$ then $A$ writes the names of both $B$ and $C$. Show that there will be one person, who has written down the names of all the other $n-1$ players.
[hide="Clarification"]
Consider a game between $A,B,C,D,E,F,G$ where $A$ defeats $B$ and $C$ and $B$ defeats $E,F$, $C$ defeats $E.$ Then $A$'s list will have $(B,C,E,F)$, and will not include $G.$
[/hide]
2012 Kosovo Team Selection Test, 1
A student had $18$ papers. He seleced some of these papers, then he cut each of them in $18$ pieces.He took these pieces and selected some of them, which he again cut in $18$ pieces each.The student took this procedure untill he got tired .After a time he counted the pieces and got $2012$ pieces .Prove that the student was wrong during the counting.
2012 Indonesia TST, 2
An $m \times n$ chessboard where $m \le n$ has several black squares such that no two rows have the same pattern. Determine the largest integer $k$ such that we can always color $k$ columns red while still no two rows have the same pattern.
2007 Serbia National Math Olympiad, 2
Triangle $\Delta GRB$ is dissected into $25$ small triangles as shown. All vertices of these triangles are painted in three colors so that the following conditions are satisfied: Vertex $G$ is painted in green, vertex $R$ in red, and $B$ in blue; Each vertex on side $GR$ is either green or red, each vertex on $RB$ is either red or blue, and each vertex on $GB$ is either green or blue. The vertices inside the big triangle are arbitrarily colored.
Prove that, regardless of the way of coloring, at least one of the $25$ small triangles has vertices of three different colors.
2006 Iran MO (3rd Round), 1
Let $A$ be a family of subsets of $\{1,2,\ldots,n\}$ such that no member of $A$ is contained in another. Sperner’s Theorem states that $|A|\leq{n\choose{\lfloor\frac{n}{2}\rfloor}}$. Find all the families for which the equality holds.
2010 Middle European Mathematical Olympiad, 2
All positive divisors of a positive integer $N$ are written on a blackboard. Two players $A$ and $B$ play the following game taking alternate moves. In the firt move, the player $A$ erases $N$. If the last erased number is $d$, then the next player erases either a divisor of $d$ or a multiple of $d$. The player who cannot make a move loses. Determine all numbers $N$ for which $A$ can win independently of the moves of $B$.
[i](4th Middle European Mathematical Olympiad, Individual Competition, Problem 2)[/i]
2017 Bulgaria JBMO TST, 4
Given is a board $n \times n$ and in every square there is a checker. In one move, every checker simultaneously goes to an adjacent square (two squares are adjacent if they share a common side). In one square there can be multiple checkers. Find the minimum and the maximum number of covered cells for $n=5, 6, 7$.
2002 Tournament Of Towns, 7
[list]
[*] A power grid with the shape of a $3\times 3$ lattice with $16$ nodes (vertices of the lattice) joined by wires (along the sides of squares. It may have happened that some of the wires have burned out. In one test technician can choose any two nodes and check if electrical current circulates between them (i.e there is a chain of intact wires joining the chosen nodes) . Technicial knows that current will circulate from any node to another node. What is the least number of tests required to demonstrate this?
[*] Previous problem for the grid of $7\times 7$ lattice.[/list]
1994 Baltic Way, 18
There are $n>2$ lines given in the plane. No two of the lines are parallel and no three of them intersect at one point. Every point of intersection of these lines is labelled with a natural number between $1$ and $n-1$. Prove that, if and only if $n$ is even, it is possible to assign the labels in such a way that every line has all the numbers from $1$ to $n-1$ at its points of intersection with the other $n-1$ lines.
2007 Turkey Team Selection Test, 1
Find the number of the connected graphs with 6 vertices. (Vertices are considered to be different)
2008 All-Russian Olympiad, 5
The distance between two cells of an infinite chessboard is defined as the minimum nuber to moves needed for a king for move from one to the other.One the board are chosen three cells on a pairwise distances equal to $ 100$. How many cells are there that are on the distance $ 50$ from each of the three cells?
2013 China Team Selection Test, 3
There are$n$ balls numbered $1,2,\cdots,n$, respectively. They are painted with $4$ colours, red, yellow, blue, and green, according to the following rules:
First, randomly line them on a circle.
Then let any three clockwise consecutive balls numbered $i, j, k$, in order.
1) If $i>j>k$, then the ball $j$ is painted in red;
2) If $i<j<k$, then the ball $j$ is painted in yellow;
3) If $i<j, k<j$, then the ball $j$ is painted in blue;
4) If $i>j, k>j$, then the ball $j$ is painted in green.
And now each permutation of the balls determine a painting method.
We call two painting methods distinct, if there exists a ball, which is painted with two different colours in that two methods.
Find out the number of all distinct painting methods.
2015 China Team Selection Test, 6
There are some players in a Ping Pong tournament, where every $2$ players play with each other at most once. Given:
\\(1) Each player wins at least $a$ players, and loses to at least $b$ players. ($a,b\geq 1$)
\\(2) For any two players $A,B$, there exist some players $P_1,...,P_k$ ($k\geq 2$) (where $P_1=A$,$P_k=B$), such that $P_i$ wins $P_{i+1}$ ($i=1,2...,k-1$).
\\Prove that there exist $a+b+1$ distinct players $Q_1,...Q_{a+b+1}$, such that $Q_i$ wins $Q_{i+1}$ ($i=1,...,a+b$)
2009 India IMO Training Camp, 12
Let $ G$ be a simple graph with vertex set $ V\equal{}\{0,1,2,3,\cdots ,n\plus{}1\}$ .$ j$and$ j\plus{}1$ are connected by an edge for $ 0\le j\le n$. Let $ A$ be a subset of $ V$ and $ G(A)$ be the induced subgraph associated with $ A$. Let $ O(G(A))$ be number of components of $ G(A)$ having an odd number of vertices.
Let
$ T(p,r)\equal{}\{A\subset V \mid 0.n\plus{}1 \notin A,|A|\equal{}p,O(G(A))\equal{}2r\}$ for $ r\le p \le 2r$.
Prove That $ |T(p,r)|\equal{}{n\minus{}r \choose{p\minus{}r}}{n\minus{}p\plus{}1 \choose{2r\minus{}p}}$.