Suppose that $f : \mathbb{N} \rightarrow \mathbb{N}$ is a function for which the expression $af(a)+bf(b)+2ab$ for all $a,b \in \mathbb{N}$ is always a perfect square. Prove that $f(a)=a$ for all $a \in \mathbb{N}$.

You are given a set of $n$ blocks, each weighing at least $1$; their total weight is $2n$. Prove that for every real number $r$ with $0 \leq r \leq 2n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r + 2$.

Show that $ x^3 + x+ a^2 = y^2 $ has at least one pair of positive integer solution $ (x,y) $ for each positive integer $ a $.

[b]problem 5.[/b] Let $x_1, x_2,\ldots, x_k$ be vectors of $m$-dimensional Euclidean space, such that $x_1+x_2+\ldots + x_k=0$. Show that there exists a permutation $\pi$ of the integers $\{ 1, 2, \ldots, k \}$ such that: $$\left\lVert \sum_{i=1}^n x_{\pi (i)}\right\rVert \leq \left( \sum_{i=1}^k \lVert x_i \rVert ^2\right)^{1/2}$$for each $n=1, 2, \ldots, k$. Note that $\lVert \cdot \rVert$ denotes the Euclidean norm. (18 points).

Prove that $\sum \frac{1}{i_1i_2 \ldots i_k} = n$ is taken over all non-empty subsets $\left\{i_1,i_2, \ldots, i_k\right\}$ of $\left\{1,2,\ldots,n\right\}$. (The $k$ is not fixed, so we are summing over all the $2^n-1$ possible nonempty subsets.)

Prove that for all integers $n \geq 3$, there exist odd positive integers $x$, $y$ such that $7x^2 + y^2 = 2^n$.

Let $S$ be a finite set. $f$ is a function defined on the subset-group $2^S$ of set $S$. $f$ is called $\textsl{monotonic decreasing}$ if when $X \subseteq Y\subseteq S$, then $f(X) \geq f(Y)$ holds. Prove that: $f(X \cup Y)+f(X \cap Y ) \leq f(X)+ f(Y)$ for $X, Y \subseteq S$ if and only if $g(X)=f(X \cup \{ a \}) - f(X)$ is a $\textsl{monotonic decreasing}$ funnction on the subset-group $2^{S \setminus \{a\}}$ of set $S \setminus \{a\}$ for any $a \in S$.

Do there exist integers $m, n$ and a function $f\colon \mathbb R \to \mathbb R$ satisfying simultaneously the following two conditions? $\bullet$ i) $f(f(x))=2f(x)-x-2$ for any $x \in \mathbb R$; $\bullet$ ii) $m \leq n$ and $f(m)=n$.

Find all polynomials $W$ with real coefficients possessing the following property: if $x+y$ is a rational number, then $W(x)+W(y)$ is rational.

Let $ n$ be a positive integer. Show that \[ \left(\sqrt{2} \plus{} 1 \right)^n \equal{} \sqrt{m} \plus{} \sqrt{m\minus{}1}\] for some positive integer $ m.$

Find all groups of positive integers $ (a,x,y,n,m)$ that satisfy $ a(x^n \minus{} x^m) \equal{} (ax^m \minus{} 4) y^2$ and $ m \equiv n \pmod{2}$ and $ ax$ is odd.

There is a broken computer such that only three primitive data $c$, $1$ and $-1$ are reserved. Only allowed operation may take $u$ and $v$ and output $u \cdot v + v.$ At the beginning, $u,v \in \{c, 1, -1\}.$ After then, it can also take the value of the previous step (only one step back) besides $\{c, 1, -1\}$. Prove that for any polynomial $P_{n}(x) = a_0 \cdot x^n + a_1 \cdot x^{n-1} + \ldots + a_n$ with integer coefficients, the value of $P_n(c)$ can be computed using this computer after only finite operation.

Prove that $N^2$ arbitrary distinct positive integers ($N>10$) can be arranged in a $N\times N$ table, so that all $2N$ sums in rows and columns are distinct. [i]Proposed by S. Volchenkov[/i]

The total mass of $100$ given weights with positive masses equals $2S$. A natural number $k$ is called [i]middle[/i] if some $k$ of the given weights have the total mass $S$. Find the maximum possible number of middle numbers.

Let $ G=(V,E)$ be a simple graph. a) Let $ A,B$ be a subsets of $ E$, and spanning subgraphs of $ G$ with edges $ A,B,A\cup B$ and $ A\cap B$ have $ a,b,c$ and $ d$ connected components respectively. Prove that $ a+b\leq c+d$. We say that subsets $ A_1,A_2,\dots,A_m$ of $ E$ have $ (R)$ property if and only if for each $ I\subset\{1,2,\dots,m\}$ the spanning subgraph of $ G$ with edges $ \cup_{i\in I}A_i$ has at most $ n-|I|$ connected components. b) Prove that when $ A_1,\dots,A_m,B$ have $ (R)$ property, and $ |B|\geq2$, there exists an $ x\in B$ such that $ A_1,A_2,\dots,A_m,B\backslash\{x\}$ also have property $ (R)$. Suppose that edges of $ G$ are colored arbitrarily. A spanning subtree in $ G$ is called colorful if and only if it does not have any two edges with the same color. c) Prove that $ G$ has a colorful subtree if and only if for each partition of $ V$ to $ k$ non-empty subsets such as $ V_1,\dots,V_k$, there are at least $ k\minus{}1$ edges with distinct colors that each of these edges has its two ends in two different $ V_i$s. d) Assume that edges of $ K_n$ has been colored such that each color is repeated $ \left[\frac n2\right]$ times. Prove that there exists a colorful subtree. e) Prove that in part d) if $ n\geq5$ there is a colorful subtree that is non-isomorphic to $ K_{1,n-1}$. f) Prove that in part e) there are at least two non-intersecting colorful subtrees.

