Found problems: 1488
2013 ELMO Shortlist, 1
Let $n\ge2$ be a positive integer. The numbers $1,2,..., n^2$ are consecutively placed into squares of an $n\times n$, so the first row contains $1,2,...,n$ from left to right, the second row contains $n+1,n+2,...,2n$ from left to right, and so on. The [i]magic square value[/i] of a grid is defined to be the number of rows, columns, and main diagonals whose elements have an average value of $\frac{n^2 + 1}{2}$. Show that the magic-square value of the grid stays constant under the following two operations: (1) a permutation of the rows; and (2) a permutation of the columns. (The operations can be used multiple times, and in any order.)
[i]Proposed by Ray Li[/i]
2002 China Team Selection Test, 2
$ m$ and $ n$ are positive integers. In a $ 8 \times 8$ chessboard, $ (m,n)$ denotes the number of grids a Horse can jump in a chessboard ($ m$ horizontal $ n$ vertical or $ n$ horizontal $ m$ vertical ). If a $ (m,n) \textbf{Horse}$ starts from one grid, passes every grid once and only once, then we call this kind of Horse jump route a $ \textbf{H Route}$. For example, the $ (1,2) \textbf{Horse}$ has its $ \textbf{H Route}$. Find the smallest positive integer $ t$, such that from any grid of the chessboard, the $ (t,t\plus{}1) \textbf{Horse}$ does not has any $ \textbf{H Route}$.
1994 China Team Selection Test, 3
Find the smallest $n \in \mathbb{N}$ such that if any 5 vertices of a regular $n$-gon are colored red, there exists a line of symmetry $l$ of the $n$-gon such that every red point is reflected across $l$ to a non-red point.
1997 Austrian-Polish Competition, 8
Let $X$ be a set with $n$ elements. Find the largest number of subsets of $X$, each with $3$ elements, so that no two of them are disjoint.
2006 India Regional Mathematical Olympiad, 4
A $ 6\times 6$ square is dissected in to 9 rectangles by lines parallel to its sides such that all these rectangles have integer sides. Prove that there are always [b]two[/b] congruent rectangles.
2008 Mexico National Olympiad, 3
Consider a chess board, with the numbers $1$ through $64$ placed in the squares as in the diagram below.
\[\begin{tabular}{| c | c | c | c | c | c | c | c |}
\hline
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\hline
9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\
\hline
17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\
\hline
25 & 26 & 27 & 28 & 29 & 30 & 31 & 32 \\
\hline
33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\
\hline
41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 \\
\hline
49 & 50 & 51 & 52 & 53 & 54 & 55 & 56 \\
\hline
57 & 58 & 59 & 60 & 61 & 62 & 63 & 64 \\
\hline
\end{tabular}\]
Assume we have an infinite supply of knights. We place knights in the chess board squares such that no two knights attack one another and compute the sum of the numbers of the cells on which the knights are placed. What is the maximum sum that we can attain?
Note. For any $2\times3$ or $3\times2$ rectangle that has the knight in its corner square, the knight can attack the square in the opposite corner.
1987 Vietnam National Olympiad, 3
Let be given $ n \ge 2$ lines on a plane, not all concurrent and no two parallel. Prove that there is a point which belongs to exactly two of the given lines.
2011 JBMO Shortlist, 6
Let $n>3$ be a positive integer. Equilateral triangle ABC is divided into $n^2$ smaller congruent equilateral triangles (with sides parallel to its sides). Let $m$ be the number of rhombuses that contain two small equilateral triangles and $d$ the number of rhombuses that contain eight small equilateral triangles. Find the difference $m-d$ in terms of $n$.
2009 Germany Team Selection Test, 2
Tracy has been baking a rectangular cake whose surface is dissected by grid lines in square fields. The number of rows is $ 2^n$ and the number of columns is $ 2^{n \plus{} 1}$ where $ n \geq 1, n \in \mathbb{N}.$ Now she covers the fields with strawberries such that each row has at least $ 2n \plus{} 2$ of them. Show that there four pairwise distinct strawberries $ A,B,C$ and $ D$ which satisfy those three conditions:
(a) Strawberries $ A$ and $ B$ lie in the same row and $ A$ further left than $ B.$ Similarly $ D$ lies in the same row as $ C$ but further left.
(b) Strawberries $ B$ and $ C$ lie in the same column.
(c) Strawberries $ A$ lies further up and further left than $ D.$
1999 All-Russian Olympiad, 2
There are several cities in a country. Some pairs of the cities are connected by a two-way airline of one of the $N$ companies, so that each company serves exactly one airline from each city, and one can travel between any two cities, possibly with transfers. During a financial crisis, $N-1$ airlines have been canceled, all from different companies. Prove that it is still possible to travel between any two cities.
2012 Indonesia TST, 2
Let $P_1, P_2, \ldots, P_n$ be distinct $2$-element subsets of $\{1, 2, \ldots, n\}$. Suppose that for every $1 \le i < j \le n$, if $P_i \cap P_j \neq \emptyset$, then there is some $k$ such that $P_k = \{i, j\}$. Prove that if $a \in P_i$ for some $i$, then $a \in P_j$ for exactly one value of $j$ not equal to $i$.
2011 China Team Selection Test, 3
Let $G$ be a simple graph with $3n^2$ vertices ($n\geq 2$). It is known that the degree of each vertex of $G$ is not greater than $4n$, there exists at least a vertex of degree one, and between any two vertices, there is a path of length $\leq 3$. Prove that the minimum number of edges that $G$ might have is equal to $\frac{(7n^2- 3n)}{2}$.
1997 Vietnam Team Selection Test, 2
There are $ 25$ towns in a country. Find the smallest $ k$ for which one can set up two-direction flight routes connecting these towns so that the following conditions are satisfied:
1) from each town there are exactly $ k$ direct routes to $ k$ other towns;
2) if two towns are not connected by a direct route, then there is a town which has direct routes to these two towns.
2003 Mexico National Olympiad, 5
Some cards each have a pair of numbers written on them. There is just one card for each pair $(a,b)$ with $1 \leq a < b \leq 2003$. Two players play the following game. Each removes a card in turn and writes the product $ab$ of its numbers on the blackboard. The first player who causes the greatest common divisor of the numbers on the blackboard to fall to $1$ loses. Which player has a winning strategy?
2007 Tournament Of Towns, 4
Nancy shuffles a deck of $52$ cards and spreads the cards out in a circle face up, leaving one spot empty. Andy, who is in another room and does not see the cards, names a card. If this card is adjacent to the empty spot, Nancy moves the card to the empty spot, without telling Andy; otherwise nothing happens. Then Andy names another card and so on, as many times as he likes, until he says "stop."
[list][b](a)[/b] Can Andy guarantee that after he says "stop," no card is in its initial spot?
[b](b)[/b] Can Andy guarantee that after he says "stop," the Queen of Spades is not adjacent to
the empty spot?[/list]
2014 Iran MO (3rd Round), 7
We have a machine that has an input and an output. The input is a letter from the finite set $I$ and the output is a lamp that at each moment has one of the colors of the set $C=\{c_1,\dots,c_p\}$.
At each moment the machine has an inner state that is one of the $n$ members of finite set $S$. The function $o: S \rightarrow C$ is a surjective function defining that at each state, what color must the lamp be, and the function $t:S \times I \rightarrow S$ is a function defining how does giving each input at each state changes the state. We only shall see the lamp and we have no direct information from the state of the car at current moment.
In other words a machine is $M=(S,I,C,o,t)$ such that $S,I,C$ are finite, $t:S \times I \rightarrow S$ , and $o:S \rightarrow C$ is surjective. It is guaranteed that for each two different inner states, there's a sequence of inputs such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state.
(a) The machine $M$ has $n$ different inner states. Prove that for each two different inner states, there's a sequence of inputs of length no more than $n-p$ such that the color of the lamp after giving the sequence to the machine at the first state is different from the color of the lamp after giving the sequence to the machine at the second state.
(b) Prove that for a machine $M$ with $n$ different inner states, there exists an algorithm with no more than $n^2$ inputs that starting at any unknown inner state, at the end of the algorithm the state of the machine at that moment is known.
Can you prove the above claim for $\frac{n^2}{2}$?
2009 Argentina Iberoamerican TST, 1
In the vertexes of a regular $ 31$-gon there are written the numbers from $ 1$ to $ 31$, ordered increasingly, clockwise oriented.
We are allowed to perform an operation which consists in taking any three vertexes, namely the ones who have written $ a$,$ b$, and $ c$ and change them into $ c$, $ a\minus{}\frac{1}{10}$ and $ b\plus{}\frac{1}{10}$ respectively ( $ a$ becomes $ c$, $ b$ becomes $ a\minus{}\frac{1}{10}$ and $ c$ turns into $ b\plus{}\frac{1}{10}$
Prove that after applying several operations we can reach the state in which the numbers in the vertexes are the numbers from $ 1$ to $ 31$, ordered increasingly,anti-clockwise oriented.
2001 Hungary-Israel Binational, 5
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})$.
(a) Let $p$ be a prime. Consider the graph whose vertices are the ordered pairs $(x, y)$ with $x, y \in\{0, 1, . . . , p-1\}$ and whose edges join vertices $(x, y)$ and $(x' , y')$ if and only if $xx'+yy'\equiv 1 \pmod{p}$ . Prove that this graph does not contain $C_{4}$ .
(b) Prove that for infinitely many values $n$ there is a graph $G_{n}$ with $e(G_{n}) \geq \frac{n\sqrt{n}}{2}-n$ that does not contain $C_{4}$.
2007 Greece National Olympiad, 4
Given a $2007\times 2007$ array of numbers $1$ and $-1$, let $A_{i}$ denote the product of the entries in the $i$th row, and $B_{j}$ denote the product of the entries in the $j$th column. Show that
\[A_{1}+A_{2}+\cdots +A_{2007}+B_{1}+B_{2}+\cdots +B_{2007}\neq 0.\]
2008 Croatia Team Selection Test, 4
Let $ S$ be the set of all odd positive integers less than $ 30m$ which are not multiples of $ 5$, where $ m$ is a given positive integer. Find the smallest positive integer $ k$ such that each $ k$-element subset of $ S$ contains two distinct numbers, one of which divides the other.
2008 Tournament Of Towns, 5
On the infinite chessboard several rectangular pieces are placed whose sides run along the grid lines. Each two have no squares in common, and each consists of an odd number of squares. Prove that these pieces can be painted in four colours such that two pieces painted in the same colour do not share any boundary points.
2011 Junior Balkan MO, 3
Let $n>3$ be a positive integer. Equilateral triangle ABC is divided into $n^2$ smaller congruent equilateral triangles (with sides parallel to its sides). Let $m$ be the number of rhombuses that contain two small equilateral triangles and $d$ the number of rhombuses that contain eight small equilateral triangles. Find the difference $m-d$ in terms of $n$.
2005 Postal Coaching, 9
In how many ways can $n$ identical balls be distributed to nine persons $A,B,C,D,E,F,G,H,I$ so that the number of balls recieved by $A$ is the same as the total number of balls recieved by $B,C,D,E$ together,.
2009 Singapore Senior Math Olympiad, 5
In an archery competition of 30 contestants, the target is divided into two zones, zone 1 and zone 2. Each arrow hitting the zone 1 gets 10 points, when hitting zone 2 will get 5 points and no score for miss. Each contestant throws 16 arrows. At the end of the competition, the statistics show that more than 50% of the arrows hit zone 2. The number of arrows that hit zone 1 is equal to the arrows which are missed. Prove than there are two contestants having equal score.
2005 MOP Homework, 7
A segment of length $2$ is divided into $n$, $n\ge 2$, subintervals. A square is then constructed on each subinterval. Assume that the sum of the areas of all such squares is greater than $1$. Show that under this assumption one can always choose two subintervals with total length greater than $1$.