Let $G$ be a simple connected graph with $2016$ vertices and $k$ edges. We want to choose a set of vertices where there is no edge between them and delete all these chosen vertices (we delete both the vertices and all edges of these vertices) such that the remaining graph becomes unconnected. If we can do this task no matter how these $k$ edges are arranged (by making the graph connected), find the maximal value of $k$.

Secco and Ramon are drunk in the real line over the integer points $a$ and $b$, respectively. Our real line is a little bit special, though: the interval $(-\infty, 0)$ is covered by a sea of lava. Being aware of this fact, and also because they are drunk, they decided to play the following game: initially they choose an integer number $k>1$ using a fair dice as large as desired, and therefore they start the game. In the first round, each player writes the point $h$ for which it wants to go. After that, they throw a coin: if the result is heads, they go to the desired points; otherwise, they go to the points $2g - h$, where $g$ is the point where each of the players were in the precedent round (that is, in the first round $g = a$ for Secco and $g = b$ for Ramon). They repeat this procedure in the other rounds, and the game finishes when some of the player is over a point exactly $k$ times bigger than the other (if both of the player end up in the point $0$, the game finishes as well). Determine, in values of $k$, the initial values $a$ and $b$ such that Secco and Ramon has a winning strategy to finish the game alive. [i]Observation: If any of the players fall in the lave, he dies and both of them lose the game[/i]

$n$ children want to divide $m$ identical pieces of chocolate into equal amounts, each piece being broken not more than once. (a) For what $n$ is it possible, if $m = 9$? (b) For what $n$ and $m$ is it possible? (Y. Tschekanov, Moscow)

Let $N$ be a positive integer, and consider an $N \times N$ grid. A [i]right-down path[/i] is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A [i]right-up path[/i] is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence. Prove that the cells of the $N \times N$ grid cannot be partitioned into less than $N$ right-down or right-up paths. For example, the following partition of the $5 \times 5$ grid uses $5$ paths. [asy] size(4cm); draw((5,-1)--(0,-1)--(0,-2)--(5,-2)--(5,-3)--(0,-3)--(0,-4)--(5,-4),gray+linewidth(0.5)+miterjoin); draw((1,-5)--(1,0)--(2,0)--(2,-5)--(3,-5)--(3,0)--(4,0)--(4,-5),gray+linewidth(0.5)+miterjoin); draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,black+linewidth(2.5)+miterjoin); draw((0,-1)--(3,-1)--(3,-2)--(1,-2)--(1,-4)--(4,-4)--(4,-3)--(2,-3)--(2,-2),black+linewidth(2.5)+miterjoin); draw((3,0)--(3,-1),black+linewidth(2.5)+miterjoin); draw((1,-4)--(1,-5),black+linewidth(2.5)+miterjoin); draw((4,-3)--(4,-1)--(5,-1),black+linewidth(2.5)+miterjoin); [/asy] [i]Proposed by Zixiang Zhou, Canada[/i]

On a $10 \times 10$ chessboard, several knights are placed, and in any $2 \times 2$ square there is at least one knight. What is the smallest number of cells these knights can threat? (The knight does not threat the square on which it stands, but it does threat the squares on which other knights are standing.)

Fourteen coins are submitted to the judge. An expert knows, that the coins from number one to seven are false, and from $8$ to $14$ -- normal. The judge is sure only that all the true coins have the same weight and all the false coins weights equal each other, but are less then the weight of the true coins. The expert has the scales without weights. a) The expert wants to prove, that the coins $1--7$ are false. How can he do it in three weighings? b) How can he prove, that the coins $1--7$ are false and the coins $8--14$ are true in three weighings?

Let $n > 1$ be an integer and $X = \{1, 2, \cdots , n^2 \}$. If there exist $x, y$ such that $x^2\mid y$ in all subsets of $X$ with $k$ elements, find the least possible value of $k$.

In a certain language there are $n$ letters. A sequence of letters is a word, if there are no two equal letters between two other equal letters. Find the number of words of the maximum length.

There are four wise men in a row, each sees only those following him in the row, i.e. the $1$st sees the other three, the $2$nd sees the $3$rd and $4$th, and the $3$rd sees only the $4$th. The devil has $100$ hats, numbered from $1$ to $100$, he puts one hat on each wise man, and hides the extra $96$ hats. After that, each wise man (in turn: first the first, then the second, etc.) loudly calls a number, trying to guess the number of his hat. The numbers mentioned should not be repeated. When all the wise men have spoken, they take off their hats and check which one of them has guessed. Can the sages to act in such a way that at least three of them knowingly guessed?

Alexandre and Bernado are playing the following game. At the beginning, there are $n$ balls in a bag. At first turn, Alexandre can take one ball from the bag; at second turn, Bernado can take one or two balls from the bag, and so on. So they take turns and in $k$ turn, they can take a number of balls from $1$ to $k$. Wins the one who makes the bag empty. For each value of $n$, find who has the winning strategy.

Vika calls some positive integers [i]nice[/i], and it is known that among any ten consecutive positive integers there is at least one nice. Prove that there are infinitely many positive integers $n$ for which $ab-cd=2n^2$ for some pairwise distinct nice numbers $a,b,c,$ and $d$

Gleb picked positive integers $N$ and $a$ ($a < N$). He wrote the number $a$ on a blackboard. Then each turn he did the following: he took the last number on the blackboard, divided the number $N$ by this last number with remainder and wrote the remainder onto the board. When he wrote the number $0$ onto the board, he stopped. Could he pick $N$ and $a$ such that the sum of the numbers on the blackboard would become greater than $100N$ ? Ivan Mitrofanov

