A simple graph has $N{}$ vertices and less than $3(N-1)/2$ edges. Prove that its vertices can be divided into two non-empty groups so that each vertex has at most one neighbor in the group it doesn't belong to.

Ben picks a positive number $n$ less than $2017$ uniformly at random. Then Rex, starting with the number $ 1$, repeatedly multiplies his number by $n$ and then finds the remainder when dividing by $2017$. Rex does this until he gets back to the number $ 1$. What is the probability that, during this process, Rex reaches every positive number less than $2017$ before returning back to $ 1$?

Consider $n$ persons, each of them speaking at most $3$ languages. From any $3$ persons there are at least two which speak a common language. i) For $n \le 8$, exhibit an example in which no language is spoken by more than two persons. ii) For $n \ge 9$, prove that there exists a language which is spoken by at least three persons

The teacher gave each of her $37$ students $36$ pencils in different colors. It turned out that each pair of students received exactly one pencil of the same color. Determine the smallest possible number of different colors of pencils distributed.

Given an initial integer $ n_0 > 1$, two players, $ {\mathcal A}$ and $ {\mathcal B}$, choose integers $ n_1$, $ n_2$, $ n_3$, $ \ldots$ alternately according to the following rules : [b]I.)[/b] Knowing $ n_{2k}$, $ {\mathcal A}$ chooses any integer $ n_{2k \plus{} 1}$ such that \[ n_{2k} \leq n_{2k \plus{} 1} \leq n_{2k}^2. \] [b]II.)[/b] Knowing $ n_{2k \plus{} 1}$, $ {\mathcal B}$ chooses any integer $ n_{2k \plus{} 2}$ such that \[ \frac {n_{2k \plus{} 1}}{n_{2k \plus{} 2}} \] is a prime raised to a positive integer power. Player $ {\mathcal A}$ wins the game by choosing the number 1990; player $ {\mathcal B}$ wins by choosing the number 1. For which $ n_0$ does : [b]a.)[/b] $ {\mathcal A}$ have a winning strategy? [b]b.)[/b] $ {\mathcal B}$ have a winning strategy? [b]c.)[/b] Neither player have a winning strategy?

On a planet there are $3\times2005!$ aliens and $2005$ languages. Each pair of aliens communicates with each other in exactly one language. Show that there are $3$ aliens who communicate with each other in one common language.

Georg has $2n + 1$ cards with one number written on each card. On one card the integer $0$ is written, and among the rest of the cards, the integers $k = 1, ... , n$ appear, each twice. Georg wants to place the cards in a row in such a way that the $0$-card is in the middle, and for each $k = 1, ... , n$, the two cards with the number $k$ have the distance $k$ (meaning that there are exactly $k - 1$ cards between them). For which $1 \le n \le 10$ is this possible?

Prove that there exists an undirected graph having $ 2004 $ vertices such that for any $ \in\{ 1,2,\ldots ,1002 \} , $ there exists at least two vertices whose orders are $ n. $

We have a $n\times n$ table and we’ve written numbers $0,+1 \ or \ -1$ in each $1\times1$ square such that in every row or column, there is only one $+1$ and one $-1$. Prove that by swapping the rows with each other and the columns with each other finitely, we can swap $+1$s with $-1$s.

An $n\times n$ square grid ($n\geqslant 3$) is rolled into a cylinder. Some of the cells are then colored black. Show that there exist two parallel lines (horizontal, vertical or diagonal) of cells containing the same number of black cells. [i]E. Poroshenko[/i]

Consider the configurations of integers $a_{1,1}$ $a_{2,1} \quad a_{2,2}$ $a_{3,1} \quad a_{3,2} \quad a_{3,3}$ $\dots \quad \dots \quad \dots$ $a_{2017,1} \quad a_{2017,2} \quad a_{2017,3} \quad \dots \quad a_{2017,2017}$ Where $a_{i,j} = a_{i+1,j} + a_{i+1,j+1}$ for all $i,j$ such that $1 \leq j \leq i \leq 2016$. Determine the maximum amount of odd integers that such configuration can contain.

Initially, on the blackboard are written all natural numbers from $1$ to $20$. A move consists of selecting $2$ numbers $a<b$ written on the blackboard such that their difference is at least $2$, erasing these numbers and writting $a+1$ and $b-1$ instead. What is the maximum numbers of moves one can perform?

