For a positive integer $n$, we consider an $n \times n$ board and tiles with dimensions $1 \times 1, 1 \times 2, ..., 1 \times n$. In how many ways exactly can $\frac12 n (n + 1)$ cells of the board are colored red, so that the red squares can all be covered by placing the $n$ tiles all horizontally, but also by placing all $n$ tiles vertically? Two colorings that are not identical, but by rotation or reflection from the board into each other count as different.

Find all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ (where $\mathbb{Z}$ is the set of all integers) such that \[ 2000f(f(x)) - 3999f(x) + 1999x = 0\textrm{ for all }x \in \mathbb{Z}. \]

Suppose that $PQ$ and $RS$ are two chords of a circle intersecting at a point $O$. It is given that $PO=3 \text{cm}$ and $SO=4 \text{cm}$. Moreover, the area of the triangle $POR$ is $7 \text{cm}^2$. Find the area of the triangle $QOS$.

In a convex hexagon $ABCDEF, AB$ is parallel to $DE, BC$ is parallel to $EF$ and $CD$ is parallel to $FA$. Prove that the triangles $ACE$ and $BDF$ have the same area.

In quadrilateral $ABCD$ the sides $AB$ and $CD$ are parallel. Let $M$ be the midpoint of diagonal $AC$. Suppose that triangles $ABM$ and $ACD$ have equal area. Prove that $DM // BC$.

$\overline{AB}$ is a diameter of a circle. Tangents $\overline{AD}$ and $\overline{BC}$ are drawn so that $\overline{AC}$ and $\overline{BD}$ intersect in a point on the circle. If $\overline{AD}=a$ and $\overline{BD}=b$, $a \not= b$, the diameter of the circle is: $\textbf{(A)}\ |a-b|\qquad \textbf{(B)}\ \frac{1}{2}(a+b)\qquad \textbf{(C)}\ \sqrt{ab} \qquad \textbf{(D)}\ \frac{ab}{a+b}\qquad \textbf{(E)}\ \frac{1}{2}\frac{ab}{a+b}$

There is a bag with balls whose colors are $c_1, c_2, \dots, c_n$. Let $a_i$ be the number of balls inside the bag with color $c_i$. We are drawing $n$ balls from the bag one by one with replacement. If $p(a_1,a_2,\dots, a_n)$ denotes the probability that at least two of them have same color, which one below is smaller? $\textbf{(A)}\ p(2,2,2,1) \qquad\textbf{(B)}\ p(1,1,1,1) \qquad\textbf{(C)}\ p(2,2,3) \qquad\textbf{(D)}\ p(2,2,1) \qquad\textbf{(E)}\ p(1,1,1)$

Find all functions $f : R \to R$ such that for all real $x,y$, $f(f(x)+y) = f(x^2 -y)+4y f(x)$

Starting at $(1,1)$, a stone is moved in the coordinate plane according to the following rules: (i) From any point $(a,b)$, the stone can move to $(2a,b)$ or $(a,2b)$. (ii) From any point $(a,b)$, the stone can move to $(a-b,b)$ if $a > b$, or to $(a,b-a)$ if $a < b$. For which positive integers $x,y$ can the stone be moved to $(x,y)$?

Let $A$ and $B$ be two fixed points in the plane. Consider all possible convex quadrilaterals $ABCD$ with $AB = BC, AD = DC$, and $\angle ADC = 90^\circ$. Prove that there is a fixed point $P$ such that, for every such quadrilateral $ABCD$ on the same side of $AB$, the line $DC$ passes through $P.$

Alice and the Cheshire Cat play a game. At each step, Alice either (1) gives the cat a penny, which causes the cat to change the number of (magic) beans that Alice has from $ n$ to $ 5n$ or (2) gives the cat a nickel, which causes the cat to give Alice another bean. Alice wins (and the cat disappears) as soon as the number of beans Alice has is greater than $ 2008$ and has last two digits $ 42$. What is the minimum number of cents Alice can spend to win the game, assuming she starts with 0 beans?

Find all integer solutions of the equation \[\frac {x^{7} \minus{} 1}{x \minus{} 1} \equal{} y^{5} \minus{} 1.\]

Prove that among any 18 consecutive positive 3-digit numbers, there is at least one that is divisible by the sum of its digits!

(A.Zaslavsky, 8--9) Given a circle and a point $ O$ on it. Another circle with center $ O$ meets the first one at points $ P$ and $ Q$. The point $ C$ lies on the first circle, and the lines $ CP$, $ CQ$ meet the second circle for the second time at points $ A$ and $ B$. Prove that $ AB\equal{}PQ$.

Suppose $a_1, a_2, a_3, \dots,$ is a sequence of real numbers such that $$a_n = \frac{a_{n-1}a_{n-2}}{3a_{n-2}-2a_{n-1}}$$ for all $n \ge 3$. If $a_1 = 1$ and $a_{10} = 10$, what is $a_{19}$? [i]Proposed by Howard Halim[/i]