Prove that for any $ n\in \mathbb N$ the number $ 1\plus{}\dfrac{1}{3}\plus{}\dfrac{1}{5}\plus{}\ldots\plus{}\dfrac{1}{2n\plus{}1}$ is not an integer.

The plane is divided into regions by $ n \ge 3$ lines, no two of which are parallel, and no three of which are concurrent. Some regions are coloured , in such a way that no two coloured regions share a common segment or half-line of their borders. Prove that the number of coloured regions is at most $ \frac{n(n\plus{}1)}{3}$

Let $\{a_n\}$ be a sequence such that: $a_1 = \frac{1}{2}$, $a_{k+1}=-a_k+\frac{1}{2-a_k}$ for all $k = 1, 2,\ldots$. Prove that \[ \left(\frac{n}{2(a_1+a_2+\cdots+a_n)}-1\right)^n \leq \left(\frac{a_1+a_2+\cdots+a_n}{n}\right)^n\left(\frac{1}{a_1}-1\right)\left(\frac{1}{a_2}-1\right)\cdots \left(\frac{1}{a_n}-1\right). \]

Let $S$ be a set containing $n^{2}+n-1$ elements, for some positive integer $n$. Suppose that the $n$-element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class.

Let $\{b_n\}_{n\geq 1}^{\infty}$ be a sequence of positive integers. The sequence $\{a_n\}_{n\geq 1}^{\infty}$ is defined as follows: $a_1$ is a fixed positive integer and \[a_{n+1}=a_n^{b_n}+1 ,\qquad \forall n\geq 1.\] Find all positive integers $m\geq 3$ with the following property: If the sequence $\{a_n\mod m\}_{n\geq 1 }^{\infty}$ is eventually periodic, then there exist positive integers $q,u,v$ with $2\leq q\leq m-1$, such that the sequence $\{b_{v+ut}\mod q\}_{t\geq 1}^{\infty}$ is purely periodic.

A square board is dissected into $n^2$ rectangular cells by $n-1$ horizontal and $n-1$ vertical lines. The cells are painted alternately black and white in a chessboard pattern. One diagonal consists of $n$ black cells which are squares. Prove that the total area of all black cells is not less than the total area of all white cells.

A [i]base[/i] 10 [i]over-expansion[/i] of a positive integer $N$ is an expression of the form $N=d_k10^k+d_{k-1}10^{k-1}+\cdots+d_0 10^0$ with $d_k\ne 0$ and $d_i\in\{0,1,2,\dots,10\}$ for all $i.$ For instance, the integer $N=10$ has two base 10 over-expansions: $10=10\cdot 10^0$ and the usual base 10 expansion $10=1\cdot 10^1+0\cdot 10^0.$ Which positive integers have a unique base 10 over-expansion?

Let $M$ be a positive integer. At a party with 120 people, 30 wear red hats, 40 wear blue hats, and 50 wear green hats. Before the party begins, $M$ pairs of people are friends. (Friendship is mutual.) Suppose also that no two friends wear the same colored hat to the party. During the party, $X$ and $Y$ can become friends if and only if the following two conditions hold: [list] [*] There exists a person $Z$ such that $X$ and $Y$ are both friends with $Z$. (The friendship(s) between $Z,X$ and $Z,Y$ could have been formed during the party.) [*] $X$ and $Y$ are not wearing the same colored hat. [/list] Suppose the party lasts long enough so that all possible friendships are formed. Let $M_1$ be the largest value of $M$ such that regardless of which $M$ pairs of people are friends before the party, there will always be at least one pair of people $X$ and $Y$ with different colored hats who are not friends after the party. Let $M_2$ be the smallest value of $M$ such that regardless of which $M$ pairs of people are friends before the party, every pair of people $X$ and $Y$ with different colored hats are friends after the party. Find $M_1+M_2$. [hide="Clarifications"] [list] [*] The definition of $M_2$ should read, ``Let $M_2$ be the [i]smallest[/i] value of $M$ such that...''. An earlier version of the test read ``largest value of $M$''.[/list][/hide] [i]Victor Wang[/i]

Find all the functions $ f :\mathbb{R}\mapsto\mathbb{R} $ with the following property: $ \forall x$ $f(x)= f(x/2) + (x/2)f'(x)$

Let two bijective and continuous functions$f,g: \mathbb{R}\to\mathbb{R}$ such that : $\left(f\circ g^{-1}\right)(x)+\left(g\circ f^{-1}\right)(x)=2x$ for any real $x$. Show that If we have a value $x_{0}\in\mathbb{R}$ such that $f(x_{0})=g(x_{0})$, then $f=g$.