There are two letter sequences $A$ and $B$, both with length $100$ letters. In one move you can insert in any place of sequence ( possibly to start or to end) any number of same letters or remove any number of consecutive same letters. Prove that it is possible to make second sequence from first sequence using not more than $100$ moves.

In a country there are several cities; some of these cities are connected by airlines, so that an airline connects exactly two cities in each case and both flight directions are possible. Each airline belongs to one of $k$ flight companies; two airlines of the same flight company have always a common final point. Show that one can partition all cities in $k+2$ groups in such a way that two cities from exactly the same group are never connected by an airline with each other.

Jordan is in the center of a circle whose radius is $100$ meters and can move one meter at a time, however, there is a giant who at every step can force you to move in the opposite direction to the one he chose (it does not mean returning to the place of departure, but advance but in the opposite direction to the chosen one). Determine the minimum number of steps that Jordan must give to get out of the circle.

It is known that $a_1, a_2,...a_{108}$ are $108$ different positive integers not exceeding $2015$. Prove that there is a positive integer $k$ such that there are at least four different pairs $(i, j) $satisfying $a_i-a_j =k$.

On the plane 1000 lines are drawn, among which there are no parallel lines. From any seven of these lines, some three pass through one point. But no more than 500 lines pass through each point. Prove that there are three points such that each line contains at least of of them.

$N \ge 3$ different points are marked on the plane. It is known that among pairwise distances between marked points there are not more than $n$ different distances. Prove that $N \le (n + 1)^2$.

There are 1995 segments such that a triangle can be formed from any three of them. Prove that using these $1995 $ segments, it is possible to assemble $664$ acute-angled triangles so that each segment is part of no more than one triangle.

An ant craws along a closed route along the edges of a dodecahedron, never going backwards. Each edge of the route is passed exactly twice. Prove that one of the edges is passed both times in the same direction. (Dodecahedron has $12$ faces in the shape of pentagon, $30$ edges and $20$ vertices; each vertex emitting 3 edges). (8)

A finite set of points $X$ and an equilateral triangle $T$ are given on a plane. Suppose that every subset $X'$ of $X$ with no more than $9$ elements can be covered by two images of $T$ under translations. Prove that the whole set $X$ can be covered by two images of $T$ under translations.

. Anthony denotes in sequence all positive integers which are divisible by $2$. Bertha denotes in sequence all positive integers which are divisible by $3$. Claire denotes in sequence all positive integers which are divisible by $4$. Orderly Dora denotes all numbers written by the other three. Thereby she puts them in order by size and does not repeat a number. What is the $2017th$ number in her list? [i]¨Proposed by Richard Henner[/i]

Let $A$ be a subset of the edges of an $n\times n $ table. Let $V(A)$ be the set of vertices from the table which are connected to at least on edge from $A$ and $j(A)$ be the number of the connected components of graph $G$ which it's vertices are the set $V(A)$ and it's edges are the set $A$. Prove that for every natural number $l$: $$\frac{l}{2}\leq min_{|A|\geq l}(|V(A)|-j(A)) \leq \frac{l}{2}+\sqrt{\frac{l}{2}}+1$$

Consider the $9\times 9$ grid of lattice points $\{(x,y) | 0 \le x, y \le 8\}$. How many rectangles with nonzero area and sides parallel to the $x, y$ axes are there such that each corner is one of the lattice points and the point $(4, 4)$ is not contained within the interior of the rectangle? ($(4,4)$ is allowed to lie on the boundary of the rectangle).

Let $m, n$ be positive integers. Starting with all positive integers written in a line, we can form a list of numbers in two ways: $(1)$ Erasing every $m$-th and then, in the obtained list, erasing every $n$-th number; $(2)$ Erasing every $n$-th number and then, in the obtained list, erasing every $m$-th number. A pair $(m,n)$ is called [i]good[/i] if, whenever some positive integer $k$ occurs in both these lists, then it occurs in both lists on the same position. (a) Show that the pair $(2, n)$ is good for any $n\in \mathbb{N}$. (b) Is there a good pair $(m, n)$ with $2<m<n$?

