Let $k$ be a natural number. For each function $f : \mathbb{N}\to \mathbb{N}$ define the sequence of functions $(f_{m})_{m\geq 1}$ by $f_{1}= f$ and $f_{m+1}= f \circ f_{m}$ for $m \geq 1$ . Function $f$ is called $k$-[i]nice[/i] if for each $n \in\mathbb{N}: f_{k}(n) = f (n)^{k}$. (a) For which $k$ does there exist an injective $k$-nice function $f$ ? (b) For which $k$ does there exist a surjective $k$-nice function $f$ ?

At the vertices of a regular hexagon are written six nonnegative integers whose sum is $2003^{2003}$. Bert is allowed to make moves of the following form: he may pick a vertex and replace the number written there by the absolute value of the difference between the numbers written at the two neighboring vertices. Prove that Bert can make a sequence of moves, after which the number 0 appears at all six vertices.

Prove that for any positive integer $ n$, there exists only $ n$ degree polynomial $ f(x),$ satisfying $ f(0) \equal{} 1$ and $ (x \plus{} 1)[f(x)]^2 \minus{} 1$ is an odd function.

Given 2005 distinct numbers $a_1,\,a_2,\dots,a_{2005}$. By one question, we may take three different indices $1\le i<j<k\le 2005$ and find out the set of numbers $\{a_i,\,a_j,\,a_k\}$ (unordered, of course). Find the minimal number of questions, which are necessary to find out all numbers $a_i$.

Let $f_1(x)=x^2-1$, and for each positive integer $n \geq 2$ define $f_n(x) = f_{n-1}(f_1(x))$. How many distinct real roots does the polynomial $f_{2004}$ have?

Let $\alpha$ be an irrational number with $0<\alpha < 1$, and draw a circle in the plane whose circumference has length $1$. Given any integer $n\ge 3$, define a sequence of points $P_1, P_2, \ldots , P_n$ as follows. First select any point $P_1$ on the circle, and for $2\le k\le n$ define $P_k$ as the point on the circle for which the length of arc $P_{k-1}P_k$ is $\alpha$, when travelling counterclockwise around the circle from $P_{k-1}$ to $P_k$. Suppose that $P_a$ and $P_b$ are the nearest adjacent points on either side of $P_n$. Prove that $a+b\le n$.

Let $t$ and $n$ be fixed integers each at least $2$. Find the largest positive integer $m$ for which there exists a polynomial $P$, of degree $n$ and with rational coefficients, such that the following property holds: exactly one of \[ \frac{P(k)}{t^k} \text{ and } \frac{P(k)}{t^{k+1}} \] is an integer for each $k = 0,1, ..., m$. [i]Proposed by Michael Kural[/i]

Let $P(A)$ be the arithmetic-means of all elements of set $A = \{ a_1, a_2, \ldots, a_n \}$, namely $P(A) = \frac{1}{n} \sum^{n}_{i=1}a_i$. We denote $B$ "balanced subset" of $A$, if $B$ is a non-empty subset of $A$ and $P(B) = P(A)$. Let set $M = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$. Find the number of all "balanced subset" of $M$.

For any integer $k\ge1$, let $p(k)$ be the smallest prime which does not divide $k$. Define the integer function $X(k)$ to be the product of all primes less than $p(k)$ if $p(k)>2$, and $X(k)=1$ if $p(k)=2$. Let $\{x_n\}$ be the sequence defined by $x_0=1$, and $x_{n+1}X(x_n)=x_np(x_n)$ for $n\ge0$. Find the smallest positive integer, $t$ such that $x_t=2090$.

Let $ R$ be a finite commutative ring. Prove that $ R$ has a multiplicative identity element $ (1)$ if and only if the annihilator of $ R$ is $ 0$ (that is, $ aR\equal{}0, \;a\in R $ imply $ a\equal{}0$).

Let $ p$ be a prime number and let $ 0\leq a_{1}< a_{2}<\cdots < a_{m}< p$ and $ 0\leq b_{1}< b_{2}<\cdots < b_{n}< p$ be arbitrary integers. Let $ k$ be the number of distinct residues modulo $ p$ that $ a_{i}\plus{}b_{j}$ give when $ i$ runs from 1 to $ m$, and $ j$ from 1 to $ n$. Prove that a) if $ m\plus{}n > p$ then $ k \equal{} p$; b) if $ m\plus{}n\leq p$ then $ k\geq m\plus{}n\minus{}1$.

There are eight different symbols designed on $n\geq 2$ different T-shirts. Each shirt contains at least one symbol, and no two shirts contain all the same symbols. Suppose that for any $k$ symbols $(1\leq k\leq 7)$ the number of shirts containing at least one of the $k$ symbols is even. Determine the value of $n$.

We call a sequence of integers a [i]Fibonacci-type sequence[/i] if it is infinite in both ways and $a_{n}=a_{n-1}+a_{n-2}$ for any $n\in\mathbb{Z}$. How many [i]Fibonacci-type sequences[/i] can we find, with the property that in these sequences there are two consecutive terms, strictly positive, and less or equal than $N$ ? (two sequences are considered to be the same if they differ only by shifting of indices) [i]Proposed by I. Pevzner[/i]

Determine all composite positive integers $n$ for which it is possible to arrange all divisors of $n$ that are greater than 1 in a circle so that no two adjacent divisors are relatively prime.

