Found problems: 1800
2002 Iran Team Selection Test, 12
We call a permutation $ \left(a_1, a_2, ..., a_n\right)$ of $ \left(1, 2, ..., n\right)$ [i]quadratic[/i] if there exists at least a perfect square among the numbers $ a_1$, $ a_1 \plus{} a_2$, $ ...$, $ a_1 \plus{} a_2 \plus{} ... \plus{} a_n$. Find all natural numbers $ n$ such that all permutations in $ S_n$ are quadratic.
[i]Remark.[/i] $ S_{n}$ denotes the $ n$-th symmetric group, the group of permutations on $ n$ elements.
1996 Romania Team Selection Test, 10
Let $ n $ and $ r $ be positive integers and $ A $ be a set of lattice points in the plane such that any open disc of radius $ r $ contains a point of $ A $. Show that
for any coloring of the points of $ A $ in $ n $ colors there exists four points of the same color which are the vertices of a rectangle.
1997 All-Russian Olympiad, 3
The lateral sides of a box with base $a\times b$ and height $c$ (where $a$; $b$;$ c$ are natural numbers) are completely covered without overlap by rectangles whose edges are parallel to the edges of the box, each containing an even number of unit squares. (Rectangles may cross the lateral edges of the box.) Prove that if $c$ is odd, then
the number of possible coverings is even.
[i]D. Karpov, C. Gukshin, D. Fon-der-Flaas[/i]
2006 Pre-Preparation Course Examination, 5
Express the sum $S_m(n)=1^m+2^m+\ldots +(n-1)^m$ with Bernolli numbers.
2009 Spain Mathematical Olympiad, 3
Some edges are painted in red. We say that a coloring of this kind is [i]good[/i], if for each vertex of the polyhedron, there exists an edge which concurs in that vertex and is not painted red. Moreover, we say that a coloring where some of the edges of a regular polyhedron is [i]completely good[/i], if in addition to being [i]good[/i], no face of the polyhedron has all its edges painted red. What regular polyhedrons is equal the maximum number of edges that can be painted in a [i]good[/i] color and a [i]completely good[/i]? Explain your answer.
2008 APMO, 2
Students in a class form groups each of which contains exactly three members such that any two distinct groups have at most one member in common. Prove that, when the class size is $ 46$, there is a set of $ 10$ students in which no group is properly contained.
2007 All-Russian Olympiad, 7
Given a matrix $\{a_{ij}\}_{i,j=0}^{9}$, $a_{ij}=10i+j+1$. Andrei is going to cover its entries by $50$ rectangles $1\times 2$ (each such rectangle contains two adjacent entries) so that the sum of $50$ products in these rectangles is minimal possible. Help him.
[i]A. Badzyan[/i]
2024 All-Russian Olympiad, 7
In a country there are $n>100$ cities and initially no roads. The government randomly determined the cost of building a two-way road between any two cities, using all amounts from $1$ to $\frac{n(n-1)}{2}$ thalers once (all options are equally likely). The mayor of each city chooses the cheapest of the $n-1$ roads emanating from that city and it is built (this may be the mutual desired of the mayors of both cities being connected, or only one of the two).
After the construction of these roads, the cities are divided into $M$ connected components (between cities of the same connected component, you can get along the constructed roads, possibly via other cities, but this is not possible for cities of different components). Find the expected value of the random variable $M$.
[i]Proposed by F. Petrov[/i]
2010 Silk Road, 4
In country there are two capitals ($A$ and $B$) and finite number of towns.
Some towns (or town with one of capital) connected with roads (one-way). (between every two towns or capital and town there are arbitrary number of roads) such that exist at least one way from $A$ to $B$.
Given, that any two ways from $A$ to $B$ have at least one common road.
Prove, that exist one road, such that all ways from $A$ to $B$ pass through this road.
2010 Indonesia TST, 2
Given an equilateral triangle, all points on its sides are colored in one of two given colors. Prove that the is a right-angled triangle such that its three vertices are in the same color and on the sides of the equilateral triangle.
[i]Alhaji Akbar, Jakarta[/i]
2013 ITAMO, 6
Two magicians are performing the following game. Initially the first magician encloses the second magician in a cabin where he can neither see nor hear anything. To start the game, the first magician invites Daniel, from the audience, to put on each square of a chessboard $n \times n$, at his (Daniel's) discretion, a token black or white. Then the first magician asks Daniel to show him a square $C$ of his own choice. At this point, the first magician chooses a square $D$ (not necessarily different from $C$) and replaces the token that is on $D$ with other color token (white with black or black with white).
Then he opens the cabin in which the second magician was held. Looking at the chessboard, the second magician guesses what is the square $C$. For what value of $n$, the two magicians have a strategy such that the second magician makes a successful guess.
2005 Kazakhstan National Olympiad, 3
Exactly one number from the set $\{ -1,0,1 \}$ is written in each unit cell of a $2005 \times 2005$ table, so that the sum of all the entries is $0$. Prove that there exist two rows and two columns of the table, such that the sum of the four numbers written at the intersections of these rows and columns is equal to $0$.
2014 ELMO Shortlist, 1
You have some cyan, magenta, and yellow beads on a non-reorientable circle, and you can perform only the following operations:
1. Move a cyan bead right (clockwise) past a yellow bead, and turn the yellow bead magenta.
2. Move a magenta bead left of a cyan bead, and insert a yellow bead left of where the magenta bead ends up.
3. Do either of the above, switching the roles of the words ``magenta'' and ``left'' with those of ``yellow'' and ``right'', respectively.
4. Pick any two disjoint consecutive pairs of beads, each either yellow-magenta or magenta-yellow, appearing somewhere in the circle, and swap the orders of each pair.
5. Remove four consecutive beads of one color.
Starting with the circle: ``yellow, yellow, magenta, magenta, cyan, cyan, cyan'', determine whether or not you can reach
a) ``yellow, magenta, yellow, magenta, cyan, cyan, cyan'',
b) ``cyan, yellow, cyan, magenta, cyan'',
c) ``magenta, magenta, cyan, cyan, cyan'',
d) ``yellow, cyan, cyan, cyan''.
[i]Proposed by Sammy Luo[/i]
2007 Kyiv Mathematical Festival, 3
a) One has a set of stones with weights $1, 2, \ldots, 20$ grams. Find all $k$ for which it is possible to place $k$ and the rest $20-k$ stones from the set respectively on the two pans of a balance so that equilibrium is achieved.
b) One has a set of stones with weights $1, 2, \ldots, 51$ grams. Find all $k$ for which it is possible to place $k$ and the rest $51-k$ stones from the set respectively on the two pans of a balance so that equilibrium is achieved.
c) One has a set of stones with weights $1, 2, \ldots, n$ grams ($n\in\mathbb{N}$). Find all $n$ and $k$ for which it is possible to place $k$ and the rest $n-k$ stones from the set respectively on the two pans of a balance so that equilibrium is achieved.
[size=75] a) and b) were proposed at the festival, c) is a generalization[/size]
2005 Kyiv Mathematical Festival, 5
The plane is dissected by broken lines into some regions. It is possible to paint the map formed by these regions in three colours so that any neighbouring regions will have different colours. Call by knots the points which belong to at least two segments of broken lines. One of the segments connecting two knots is erased and replaced by arbitrary broken line connecting the same knots. Prove that it is possible to paint new map in three colours so that any neighbouring regions will have different colours.
1999 Romania Team Selection Test, 13
Let $n\geq 3$ and $A_1,A_2,\ldots,A_n$ be points on a circle. Find the largest number of acute triangles that can be considered with vertices in these points.
[i]G. Eckstein[/i]
2012 European Mathematical Cup, 4
Let $k$ be a positive integer. At the European Chess Cup every pair of players played a game in which somebody won (there were no draws). For any $k$ players there was a player against whom they all lost, and the number of players was the least possible for such $k$. Is it possible that at the Closing Ceremony all the participants were seated at the round table in such a way that every participant was seated next to both a person he won against and a person he lost against.
[i]Proposed by Matija Bucić.[/i]
2023 Bundeswettbewerb Mathematik, 2
A hilly island has $2023$ lookouts. It is known that each of them is in line of sight with at least $42$ of the other lookouts. For any two distinct lookouts $X$ and $Y$ there is a positive integer $n$ and lookouts $A_1,A_2,\dots,A_{n+1}$ such that $A_1=X$ and $A_{n+1}=Y$ and $A_1$ is in line of sight with $A_2$, $A_2$ with $A_3$, $\dots$ and $A_n$ with $A_{n+1}$. The smallest such number $n$ is called the [i]viewing distance[/i] of $X$ and $Y$.
Determine the largest possible viewing distance that can exist between two lookouts under these conditions.
1995 Romania Team Selection Test, 3
Let $n \geq 6$ and $3 \leq p < n - p$ be two integers. The vertices of a regular $n$-gon are colored so that $p$ vertices are red and the others are black. Prove that there exist two congruent polygons with at least $[p/2] + 1$ vertices, one with all the vertices red and the other with all the vertices black.
2013 Federal Competition For Advanced Students, Part 2, 5
Let $n\geqslant3$ be an integer. Let $A_1A_2\ldots A_n$ be a convex $n$-gon. Consider a line $g$ through $A_1$ that does not contain a further vertice of the $n$-gon. Let $h$ be the perpendicular to $g$ through $A_1$. Project the $n$-gon orthogonally on $h$.
For $j=1,\ldots,n$, let $B_j$ be the image of $A_j$ under this projection. The line $g$ is called admissible if the points $B_j$ are pairwise distinct.
Consider all convex $n$-gons and all admissible lines $g$. How many different orders of the points $B_1,\ldots,B_n$ are possible?
2016 Croatia Team Selection Test, Problem 2
Let $S$ be a set of $N \ge 3$ points in the plane. Assume that no $3$ points in $S$ are collinear. The segments with both endpoints in $S$ are colored in two colors.
Prove that there is a set of $N - 1$ segments of the same color which don't intersect except in their endpoints such that no subset of them forms a polygon with positive area.
2006 IMAR Test, 2
A number of $n > m \geq 1$ soccer teams play a full tournament, each team meeting (once) each other. Points are awarded: $2$ for a victory, $1$ for a tie and $0$ for a loss. At the end, each team has won half of its points against the $m$ teams placed last (including each of these teams, who won half of its points against the other $m-1$).
Find all possible values for $n$ and $m$, supported with examples of such tournaments.
1977 IMO Longlists, 3
In a company of $n$ persons, each person has no more than $d$ acquaintances, and in that company there exists a group of $k$ persons, $k\ge d$, who are not acquainted with each other. Prove that the number of acquainted pairs is not greater than $\left[ \frac{n^2}{4}\right]$.
1996 ITAMO, 4
There is a list of $n$ football matches. Determine how many possible columns, with an even number of draws, there are.
2024 Baltic Way, 6
A [i]labyrinth[/i] is a system of $2024$ caves and $2023$ non-intersecting (bidirectional) corridors, each of which connects exactly two caves, where each pair of caves is connected through some sequence of corridors. Initially, Erik is standing in a corridor connecting some two caves. In a move, he can walk through one of the caves to another corridor that connects that cave to a third cave. However, when doing so, the corridor he was just in will magically disappear and get replaced by a new one connecting the end of his new corridor to the beginning of his old one (i.e., if Erik was in a corridor connecting caves $a$ and $b$ and he walked through cave $b$ into a corridor that connects caves $b$ and $c$, then the corridor between caves $a$ and $b$ will disappear and a new corridor between caves $a$ and $c$ will appear).
Since Erik likes designing labyrinths and has a specific layout in mind for his next one, he is wondering whether he can transform the labyrinth into that layout using these moves. Prove that this is in fact possible, regardless of the original layout and his starting position there.