Let $S = \{1,2,3,\ldots,n\}$. Consider a function $f\colon S\to S$. A subset $D$ of $S$ is said to be invariant if for all $x\in D$ we have $f(x)\in D$. The empty set and $S$ are also considered as invariant subsets. By $\deg (f)$ we define the number of invariant subsets $D$ of $S$ for the function $f$. [b]i)[/b] Show that there exists a function $f\colon S\to S$ such that $\deg (f)=2$. [b]ii)[/b] Show that for every $1\leq k\leq n$ there exists a function $f\colon S\to S$ such that $\deg (f)=2^{k}$.

[i]In this round, problems will depend on the answers to other problems. A bolded letter is used to denote a quantity whose value is determined by another problem's answer.[/i] [u]Part I[/u] [b]p1.[/b] Let F be the answer to problem number $6$. You want to tile a nondegenerate square with side length $F$ with $1\times 2$ rectangles and $1 \times 1$ squares. The rectangles can be oriented in either direction. How many ways can you do this? [b]p2.[/b] Let [b]A[/b] be the answer to problem number $1$. Triangle $ABC$ has a right angle at $B$ and the length of $AC$ is [b]A[/b]. Let $D$ be the midpoint of $AB$, and let $P$ be a point inside triangle $ABC$ such that $PA = PC = \frac{7\sqrt5}{4}$ and $PD = \frac74$ . The length of $AB^2$ is expressible as $m/n$ for $m, n$ relatively prime positive integers. Find $m$. [b]p3.[/b] Let [b]B[/b] be the answer to problem number $2$. Let $S$ be the set of positive integers less than or equal to [b]B[/b]. What is the maximum size of a subset of $S$ whose elements are pairwise relatively prime? [b]p4.[/b] Let [b]C[/b] be the answer to problem number $3$. You have $9$ shirts and $9$ pairs of pants. Each is either red or blue, you have more red shirts than blue shirts, and you have same number of red shirts as blue pants. Given that you have [b]C[/b] ways of wearing a shirt and pants whose colors match, find out how many red shirts you own. [b]p5.[/b] Let [b]D[/b] be the answer to problem number $4$. You have two odd positive integers $a, b$. It turns out that $lcm(a, b) + a = gcd(a, b) + b =$ [b]D[/b]. Find $ab$. [b]p6.[/b] Let [b]E[/b] be the answer to problem number $5$. A function $f$ defined on integers satisfies $f(y)+f(12-y) = 10$ and $f(y) + f(8 - y) = 4$ for all integers $y$. Given that $f($ [b]E[/b] $) = 0$, compute $f(4)$. [u]Part II[/u] [b]p7.[/b] Let [b]L[/b] be the answer to problem number $12$. You want to tile a nondegenerate square with side length [b]L[/b] with $1\times 2$ rectangles and $7\times 7$ squares. The rectangles can be oriented in either direction. How many ways can you do this? [b]p8.[/b] Let [b]G[/b] be the answer to problem number $7$. Triangle $ABC$ has a right angle at $B$ and the length of $AC$ is [b]G[/b]. Let $D$ be the midpoint of $AB$, and let $P$ be a point inside triangle $ABC$ such that $PA = PC = \frac12$ and $PD = \frac{1}{2010}$ . The length of $AB^2$ is expressible as $m/n$ for $m, n$ relatively prime positive integers. Find $m$. [b]p9.[/b] Let [b]H[/b] be the answer to problem number $8$. Let $S$ be the set of positive integers less than or equal to [b]H[/b]. What is the maximum size of a subset of $S$ whose elements are pairwise relatively prime? [b]p10.[/b] Let [b]I[/b] be the answer to problem number $9$. You have $391$ shirts and $391$ pairs of pants. Each is either red or blue, you have more red shirts than blue shirts, and you have same number of red shirts as red pants. Given that you have [b]I[/b] ways of wearing a shirt and pants whose colors match, find out how many red shirts you own. [b]p11.[/b] Let [b]J[/b] be the answer to problem number $10$. You have two odd positive integers $a, b$. It turns out that $lcm(a, b) + 2a = 2 gcd(a, b) + b = $ [b]J[/b]. Find $ab$. [b]p12.[/b] Let [b]K[/b] be the answer to problem number $11$. A function $f$ defined on integers satisfies $f(y)+f(7-y) = 8$ and $f(y) + f(5 - y) = 4$ for all integers $y$. Given that $f($ [b]K[/b] $) = 453$, compute $f(2)$. PS. You had better use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

