Let $G$ be a simple graph with $3n^2$ vertices ($n\geq 2$). It is known that the degree of each vertex of $G$ is not greater than $4n$, there exists at least a vertex of degree one, and between any two vertices, there is a path of length $\leq 3$. Prove that the minimum number of edges that $G$ might have is equal to $\frac{(7n^2- 3n)}{2}$.

We consider graphs with vertices colored black or white. "Switching" a vertex means: coloring it black if it was formerly white, and coloring it white if it was formerly black. Consider a finite graph with all vertices colored white. Now, we can do the following operation: Switch a vertex and simultaneously switch all of its neighbours (i. e. all vertices connected to this vertex by an edge). Can we, just by performing this operation several times, obtain a graph with all vertices colored black? [It is assumed that our graph has no loops (a [i]loop[/i] means an edge connecting one vertex with itself) and no multiple edges (a [i]multiple edge[/i] means a pair of vertices connected by more than one edge).]

Let $m,n$ be natural numbers and let $d = gcd(m,n)$. Let $x = 2^{m} -1$ and $y= 2^n +1$ (a) If $\frac{m}{d}$ is odd, prove that $gcd(x,y) = 1$ (b) If $\frac{m}{d}$ is even, Find $gcd(x,y)$

Prove that a graph containing a copy of each possible tree on $n$ vertices as a subgraph has at least $n(\ln n - 2)$ edges.

Mr. Fat and Ms. Taf play a game. Mr. Fat chooses a sequence of positive integers $ k_1, k_2, \ldots , k_n$. Ms. Taf must guess this sequence of integers. She is allowed to give Mr. Fat a red card and a blue card, each with an integer written on it. Mr. Fat replaces the number on the red card with $ k_1$ times the number on the red card plus the number on the blue card, and replaces the number on the blue card with the number originally on the red card. He repeats this process with number $ k_2$. (That is, he replaces the number on the red card with $ k_2$ times the number now on the red card plus the number now on the blue card, and replaces the number on the blue card with the number that was just placed on the red card.) He then repeats this process with each of the numbers $ k_3, \ldots k_n$, in this order. After has has gone through the sequence of integers, Mr. Fat then gives the cards back to Ms. Taf. How many times must Ms. Taf submit the red and blue cards in order to be able to determine the sequence of integers $ k_1, k_2, \ldots k_n$?

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.

Let $S$ be the set of all pairs $(a,b)$ of real numbers satisfying $1+a+a^2+a^3 = b^2(1+3a)$ and $1+2a+3a^2 = b^2 - \frac{5}{b}$. Find $A+B+C$, where \[ A = \prod_{(a,b) \in S} a , \quad B = \prod_{(a,b) \in S} b , \quad \text{and} \quad C = \sum_{(a,b) \in S} ab. \][i]Proposed by Evan Chen[/i]

Sequences $ (x_n)$ and $ (y_n)$ are constructed as follows: $ x_0 \equal{} 365$, $ x_{n\plus{}1} \equal{} x_n\left(x^{1986} \plus{} 1\right) \plus{} 1622$, and $ y_0 \equal{} 16$, $ y_{n\plus{}1} \equal{} y_n\left(y^3 \plus{} 1\right) \minus{} 1952$, for all $ n \ge 0$. Prove that $ \left|x_n\minus{} y_k\right|\neq 0$ for any positive integers $ n$, $ k$.

Consider all sets of $n$ distinct positive integers, no three of which form an arithmetic progression. Prove that among all such sets there is one which has the largest sum of the reciprocals of its elements.

On the infinite chessboard several rectangular pieces are placed whose sides run along the grid lines. Each two have no squares in common, and each consists of an odd number of squares. Prove that these pieces can be painted in four colours such that two pieces painted in the same colour do not share any boundary points.

There are 2000 cities in a country and no roads. Prove that some cities can be connected by a road such that there would be 2 cities with 1 road passing through them, there would be 2 cities with 2 roads passim through them,...,there would be 2 cities with 1000 roads passing through them. [I]Proposed by F. Bakharev[/i]

Let $T$ be the set of ordered triples $(x,y,z)$, where $x,y,z$ are integers with $0\leq x,y,z\leq9$. Players $A$ and $B$ play the following guessing game. Player $A$ chooses a triple $(x,y,z)$ in $T$, and Player $B$ has to discover $A$[i]'s[/i] triple in as few moves as possible. A [i]move[/i] consists of the following: $B$ gives $A$ a triple $(a,b,c)$ in $T$, and $A$ replies by giving $B$ the number $\left|x+y-a-b\right |+\left|y+z-b-c\right|+\left|z+x-c-a\right|$. Find the minimum number of moves that $B$ needs to be sure of determining $A$[i]'s[/i] triple.

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.

The image shown below is a cross with length 2. If length of a cross of length $k$ it is called a $k$-cross. (Each $k$-cross ahs $6k+1$ squares.) [img]http://aycu08.webshots.com/image/4127/2003057947601864020_th.jpg[/img] a) Prove that space can be tiled with $1$-crosses. b) Prove that space can be tiled with $2$-crosses. c) Prove that for $k\geq5$ space can not be tiled with $k$-crosses.

In a $2\times n$ array we have positive reals s.t. the sum of the numbers in each of the $n$ columns is $1$. Show that we can select a number in each column s.t. the sum of the selected numbers in each row is at most $\frac{n+1}4$.

We have $2p-1$ integer numbers, where $p$ is a prime number. Prove that we can choose exactly $p$ numbers (from these $2p-1$ numbers) so that their sum is divisible by $p$.

100 people from 25 countries, four from each countries, stay on a circle. Prove that one may partition them onto 4 groups in such way that neither no two countrymans, nor two neighbours will be in the same group.