All the grids of a $m\times n$ chess board ($m,n\geq 3$), are colored either with red or with blue. Two adjacent grids (having a common side) are called a "good couple" if they have different colors. Suppose there are $S$ "good couples". Explain how to determine whether $S$ is odd or even. Is it prescribed by some specific color grids? Justify your answers.

Let $f$ be a polynomial with real coefficients of degree $n$. Suppose that $\displaystyle \frac{f(x)-f(y)}{x-y}$ is an integer for all $0 \leq x<y \leq n$. Prove that $a-b | f(a)-f(b)$ for all distinct integers $a,b$.

Lisa and Bart are playing a game. A round table has $n$ lights evenly spaced around its circumference. Some of the lights are on and some of them off; the initial configuration is random. Lisa wins if she can get all of the lights turned on; Bart wins if he can prevent this from happening. On each turn, Lisa chooses the positions at which to flip the lights, but before the lights are flipped, Bart, knowing Lisa’s choices, can rotate the table to any position that he chooses (or he can leave the table as is). Then the lights in the positions that Lisa chose are flipped: those that are off are turned on and those that are on are turned off. Here is an example turn for $n = 5$ (a white circle indicates a light that is on, and a black circle indicates a light that is off): [asy] size(250); defaultpen(linewidth(1)); picture p = new picture; real r = 0.2; pair s1=(0,-4), s2=(0,-8); int[][] filled = {{1,2,3},{1,2,5},{2,3,4,5}}; draw(p,circle((0,0),1)); for(int i = 0; i < 5; ++i) { pair P = dir(90-72*i); filldraw(p,circle(P,r),white); label(p,string(i+1),P,2*P,fontsize(10)); } add(p); add(shift(s1)*p); add(shift(s2)*p); for(int j = 0; j < 3; ++j) for(int i = 0; i < filled[j].length; ++i) filldraw(circle(dir(90-72*(filled[j][i]-1))+j*s1,r)); label("$\parbox{15em}{Initial Position.}$", (-4.5,0)); label("$\parbox{15em}{Lisa says ``1,3,4.'' \\ Bart rotates the table one \\ position counterclockwise. }$", (-4.5,0)+s1); label("$\parbox{15em}{Lights in positions 1,3,4 are \\ flipped.}$", (-4.5,0)+s2);[/asy] Lisa can take as many turns as she needs to win, or she can give up if it becomes clear to her that Bart can prevent her from winning. (a) Show that if $n = 7$ and initially at least one light is on and at least one light is off, then Bart can always prevent Lisa from winning. (b) Show that if $n = 8$, then Lisa can always win in at most 8 turns.

The sequence $ (x_n)_{n \geq 1}$ is defined by: $ x_1\equal{}1$ $ x_{n\plus{}1}\equal{}\frac{x_n}{n}\plus{}\frac{n}{x_n}$ Prove that $ (x_n)$ increases and $ [x_n^2]\equal{}n$.

Find all functions $ f: \mathbb Q\longrightarrow\mathbb Q$ such that: $ f(x)+f(\frac1x)=1$ $ 2f(f(x))=f(2x)$

Assume that $k$ and $n$ are two positive integers. Prove that there exist positive integers $m_1 , \dots , m_k$ such that \[1+\frac{2^k-1}{n}=\left(1+\frac1{m_1}\right)\cdots \left(1+\frac1{m_k}\right).\] [i]Proposed by Japan[/i]

Given a sequence $(a_n)$, with $a_1 = 4$ and $a_{n+1} = a_n^2-2 (\forall n \in\mathbb{N})$, prove that there is a triangle with side lengths $a_{n-1}, a_n, a_{n+1},$ and that its area is equal to an integer.

There are $ n$ websites $ 1,2,\ldots,n$ ($ n \geq 2$). If there is a link from website $ i$ to $ j$, we can use this link so we can move website $ i$ to $ j$. For all $ i \in \left\{1,2,\ldots,n - 1 \right\}$, there is a link from website $ i$ to $ i+1$. Prove that we can add less or equal than $ 3(n - 1)\log_{2}(\log_{2} n)$ links so that for all integers $ 1 \leq i < j \leq n$, starting with website $ i$, and using at most three links to website $ j$. (If we use a link, website's number should increase. For example, No.7 to 4 is impossible). Sorry for my bad English.

Let $A$ be the set of all binary sequences of length $n$ and denote $o =(0, 0, \ldots , 0) \in A$. Define the addition on $A$ as $(a_1, \ldots , a_n)+(b_1, \ldots , b_n) =(c_1, \ldots , c_n)$, where $c_i = 0$ when $a_i = b_i$ and $c_i = 1$ otherwise. Suppose that $f\colon A \to A$ is a function such that $f(0) = 0$, and for each $a, b \in A$, the sequences $f(a)$ and $f(b)$ differ in exactly as many places as $a$ and $b$ do. Prove that if $a$ , $b$, $c \in A$ satisfy $a+ b + c = 0$, then $f(a)+ f(b) + f(c) = 0$.

Prove that for all positive integers $n$ there exists a single positive integer divisible with $5^n$ which in decimal base is written using $n$ digits from the set $\{1,2,3,4,5\}$.

Let $a_{1}=1$, $a_{2}=2$, $a_{3}$, $a_{4}$, $\cdots$ be the sequence of positive integers of the form $2^{\alpha}3^{\beta}$, where $\alpha$ and $\beta$ are nonnegative integers. Prove that every positive integer is expressible in the form \[a_{i_{1}}+a_{i_{2}}+\cdots+a_{i_{n}},\] where no summand is a multiple of any other.