$n\in{Z^{+}}$ and $A={1,\ldots ,n}$. $f: N\rightarrow N$ and $\sigma: N\rightarrow N$ are two permutations, if there is one $k\in A$ such that $(f\circ\sigma)(1),\ldots ,(f\circ\sigma)(k)$ is increasing and $(f\circ\sigma)(k),\ldots ,(f\circ\sigma)(n)$ is decreasing sequences we say that $f$ is good for $\sigma$. $S_\sigma$ shows the set of good functions for $\sigma$. a) Prove that, $S_\sigma$ has got $2^{n-1}$ elements for every $\sigma$ permutation. b)$n\geq 4$, prove that there are permutations $\sigma$ and $\tau$ such that, $S_{\sigma}\cap S_{\tau}=\phi$ .

There are $n$ boyfriend-girlfriend pairs at a party. Initially all the girls sit at a round table. For the first dance, each boy invites one of the girls to dance with.After each dance, a boy takes the girl he danced with to her seat, and for the next dance he invites the girl next to her in the counterclockwise direction. For which values of $n$ can the girls be selected in such a way that in every dance at least one boy danced with his girlfriend, assuming that there are no less than $n$ dances?

Let $S$ be a subset with $673$ elements of the set $\{1,2,\ldots ,2010\}$. Prove that one can find two distinct elements of $S$, say $a$ and $b$, such that $6$ divides $a+b$.

Let $ p$ and $ q$ be relatively prime positive integers. A subset $ S$ of $ \{0, 1, 2, \ldots \}$ is called [b]ideal[/b] if $ 0 \in S$ and for each element $ n \in S,$ the integers $ n \plus{} p$ and $ n \plus{} q$ belong to $ S.$ Determine the number of ideal subsets of $ \{0, 1, 2, \ldots \}.$

For positive integers $n$, let $S_n$ be the set of integers $x$ such that $n$ distinct lines, no three concurrent, can divide a plane into $x$ regions (for example, $S_2=\{3,4\}$, because the plane is divided into 3 regions if the two lines are parallel, and 4 regions otherwise). What is the minimum $i$ such that $S_i$ contains at least 4 elements?

Consider an infinite white plane divided into square cells. For which $k$ it is possible to paint a positive finite number of cells black so that on each horizontal, vertical and diagonal line of cells there is either exactly $k$ black cells or none at all? A. Dinev, K. Garov, N Belukhov

If there are four numbers $(a,b,c,d)$ in four registers of the calculating machine, they turn into $(a-b,b-c,c-d,d-a)$ numbers whenever you press the button. Prove that if not all the initial numbers are equal, machine will obtain at least one number more than $1985$ after some number of the operations.

To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers $x,y,z$ respectively, and $y<0$, then the following operation is allowed: $x,y,z$ are replaced by $x+y,-y,z+y$ respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.

In some cells of a rectangular table $m\times n (m, n> 1)$ is one checker. $Baby$ cut along the lines of the grid this table so that it is split into two equal parts, with the number of pieces on each side were the same. $Carlson$ changed the arrangement of checkers on the board (and on each side of the cage is still worth no more than one pieces). Prove that the $Baby$ may again cut the board into two equal parts containing an equal number of pieces

The integers $1, 2, 3, 4, 5$ and $6$ are written on a board. You can perform the following kind of move: select two of the numbers, say $a$ and $b$, such that $4a - 2b$ is nonnegative; erase $a$ and $b$, then write down $4a - 2b$ on the board (hence replacing two of the numbers by just one). Continue performing such moves until only one number remains on the board. What is the smallest possible positive value of this last remaining number?

Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n + 1$ squares in a row, numbered $0$ to $n$ from left to right. Initially, $n$ stones are put into square $0$, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of these stones and moves it to the right by at most $k$ squares (the stone should say within the board). Sisyphus' aim is to move all $n$ stones to square $n$. Prove that Sisyphus cannot reach the aim in less than \[ \left \lceil \frac{n}{1} \right \rceil + \left \lceil \frac{n}{2} \right \rceil + \left \lceil \frac{n}{3} \right \rceil + \dots + \left \lceil \frac{n}{n} \right \rceil \] turns. (As usual, $\lceil x \rceil$ stands for the least integer not smaller than $x$. )

In a chess tournament , every two participants play each other exactly once. A win is worth one point , a draw is worth half a point and a loss is worth zero points. Looking back at the end of the tournament, a game is called an upset if the total number of points obtained by the winner of that game is less than the total number of points obtained by the loser of that game. (a) Prove that the number of upsets is always strictly less than three-quarters of the total number of games in the tournament. (b) Prove that three-quarters cannot be replaced by a smaller number. (S Tokarev) PS. part (a) for Juniors, both parts for Seniors

At the beginning there are $2017$ marbles in each of $1000$ boxes. On each move Aybike chooses a box, grabs some of the marbles from that box and delivers them one for each to the boxes she wishes. At least how many moves does Aybike have to make to have different number of marbles in each box?

A chessboard with some unit squares marked is called a $\textit{good board}$ if for any pair of rows \((s, t)\), a rook placed on a marked square in row \(s\) can reach a marked square in row \(t\) in several moves by only moving to marked squares above, below, or to the right of its current position. Consider a chessboard with 220 rows and 12 columns, where exactly 9 unit squares in each row are marked. Regardless of how the marked squares are chosen, if it is possible to delete \(k\) columns and rearrange the remaining columns to form a $\textit{good board}$ determine the maximum possible value of \(k\).

