Let $n>1$ be an integer and let $f_1$, $f_2$, ..., $f_{n!}$ be the $n!$ permutations of $1$, $2$, ..., $n$. (Each $f_i$ is a bijective function from $\{1,2,...,n\}$ to itself.) For each permutation $f_i$, let us define $S(f_i)=\sum^n_{k=1} |f_i(k)-k|$. Find $\frac{1}{n!} \sum^{n!}_{i=1} S(f_i)$.

Define a sequence: $x_0=1$ and for all $n\ge 0$, $x_{2n+1}=x_{n}$ and $x_{2n+2}=x_{n}+x_{n+1}$. Prove that for any relatively prime positive integers $a$ and $b$, there is a non-negative integer $n$ such that $a=x_n$ and $b=x_{n+1}$.

Sets \(X\subset \mathbb{Z}^{+}\) and \(Y\subset \mathbb{Z}^{+}\) are called [i]comradely[/i], if every positive integer \(n\) can be written as \(n=xy\) for some \(x\in X\) and \(y\in Y\). Let \(X(n)\) and \(Y(n)\) denote the number of elements of \(X\) and \(Y\), respectively, among the first \(n\) positive integers. Let \(f\colon \mathbb{Z}^{+}\to \mathbb{R}^{+}\) be an arbitrary function that goes to infinity. Prove that one can find comradely sets \(X\) and \(Y\) such that \(\dfrac{X(n)}{n}\) and \(\dfrac{Y(n)}{n}\) goes to \(0\), and for all \(\varepsilon>0\) exists \(n \in \mathbb{Z}^+\) such that \[\frac{\min\big\{X(n), Y(n)\big\}}{f(n)}<\varepsilon. \]

For a positive integer $n$, let $s(n)$ denote the sum of the binary digits of $n$. Find the sum $s(1)+s(2)+s(3)+...+s(2^k)$ for each positive integer $k$.

Let $d(n)$ be the number of positive divisors of a positive integer $n$. Let $\mathbb{N}$ be the set of all positive integers. Say that a function $F$ from $\mathbb{N}$ to $\mathbb{N}$ is [i]divisor-respecting[/i] if $d(F(mn)) = d(F(m)) d(F(n))$ for all positive integers $m$ and $n$, and $d(F(n)) \le d(n)$ for all positive integers $n$. Find all divisor-respecting functions. Justify your answer.

For a sequence of integers $a_1 < a_2 < \cdot\cdot\cdot < a_n$, a pair $(a_i,a_j)$ where $1 \leq i < j \leq n$ is said to be [i]balanced[/i] if the number $\frac{a_i+a_j}{2}$ belongs to the sequence. For every natural number $n \geq 3$, find the maximum possible number of balanced pairs in a sequence with $n$ numbers.

The points $M$ and $N$ are located respectively on the diagonal $(AC)$ and the side $(BC)$ of the square $ABCD$ such that $MN = MD$. Determine the measure of the angle $MDN$.

A collector of rare coins has coins of denominations $1, 2,..., n$ (several coins for each denomination). He wishes to put the coins into $5$ boxes so that: (1) in each box there is at most one coin of each denomination; (2) each box has the same number of coins and the same denomination total; (3) any two boxes contain all the denominations; (4) no denomination is in all $5$ boxes. For which $n$ is this possible?

There are coins worth $1, 2, \ldots , b$ rubles, blue bills with worth $a{}$ rubles and red bills worth $a + b$ rubles. Ilya wants to exchange a certain amount into coins and blue bills, and use no more than $a-1$ coins. Pasha wants to exchange the same amount in coins and red bills, but use no more than $a{}$ coins. Prove that they have equally many ways of doing so.

A man gets lost in a large forest, the boundary of which is a straight line. (We can assume that the forest fills the half-plane.) It is known that the distance from a person to Granina forest does not exceed $2$ km. a) Suggest a path along which he will certainly be able to get out of the forest after walking no more than $14$ km. (Of course, a person does not know in which direction the border of the forest is, BUT he has the opportunity to move along any pre-selected curve. It is believed that a person left the forest as soon as he reached its border, while the border of the forest is invisible to him, no matter how close he would have approached it.) b) Find a path with the same property and length no more than $13$ km.