A table $2 \times 2010$ is divided to unit cells. Ivan and Peter are playing the following game. Ivan starts, and puts horizontal $2 \times 1$ domino that covers exactly two unit table cells. Then Peter puts vertical $1 \times 2$ domino that covers exactly two unit table cells. Then Ivan puts horizontal domino. Then Peter puts vertical domino, etc. The person who cannot put his domino will lose the game. Find who have winning strategy.

A $k$-set is a set with exactly $k$ elements. For a $6$-set $A$ and any collection $\mathcal{F}$ of $4$-sets, we say that $A$ is [i]$\mathcal{F}$-good[/i] if there are exactly three elements $B_1, B_2, B_3$ in $\mathcal{F}$ that are subsets of $A$, and they furthermore satisfy $$(A \backslash B_1) \cup (A \backslash B_2) \cup (A \backslash B_3) = A.$$ Find all $n \geq 6$ so that there exists a collection $\mathcal{F}$ of $4$-subsets of $\{1, 2, \ldots , n\}$ such that every $6$-set $A \subseteq \{1, 2, \ldots , n\}$ is $\mathcal{F}$-good. [i] Proposed by usjl[/i]

Every positive integer $n>2$ can be written as a sum of distinct positive integers. Let $A(n)$ be the maximal number of summands in such a representation. Find a formula for $A(n).$

Let $n \ge 3$ be an odd integer. In a $2n \times 2n$ board, we colour $2(n-1)^2$ cells. What is the largest number of three-square corners that can surely be cut out of the uncoloured figure? [i]Proposed by G. Sharafetdinova[/i]

A polygon (not necessarily convex) on the coordinate plane is called [i]plump[/i] if it satisfies the following conditions: $\bullet$ coordinates of vertices are integers; $\bullet$ each side forms an angle of $0^\circ$, $90^\circ$, or $45^\circ$ with the abscissa axis; $\bullet$ internal angles belong to the interval $[90^\circ, 270^\circ]$. Prove that if a square of each side length of a plump polygon is even, then such a polygon can be cut into several convex plump polygons. [i](A. Yuran)[/i]

There are $2014$ balls with $106$ different colors, $19$ of each color. Determine the least possible value of $n$ so that no matter how these balls are arranged around a circle, one can choose $n$ consecutive balls so that amongst them, there are $53$ balls with different colors.

Determine all positive integers $n$ for which the square $n \times n$ can be cut into squares $2\times 2$ and $3\times3$ (with the sides parallel to the sides of the big square).

A planar country has an odd number of cities separated by pairwise distinct distances. Some of these cities are connected by direct two-way flights. Each city is directly connected to exactly two ther cities, and the latter are located farthest from it. Prove that, using these flights, one may go from any city to any other city

Let $n\in\mathbb{N}^*$ and $v_1,v_2,\ldots ,v_n$ be vectors in the plane with lengths less than or equal to $1$. Prove that there exists $\xi_1,\xi_2,\ldots ,\xi_n\in\{-1,1\}$ such that \[ | \xi_1v_1+\xi_2v_2+\ldots +\xi_nv_n|\le\sqrt{2}\]

$ A_1 , A_2 , \cdots , A_n $ are given subsets. Let $ S = \left\{ 1, 2, \cdots , n \right\} $. For any $ X \subset S $, let \[ N(X)= \left\{ i \in S-X \ | \ \forall j \in X, \ A_i \cap A_j \ne \emptyset \right\} \] Let $ m $ be an integer such that $ 3 \le m \le n-2 $. Prove that there exist $ X \subset S $ such that $ |X|=m $ and $ |N(X)| \ne 1 $.