Let $A_{1}A_{2}B_{1}B_{2}$ be a convex quadrilateral. At adjacent vertices $A_{1}$ and $A_{2}$ there are two Argentinian cities. At adjacent vertices $B_{1}$ and $B_{2}$ there are two Brazilian cities. There are $a$ Argentinian cities and $b$ Brazilian cities in the quadrilateral interior, no three of which collinear. Determine if it's possible, independently from the cities position, to build straight roads, each of which connects two Argentinian cities ou two Brazilian cities, such that: $\bullet$ Two roads does not intersect in a point which is not a city; $\bullet$ It's possible to reach any Argentinian city from any Argentinian city using the roads; and $\bullet$ It's possible to reach any Brazilian city from any Brazilian city using the roads. If it's always possible, construct an algorithm that builds a possible set of roads.

In the following triangular lattice distance of two vertices is length of the shortest path between them. Let $ A_{1},A_{2},\dots,A_{n}$ be constant vertices of the lattice. We want to find a vertex in the lattice whose sum of distances from vertices is minimum. We start from an arbitrary vertex. At each step we check all six neighbors and if sum of distances from vertices of one of the neighbors is less than sum of distances from vertices at the moment we go to that neighbor. If we have more than one choice we choose arbitrarily, as seen in the attached picture. Obviusly the algorithm finishes a) Prove that when we can not make any move we have reached to the problem's answer. b) Does this algorithm reach to answer for each connected graph?

$\mathbb{N}_{10}$ is generalization of $\mathbb{N}$ that every hypernumber in $\mathbb{N}_{10}$ is something like: $\overline{...a_2a_1a_0}$ with $a_i \in {0,1..9}$ (Notice that $\overline {...000} \in \mathbb{N}_{10}$) Also we easily have $+,*$ in $\mathbb{N}_{10}$. first $k$ number of $a*b$= first $k$ nubmer of (first $k$ number of a * first $k$ number of b) first $k$ number of $a+b$= first $k$ nubmer of (first $k$ number of a + first $k$ number of b) Fore example $\overline {...999}+ \overline {...0001}= \overline {...000}$ Prove that every monic polynomial in $\mathbb{N}_{10}[x]$ with degree $d$ has at most $d^2$ roots.

At a math contest there are $2n$ students participating. Each of them submits a problem to the jury, which thereafter gives each students one of the $2n$ problems submitted. One says that the contest is [i]fair[/i] is there are $n$ participants which receive their problems from the other $n$ participants. Prove that the number of distributions of the problems in order to obtain a fair contest is a perfect square.

Let $ n$ be a positive integer. Given an integer coefficient polynomial $ f(x)$, define its [i]signature modulo $ n$[/i] to be the (ordered) sequence $ f(1), \ldots , f(n)$ modulo $ n$. Of the $ n^n$ such $ n$-term sequences of integers modulo $ n$, how many are the signature of some polynomial $ f(x)$ if a) $ n$ is a positive integer not divisible by the square of a prime. b) $ n$ is a positive integer not divisible by the cube of a prime.

Let $a,b$ be integers greater than 2. Prove that there exists a positive integer $k$ and a finite sequence $n_1, n_2, \dots, n_k$ of positive integers such that $n_1 = a$, $n_k = b$, and $n_i n_{i+1}$ is divisible by $n_i + n_{i+1}$ for each $i$ ($1 \leq i < k$).

Let $n \geq 3$ be a fixed integer. The number $1$ is written $n$ times on a blackboard. Below the blackboard, there are two buckets that are initially empty. A move consists of erasing two of the numbers $a$ and $b$, replacing them with the numbers $1$ and $a+b$, then adding one stone to the first bucket and $\gcd(a, b)$ stones to the second bucket. After some finite number of moves, there are $s$ stones in the first bucket and $t$ stones in the second bucket, where $s$ and $t$ are positive integers. Find all possible values of the ratio $\frac{t}{s}$.

For any positive integer $b\ge2$, we write the base-$b$ numbers as follows: \[(d_kd_{k-1}\dots d_0)_b=d_kb^k+d_{k-1}b^{k-1}+\dots+d_1b^1+d_0b^0,\]where each digit $d_i$ is a member of the set $S=\{0,1,2,\dots,b-1\}$ and either $d_k\not=0$ or $k=0$. There is a unique way to write any nonnegative integer in the above form. If we select the digits from a different set $S$ instead, we may obtain new representations of all positive integers or, in some cases, all integers. For example, if $b=3$ and the digits are selected from $S=\{-1,0,1\}$, we obtain a way to uniquely represent all integers, known as a $\emph{balanced ternary}$ representation. As further examples, the balanced ternary representation of numbers $5$, $-3$, and $25$ are: \[5=(1\ {-1}\ {-1})_3,\qquad{-3}=({-1}\ 0)_3,\qquad25=(1\ 0\ {-1}\ 1)_3.\]However, not all digit sets can represent all integers. If $b=3$ and $S=\{-2,0,2\}$, then no odd number can be represented. Also, if $b=3$ and $S=\{0,1,2\}$ as in the usual base-$3$ representation, then no negative number can be represented. Given a set $S$ of four integers, one of which is $0$, call $S$ a $\emph{4-basis}$ if every integer $n$ has at least one representation in the form \[n=(d_kd_{k-1}\dots d_0)_4=d_k4^k+d_{k-1}4^{k-1}+\dots+d_14^1+d_04^0,\]where $d_k,d_{k-1},\dots,d_0$ are all elements of $S$ and either $d_k\not=0$ or $k=0$. [list=a] [*]Show that there are infinitely many integers $a$ such that $\{-1,0,1,4a+2\}$ is not a $4$-basis. [*]Show that there are infinitely many integers $a$ such that $\{-1,0,1,4a+2\}$ is a $4$-basis.[/list]