Find all complex roots (with multiplicities) of the polynomial $$p(x)=\sum_{n=1}^{2008}(1004-|1004-n|)x^n.$$

Let \[f(x)=x^4-6x^3+26x^2-46x+65.\] Let the roots of $f(x)$ be $a_k+ib_k$ for $k=1,2,3,4$. Given that the $a_k$, $b_k$ are all integers, find $|b_1|+|b_2|+|b_3|+|b_4|.$

A circle is inscribed in the triangle $ ABC$ and it's center $I$ and the points of tangency $P, Q, R$ with the sides $BC$, $C A$ and $AB$ are marked, respectively. With a single ruler, build a point $K$ at which the circle passing through the vertices B and $C$ touches (internally) the inscribed circle.

Find the maximal possible finite number of roots of the equation $|x-a_1|+\dots+|x-a_{50}|=|x-b_1|+\dots+|x-b_{50}|$, where $a_1,\,a_2,\,\dots,a_{50},\,b_1,\dots,\,b_{50}$ are distinct reals.

A triangle ABC is inscribed in a circle with center $ O$ and radius $ R$. If the inradii of the triangles $ OBC, OCA, OAB$ are $ r_{1}, r_{2}, r_{3}$ , respectively, prove that $ \frac{1}{r_{1}}+\frac{1}{r_{2}}+\frac{1}{r_{3}}\geq\frac{4\sqrt{3}+6}{R}.$

Let $ ABC$ be an isosceles triangle with $ AB\equal{}AC$ and $ \angle A\equal{}20^\circ$. On the side $ AC$ consider point $ D$ such that $ AD\equal{}BC$. Find $ \angle BDC$.

The euclidean plane is divided into regions by drawing a finite number of circles. Show that it is possible to color each of these regions either red or blue in such a way that no two adjacent regions have the same color.

Let $C_0$ be the midpoint of hypotenuse $AB$ of triangle $ABC$; $AA_1, BB_1$ the bisectors of this triangle; $I$ its incenter. Prove that the lines $C_0I$ and $A_1B_1$ meet on the altitude from $C$. [i]Proposed by A.Zaslavsky[/i]

Antonio plays a game where he continually flips a fair coin to see the sequence of heads ($H$) and tails ($T$) that he flips. Antonio wins the game if he sees on four consecutive flips the sequence $TTHT$ before he sees the sequence $HTTH$. The probability that Antonio wins the game is $\frac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. Find $m + n$.

In a race among 5 snails, there is at most one tie, but that tie can involve any number of snails. For example, the result of the race might be that Dazzler is first; Abby, Cyrus, and Elroy are tied for second, and Bruna is fifth. How many different results of the race are possible? $ \textbf{(A) }180 \qquad \textbf{(B) }361 \qquad \textbf{(C) }420 \qquad \textbf{(D) }431 \qquad \textbf{(E) }720 \qquad $

Gary purchased a large beverage, but drank only $m/n$ of this beverage, where $m$ and $n$ are relatively prime positive integers. If Gary had purchased only half as much and drunk twice as much, he would have wasted only $\frac{2}{9}$ as much beverage. Find $m+n$.

Prove that there exist infinitely many positive integer triples $(a,b,c)(a,b,c>2015)$ such that $$ a|bc-1, b|ac+1, c|ab+1.$$

Source: 2017 Canadian Open Math Challenge, Problem A1 ----- The average of the numbers $2$, $5$, $x$, $14$, $15$ is $x$. Determine the value of $x$ .

An infinite set $B$ consisting of positive integers has the following property. For each $a,b \in B$ with $a>b$ the number $\frac{a-b}{(a,b)}$ belongs to $B$. Prove that $B$ contains all positive integers. Here, $(a,b)$ is the greatest common divisor of numbers $a$ and $b$.

Suppose $x$ and $y$ are nonzero real numbers simultaneously satisfying the equations $x + \frac{2018}{y}= 1000$ and $ \frac{9}{x}+ y = 1$. Find the maximum possible value of $x + 1000y$.