In a plane, there is an infinite triangular grid consists of equilateral triangles whose lengths of the sides are equal to $ 1$, call the vertices of the triangles the lattice points, call two lattice points are adjacent if the distance between the two points is equal to $ 1;$ A jump game is played by two frogs $ A,B,$ "A jump" is called if the frogs jump from the point which it is lying on to its adjacent point, " A round jump of $ A,B$" is called if first $ A$ jumps and then $ B$ by the following rules: Rule (1): $ A$ jumps once arbitrarily, then $ B$ jumps once in the same direction, or twice in the opposite direction; Rule (2): when $ A,B$ sits on adjacent lattice points, they carry out Rule (1) finishing a round jump, or $ A$ jumps twice continually, keep adjacent with $ B$ every time, and $ B$ rests on previous position; If the original positions of $ A,B$ are adjacent lattice points, determine whether for $ A$ and $ B$,such that the one can exactly land on the original position of the other after a finite round jumps.

Suppose $a,b,c$ are the side lengths of a triangle $ABC$. Show that $$x=\sqrt{a(b+c-a)}, y=\sqrt{b(c+a-b)}, z=\sqrt{c(a+b-c)}$$ are the side lengths of an acute-angled triangle $XYZ$, with the same area as $ABC$, but with a smaller perimeter, unless $ABC$ is equilateral.

What is the largest possible rational root of the equation $ax^2 + bx + c = 0{}$ where $a, b$ and $c{}$ are positive integers that do not exceed $100{}$?

Let $A$ be a vertex of a regular star-shaped pentagon, the angle at $A$ being less than $180^o$ and the broken line $AA_1BB_1CC_1DD_1EE_1$ being its contour. Lines $AB$ and $DE$ meet at $F$. Prove that polygon $ABB_1CC_1DED_1$ has the same area as the quadrilateral $AD_1EF$. Note: A regular star pentagon is a figure formed along the diagonals of a regular pentagon.

A large metal cylindrical cup floats in a rectangular tub half-filled with water. The tap is placed over the cup and turned on, releasing water at a constant rate. Eventually the cup sinks to the bottom and is completely submerged. Which of the following five graphs could represent the water level in the sink as a function of time? [asy] size(450); picture pic; draw(pic,(0,0)--(10,0)--(10,7)--(0,7)--cycle); for (int i=1;i<10;++i) { draw(pic,(i,0)--(i,7),dashed+linewidth(0.4)); } for (int j=1;j<7;++j) { draw(pic,(0,j)--(10,j),dashed+linewidth(0.4)); } label(pic,scale(1.2)*"time",(5.5,-0.5),S); label(pic,rotate(90)*scale(1.2)*"water level",(-0.5,2.5),W); add(pic); path A=(0,1)--(10,6); draw(A,linewidth(2)); label("(A)",(4.5,-1.5),1.5*S); picture pic2=shift(13*right)*pic; add(pic2); path B=(0,1)--(4,4)--(10,6); draw(shift(13*right)*B,linewidth(2)); label("(B)",(17.5,-1.5),1.5*S); picture pic3=shift(26*right)*pic; add(pic3); path C=(0,1)--(4,3)--(4,2)--(10,5); draw(shift(26*right)*C,linewidth(2)); label("(C)",(30.5,-1.5),1.5*S); picture pic4=shift(13*down)*pic; add(pic4); path D=(0,1)--(4,3)--(4,4)--(10,7); draw(shift(13*down)*D,linewidth(2)); label("(D)",(4.5,-14.5),1.5*S); picture pic5=shift(13*down)*shift(13*right)*pic; add(pic5); path E=(0,1)--(4,3)--(4,2)--(10,4); draw(shift(13*down)*shift(13*right)*E,linewidth(2)); label("(E)",(17.5,-14.5),1.5*S); [/asy]

We have a pile of $2016$ cards and a hat. We take out one card, put it in the hat and then divide the remaining cards into two arbitrary non empty piles. In the next step, we choose one of the two piles, we move one card from this pile to the hat and then divide this pile into two arbitrary non empty piles. This procedure is repeated several times : in the $k$-th step $(k>1)$ we move one card from one of the piles existing after the step $(k-1)$ to the hat and then divide this pile into two non empty piles. Is it possible that after some number of steps we get all piles containing three cards each?

Let $p$ be a permutation of the set $S_n = \{1, 2, \dots, n\}$. An element $j \in S_n$ is called a fixed point of $p$ if $p(j) = j$. Let $f_n$ be the number of permutations having no fixed points, and $g_n$ be the number with exactly one fixed point. Show that $|f_n - g_n| = 1$.

In a triangle $ABC$, $T$ is the centroid and $ \angle TAB = \angle ACT$. Find the maximum possible value of $sin \angle CAT +sin \angle CBT$.

Let $ABCD$ be a cyclic quadrilateral inscirbed in circle $O$. Let the tangent to $O$ at $A$ meet $BC$ at $S$, and the tangent to $O$ at $B$ meet $CD$ at $T$. Circle with $S$ as its center and passing $A$ meets $BC$ at $E$, and $AE$ meets $O$ again at $F(\ne A)$. The circle with $T$ as its center and passing $B$ meets $CD$ at $K$. Let $P = BK \cap AC$. Prove that $P,F,D$ are collinear if and only if $AB = AP$.

Let $m$ and $n$ be positive integers such that $5m+ n$ is a divisor of $5n +m$. Prove that $m$ is a divisor of $n$.