Consider a sequence of numbers $(a_1, a_2, \ldots , a_{2^n}).$ Define the operation \[S\biggl((a_1, a_2, \ldots , a_{2^n})\biggr) = (a_1a_2, a_2a_3, \ldots , a_{2^{n-1}a_{2^n}, a_{2^n}a_1).}\] Prove that whatever the sequence $(a_1, a_2, \ldots , a_{2^n})$ is, with $a_i \in \{-1, 1\}$ for $i = 1, 2, \ldots , 2^n,$ after finitely many applications of the operation we get the sequence $(1, 1, \ldots, 1).$

Let $A$ be a set of $N$ residues $\pmod{N^2}$. Prove that there exists a set $B$ of $N$ residues $\pmod{N^2}$ such that the set $A+B=\{a+b \vert a \in A, b \in B \}$ contains at least half of all the residues $\pmod{N^2}$.

Let a sequences: $ x_0\in [0;1],x_{n\plus{}1}\equal{}\frac56\minus{}\frac43 \Big|x_n\minus{}\frac12\Big|$. Find the "best" $ |a;b|$ so that for all $ x_0$ we have $ x_{2009}\in [a;b]$

The vertices of a connected graph cannot be coloured with less than $n+1$ colours (so that adjacent vertices have different colours). Prove that $\dfrac{n(n-1)}{2}$ edges can be removed from the graph so that it remains connected. [i]V. Dolnikov[/i] [b]EDIT.[/b] It is confirmed by the official solution that the graph is tacitly assumed to be [b]finite[/b].

There were finitely many persons at a party among whom some were friends. Among any $4$ of them there were either $3$ who were all friends among each other or $3$ who weren't friend with each other. Prove that you can separate all the people at the party in two groups in such a way that in the first group everyone is friends with each other and that all the people in the second group are not friends to anyone else in second group. (Friendship is a mutual relation).

Let $k$ be a positive integer. Prove that one can partition the set $\{ 0,1,2,3, \cdots ,2^{k+1}-1 \}$ into two disdinct subsets $\{ x_1,x_2, \cdots, x_{2k} \}$ and $\{ y_1, y_2, \cdots, y_{2k} \}$ such that $\sum_{i=1}^{2^k} x_i^m =\sum_{i=1}^{2^k} y_i^m$ for all $m \in \{ 1,2, \cdots, k \}$.

The following solitaire game is played on an $m\times n$ rectangular board, $m,n\ge 2$, divided into unit squares. First, a rook is placed on some square. At each move, the rook can be moved an arbitrary number of squares horizontally or vertically, with the extra condition that each move has to be made in the $90^{\circ}$ clockwise direction compared to the previous one (e.g. after a move to the left, the next one has to be done upwards, the next one to the right etc). For which values of $m$ and $n$ is it possible that the rook visits every square of the board exactly once and returns to the first square? (The rook is considered to visit only those squares it stops on, and not the ones it steps over.)

Determine all pairs $(n,m)$ of positive integers for which there exists an infinite sequence $\{x_k\}$ of $0$'s and $1$'s with the properties that if $x_i=0$ then $x_{i+m}=1$ and if $x_i = 1$ then $x_{i+n} = 0.$

There are 2000 cities in Graphland; some of them are connected by roads. For every city the number of roads going from it is counted. It is known that there are exactly two equal numbers among all the numbers obtained. What can be these numbers?

A function $f(x)$ defined for $x\ge 0$ satisfies the following conditions: i. for $x,y\ge 0$, $f(x)f(y)\le x^2f(y/2)+y^2f(x/2)$; ii. there exists a constant $M$($M>0$), such that $|f(x)|\le M$ when $0\le x\le 1$. Prove that $f(x)\le x^2$.

In some finite set of positive numbers, each number is expressed as a linear combination of the rest with rational non-negative coefficients. Prove that the ratio of some two numbers in the set is rational.

If $x_{1},x_{2},...,x_{n}(n>2)$ are positive real numbers with $x_{1}+x_{2}+...+x_{n}=1$. Prove that $x_{1}^{2}x_{2}+x_{2}^{2}x_{3}+...+x_{n}^{2}x_{1}\leq\frac{4}{27}$.

$ 2^n $ coins are given to a couple of kids. Interchange of the coins occurs when some of the kids has at least half of all the coins. Then from the coins of one of those kids to the all other kids are given that much coins as the kid already had. In case when all the coins are at one kid there is no possibility for interchange. What is the greatest possible number of consecutive interchanges? ($ n $ is natural number)