The point $O{}$ is given in the plane. Find all natural numbers $n{}$ for which $n{}$ points in the plane can be colored red, so that for any two red points $A{}$ and $B{}$ there is a third red point $C{}$ is such that $O{}$ lies strictly inside the triangle $ABC$. [i]From the folklore[/i]

Two toads named Gamakichi and Gamatatsu are sitting at the points $(0,0)$ and $(2,0)$ respectively. Their goal is to reach $(5,5)$ and $(7,5)$ respectively by making one unit jumps in positive $x$ or $y$ direction at a time. How many ways can they do this while ensuring that there is no point on the plane where both Gamakichi And Gamatatsu land on?

The plane shows $2020$ straight lines in general position, that is, there are none three intersecting at one point but no two parallel. Let's say, that the drawn line $a$ [i]detaches [/i] the drawn line $b$ if all intersection points of line $b$ with the other drawn lines lie in one half plane wrt to line $a$ (given the most straightforward $a$). Prove that you can be guaranteed find two drawn lines $a$ and $b$ that $a$ detaches $b$, but $b$ does not detach $a$.

Per and Kari each have $n$ pieces of paper. They both write down the numbers from $1$ to $2n$ in an arbitrary order, one number on each side. Afterwards, they place the pieces of paper on a table showing one side. Prove that they can always place them so that all the numbers from $1$ to $2n$ are visible at once.

Find the largest positive integer $m$ which makes it possible to color several cells of a $70\times 70$ table red such that [list] [*] There are no two red cells satisfying: the two rows in which they are have the same number of red cells, while the two columns in which they are also have the same number of red cells; [*] There are two rows with exactly $m$ red cells each. [/list]

The points $(1,1),(2,3),(4,5)$ and $(999,111)$ are marked in the coordinate system. We continue to mark points in the following way : [list] [*]If points $(a,b)$ are marked then $(b,a)$ and $(a-b,a+b)$ can be marked [*]If points $(a,b)$ and $(c,d)$ are marked then so can be $(ad+bc, 4ac-4bd)$. [/list] Can we, after some finite number of these steps, mark a point belonging to the line $y=2x$.

2011 storage buildings are connected by roads so that it is possible to reach any building from any other building, possibly using multiple roads. The buildings contain $x_1,\dots,x_{2011}$ kilogram of cement. In one move, it is possible to relocate any quantity of cement from one building to any other building that is connected to it. The target is to have $y_1,\dots,y_{2011}$ redistributed across storage buildings and \[x_1+x_2+\dots+x_{2011}=y_1+y_2+\dots+y_{2011}.\] What is the minimal number of moves that the redistribution can take regardless of values of $x_i$ and $y_i$ and of the road plan? (Author: P. Karasev)

A safe is protected with a number of locks. Eleven members of the committee have keys for some of the locks. What is the smallest number of locks necessary so that every six members of the committee can open the safe, but no five members can do it? How should the keys be distributed among the committee members if the number of locks is the smallest?

Given an $ n\times n$ chessboard. a) Find the number of rectangles on the chessboard. b) Assume there exists an $ r\times r$ square (label $ B$) with $ r<n$ which is located on the upper left corner of the board. Define "inner border" of $ A$ as the border of $ A$ which is not the border of the chessboard. How many rectangles in $ B$ that touch exactly one inner border of $ B$?

A game is played by $n$ girls ($n \geq 2$), everybody having a ball. Each of the $\binom{n}{2}$ pairs of players, is an arbitrary order, exchange the balls they have at the moment. The game is called nice [b]nice[/b] if at the end nobody has her own ball and it is called [b]tiresome[/b] if at the end everybody has her initial ball. Determine the values of $n$ for which there exists a nice game and those for which there exists a tiresome game.

[u]Townspeople and Goons[/u] In the city of Lincoln, there is an empty jail, at least two townspeople and at least one goon. A game proceeds over several days, starting with morning. $\bullet$ Each morning, one randomly selected unjailed person is placed in jail. If at this point all goons are jailed, and at least one townsperson remains, then the townspeople win. If at this point all townspeople are jailed and at least one goon remains, then the goons win. $\bullet$ Each evening, if there is at least one goon and at least one townsperson not in jail, then one randomly selected townsperson is jailed. If at this point there are at least as many goons remaining as townspeople remaining, then the goons win. The game ends immediately after any group wins. [b]p1. [/b]Find the probability that the townspeople win if there are initially two townspeople and one goon. [b]p2.[/b] Find the smallest positive integer $n$ such that, if there are initially $2n$ townspeople and $1$ goon, then the probability the townspeople win is greater than $50\%$. [b]p3.[/b] Find the smallest positive integer $n$ such that, if there are initially $n + 1$ townspeople and $n$ goons, then the probability the townspeople win is less than $1\%$. [b]p4[/b]. Suppose there are initially $1001$ townspeople and two goons. What is the probability that, when the game ends, there are exactly $1000$ people in jail? [b]p5.[/b] Suppose that there are initially eight townspeople and one goon. One of the eight townspeople is named Jester. If Jester is sent to jail during some morning, then the game ends immediately in his sole victory. (However, the Jester does not win if he is sent to jail during some night.) Find the probability that only the Jester wins.