Find the number of $10$-tuples $(a_1,a_2,\dots,a_9,a_{10})$ of integers such that $|a_1|\leq 1$ and \[a_1^2+a_2^2+a_3^2+\cdots+a_{10}^2-a_1a_2-a_2a_3-a_3a_4-\cdots-a_9a_{10}-a_{10}a_1=2.\]

On the board is written in decimal the integer positive number $N$. If it is not a single digit number, wipe its last digit $c$ and replace the number $m$ that remains on the board with a number $m -3c$. (For example, if $N = 1,204$ on the board, $120 - 3 \cdot 4 = 108$.) Find all the natural numbers $N$, by repeating the adjustment described eventually we get the number $0$.

A set $X=\{ x_1,x_2,\ldots,x_n \}$ consisting of $n$ positive integers is given. It is known that the greatest common divisor of any four different elements of $X$ is $1$. For every number $x_i$ let $m_i$ be the number of elements of $X$, which are divisible by $x_i$ For every $n \geq 4$, find the maximal possible value of the sum $m_1+\ldots+m_n$ [i]A. Vaidzelevich[/i]

Let $n$ be positive integer. Let $S_1,S_2,\cdots,S_k$ be a collection of $2n$-element subsets of $\{1,2,3,4,...,4n-1,4n\}$ so that $S_{i}\cap S_{j}$ contains at most $n$ elements for all $1\leq i<j\leq k$. Show that $$k\leq 6^{(n+1)/2}$$

4. Let $v$ and $w$ be two randomly chosen roots of the equation $z^{1997} -1 = 0$ (all roots are equiprobable). Find the probability that $\sqrt{2+\sqrt{3}}\le |u+w|$

A $\pm 1$-[i]sequence[/i] is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and $$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$

Find the maximum value of an integer $B$ such that for every 9 distinct natural number with the sum of $2023$, there must exist a sum of 4 of the number that is greater than or equal to $B$

Let $N$ be the set of natural numbers, and let $f: N \to N$ be a function satisfying $f(x) + f(x + 2) < 2 f(x + 1)$ for any $x \in N$. Prove that there exists a straight line in the $xy$-plane which contains infinitely many points with coordinates $(n,f(n))$.

Let $S$ be a string of $99$ characters, $66$ of which are $A$ and $33$ are $B$. We call $S$ [i]good[/i] if, for each $n$ such that $1\le n \le 99$, the sub-string made from the first $n$ characters of $S$ has an odd number of distinct permutations. How many good strings are there? Which strings are good?

[b](i)[/b] Determine the smallest number of edges which a graph of $ n$ nodes may have given that adding an arbitrary new edge would give rise to a 3-clique (3 nodes joined pairwise by edges). [b](ii)[/b] Determine the smallest number of edges which a graph of $ n$ nodes may have given that adding an arbitrary new edge would give rise to a 4-clique (4 nodes joined pairwise by edges).

Let $x_1,\ldots,x_n$ be real numbers. For any set $I\subset\{1,2,…,n\}$ let $s(I)=\sum_{i\in I}x_i$. Assume that the function $I\to s(I)$ takes on at least $1.8^n$ values where $I$ runs over all $2^n$ subsets of $\{1,2,…,n\}$. Prove that the number of sets $I\subset \{1,2,…,n\}$ for which $s(I)=2019$ does not exceed $1.7^n$. [i]Proposed by Fedor Part and Fedor Petrov, St. Petersburg State University[/i]

Given a finite set of points in the plane, each with integer coordinates, is it always possible to color the points red or white so that for any straight line $L$ parallel to one of the coordinate axes the difference (in absolute value) between the numbers of white and red points on $L$ is not greater than $1$?

The game of circulate is played with a deck of $kn$ cards each with a number in $1,2,\ldots,n$ such that there are $k$ cards with each number. First, $n$ piles numbered $1,2,\ldots,n$ of $k$ cards each are dealt out face down. The player then flips over a card from pile $1$, places that card face up at the bottom of the pile, then next flips over a card from the pile whose number matches the number on the card just flipped. The player repeats this until he reaches a pile in which every card has already been flipped and wins if at that point every card has been flipped. Hamster has grown tired of losing every time, so he decides to cheat. He looks at the piles beforehand and rearranges the $k$ cards in each pile as he pleases. When can Hamster perform this procedure such that he will win the game? [i]Brian Hamrick.[/i]