Consider a $ n\times n $ square grid which is divided into $ n^2 $ unit squares(think of a chess-board). The set of all unit squares intersecting the main diagonal of the square or lying under it is called an $n$-staircase. Find the number of ways in which an $n$-stair case can be partitioned into several rectangles, with sides along the grid lines, having mutually distinct areas.

Given an integer $n\ge 2$. Prove that there only exist a finite number of n-tuples of positive integers $(a_1,a_2,\ldots,a_n)$ which simultaneously satisfy the following three conditions: [list] [*] $a_1>a_2>\ldots>a_n$; [*] $\gcd (a_1,a_2,\ldots,a_n)=1$; [*] $a_1=\sum_{i=1}^{n}\gcd (a_i,a_{i+1})$,where $a_{n+1}=a_1$.[/list]

Determine whether there exists a function $ f: \mathbb{N}\longrightarrow \mathbb{N}$ such that $ f(n)\equal{}f(f(n\minus{}1))\plus{}f(f(n\plus{}1))$ for all natural numbers $ n\ge 2$.

Find all integers $b$ such that there exists a positive real number $x$ with \[ \dfrac {1}{b} = \dfrac {1}{\lfloor 2x \rfloor} + \dfrac {1}{\lfloor 5x \rfloor} \] Here, $\lfloor y \rfloor$ denotes the greatest integer that is less than or equal to $y$.

We call an integer $ n > 1$ [i]good[/i] if, for any natural numbers $ 1 \le b_1, b_2, \ldots , b_{n\minus{}1} \le n \minus{} 1$ and any $ i \in \{0, 1, \ldots , n \minus{} 1\}$, there is a subset $ I$ of $ \{1, \ldots , n \minus{} 1\}$ such that $ \sum_{k\in I} b_k \equiv i \pmod n$. (The sum over the empty set is zero.) Find all good numbers.

Consider the sequence $ \{a_n\}_{n\geq1}$ defined as follows: $ a_1 \equal{} 1$, $ a_{2k} \equal{} 1 \plus{} a_k$ and $ a_{2k \plus{} 1} \equal{} \frac {1}{a_{2k}}$ for every $ k\geq 1$. Prove that every positive rational number appears on the sequence $ \{a_n\}$ exactly once.

Find all integers $n$, $n \ge 1$, such that $n \cdot 2^{n+1}+1$ is a perfect square.

Consider a stripe of $n$ fieds, numbered from left to right with the integers $1$ to $n$ in ascending order. Each of the fields is colored with one of the colors $1$, $2$ or $3$. Even-numbered fields can be colored with any color. Odd-numbered fields are only allowed to be colored with the odd colors $1$ and $3$. How many such colorings are there such that any two neighboring fields have different colors?

Let $ c$ be a positive integer. The sequence $ a_1,a_2,\ldots$ is defined as follows $ a_1\equal{}c$, $ a_{n\plus{}1}\equal{}a_n^2\plus{}a_n\plus{}c^3$ for all positive integers $ n$. Find all $ c$ so that there are integers $ k\ge1$ and $ m\ge2$ so that $ a_k^2\plus{}c^3$ is the $ m$th power of some integer.

Let the sequence of real numbers $(a_n),n=1,2,3...$ with $a_1=2$ and $a_n=\left(\frac{n+1}{n-1} \right)\left(a_1+a_2+...+a_{n-1} \right),n\geq 2$. Find the term $a_{2013}$.

Find all the functions $f(x),$ continuous on the whole real axis, such that for every real $x$ \[f(3x-2)\leq f(x)\leq f(2x-1).\] [i]Proposed by A. Golovanov[/i]

Let $A_1,A_2,\ldots,A_n$ be subsets of a finite set $S$ such that $|A_j|=8$ for each $j$. For a subset $B$ of $S$ let $F(B)=\{j \mid 1\le j\le n \ \ \text{and} \ A_j \subset B\}$. Suppose for each subset $B$ of $S$ at least one of the following conditions holds [list][b](a)[/b] $|B| > 25$, [b](b)[/b] $F(B)={\O}$, [b](c)[/b] $\bigcap_{j\in F(B)} A_j \neq {\O}$.[/list] Prove that $A_1\cap A_2 \cap \cdots \cap A_n \neq {\O}$.