I'll post some nice combinatorics problems here, taken from the wonderful training book "Les olympiades de mathmatiques" (in French) written by Tarik Belhaj Soulami. Here goes the first one: Let $\mathbb{I}$ be a non-empty subset of $\mathbb{Z}$ and let $f$ and $g$ be two functions defined on $\mathbb{I}$. Let $m$ be the number of pairs $(x,\;y)$ for which $f(x) = g(y)$, let $n$ be the number of pairs $(x,\;y)$ for which $f(x) = f(y)$ and let $k$ be the number of pairs $(x,\;y)$ for which $g(x) = g(y)$. Show that \[2m \leq n + k.\]

Let $n\ge 3$ be an integer. In a game there are $n$ boxes in a circular array. At the beginning, each box contains an object which can be rock, paper or scissors, in such a way that there are no two adjacent boxes with the same object, and each object appears in at least one box. Same as in the game, rock beats scissors, scissors beat paper, and paper beats rock. The game consists on moving objects from one box to another according to the following rule: [i]Two adjacent boxes and one object from each one are chosen in such a way that these are different, and we move the loser object to the box containing the winner object. For example, if we picked rock from box A and scissors from box B, we move scossors to box A.[/i] Prove that, applying the rule enough times, it is possible to move all the objects to the same box. [i]Proposed by Victor de la Fuente[/i]

For a binary string $S$ (i.e. a string of 0 's and 1's) that contains at least one 0 , we produce a binary string $f(S)$ as follows: - If the substring 110 occurs in $S$, replace each instance of 110 with 01 to produce $f(S)$; - Otherwise, replace the leftmost occurrence of 0 in $S$ by 1 to produce $f(S)$. Given binary string $S$ of length $n$, we define the lifetime of $S$ to be the number of times $f$ can be applied to $S$ until the resulting string contains no more 0 's. For example, $$

A tourist has arrived on an island where $100$ wizards live, each of whom can be a knight or a liar. He knows that at the time of his arrival, one of the hundred wizards is a knight (but does not know who exactly), and the rest are liars. A tourist can choose any two wizards $A$ and $B$ and ask $A$ to spell on $B$ with the spell "Whoosh"!, which changes the essence (turns a knight into a liar, and a liar into a knight). Wizards fulfill the tourist's requests, but if at that moment wizard $A$ is a knight, then the essence of $B$ really changes, and if $A$ is a liar, that doesn't change. The tourist wants to know the essence of at least $k$ wizards at the same time after several consecutive requests. For which maximum $k$ will he be able to achieve his goal?

Each positive integer shall be coloured red or green such that it satisfies the following properties: - The sum of three not necessarily distinct red numbers is a red number. - The sum of three not necessarily distinct green numbers is a green number. - There are red and green numbers. Find all such colorations!

Let $ n $ be a positive integer. A sequence $(a_1,a_2,\ldots,a_n)$ of length is called $balanced$ if for every $ k $ $(1\leq k\leq n)$ the term $ a_k $ is equal with the number of distinct numbers from the subsequence $(a_1,a_2,\ldots,a_k).$ a) How many balanced sequences $(a_1,a_2,\ldots,a_n)$ of length $ n $ do exist? b) For every positive integer $m$ find how many balanced sequences $(a_1,a_2,\ldots,a_n)$ of length $ n $ exist such that $a_n=m.$

We are given the natural numbers $1=a_1,\, \, a_2,...,a_n$, for which $a_i\leq a_{i+1}\leq 2a_i$ for $i=1,2,...,n-1$ and the sum $\sum_{i=1}^n a_i$ is even. Prove that these numbers can be partitioned into two groups with equal sum.

Johann and Nicole are playing a game on the coordinate plane. First, Johann draws any polygon $\mathcal{S}$ and then Nicole can shift $\mathcal{S}$ to wherever she wants. Johann wins if there exists a point with coordinates $(x, y)$ in the interior of $\mathcal{S}$, where $x$ and $y$ are coprime integers. Otherwise, Nicole wins. Determine who has a winning strategy.

Consider partitions of an $n \times n$ square (composed of $n^2$ unit squares) into rectangles with one integer side and the other side equal to $1$. What is the largest possible number of such partitions among which no two have an identical rectangle at the same place?

A rook is randomly placed on an otherwise empty $8 \times 8$ chessboard. Owen makes moves with the rook by randomly choosing $1$ of the $14$ possible moves. Find the expected value of the number of moves it takes Owen to move the rook to the top left square. Note that a rook can move any number of squares either in the horizontal or vertical direction each move.

How many ways are there to line up $19$ girls (all of different heights) in a row so that no girl has a shorter girl both in front of and behind her?

It is about deciphering the code $C_1C_2C_3C_4$ in which each letter is one of the colors: white $(B)$, blue $(A)$, red $(R)$, green $(V)$, black $(N)$ and brown $(C)$ with allowed repetitions. Four were made attempts to decipher it. $NAVB$ and $ACRC$ have two color hits, but in wrong places. $RBAC$ and $VRBA$ have one color match in the correct place, and two other color matches, in places incorrect. Determine all combinations compatible with the information.

A sequence of integers $(a_0,...,a_k)$ is said to be [i]medaled[/i] if, for each $i = 0,...,k$, there are exactly $a_i$ elements of the sequence equal to $i$. For example, $(1,2,1,0)$ is a [i]medaled [/i] seqence. Indicates all [i]medaled [/i] sequences $(a_0,...,a_{2015})$.