A crazy physicist discovered a new kind of particle wich he called an imon, after some of them mysteriously appeared in his lab. Some pairs of imons in the lab can be entangled, and each imon can participate in many entanglement relations. The physicist has found a way to perform the following two kinds of operations with these particles, one operation at a time. (i) If some imon is entangled with an odd number of other imons in the lab, then the physicist can destroy it. (ii) At any moment, he may double the whole family of imons in the lab by creating a copy $I'$ of each imon $I$. During this procedure, the two copies $I'$ and $J'$ become entangled if and only if the original imons $I$ and $J$ are entangled, and each copy $I'$ becomes entangled with its original imon $I$; no other entanglements occur or disappear at this moment. Prove that the physicist may apply a sequence of such operations resulting in a family of imons, no two of which are entangled.

For two positive integers a and b, which are relatively prime, find all integer that can be the great common divisor of $a+b$ and $\frac{a^{2005}+b^{2005}}{a+b}$.

Find the number of rational numbers $r$, $0<r<1$, such that when $r$ is written as a fraction in lowest terms, the numerator and denominator have a sum of $1000$.

The numbers $1, 2, \ldots, 2012$ are written on a blackboard. Each minute, a student goes up to the board, chooses two numbers $x$ and $y$, erases them, and writes the number $2x+2y$ on the board. This continues until only one number $N$ remains. Find the remainder when the maximum possible value of $N$ is divided by 1000. [i]Victor Wang.[/i]

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

There are $ 63$ points arbitrarily on the circle $ \mathcal{C}$ with its diameter being $ 20$. Let $ S$ denote the number of triangles whose vertices are three of the $ 63$ points and the length of its sides is no less than $ 9$. Fine the maximum of $ S$.

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$.

Each cell of an $m\times n$ board is filled with some nonnegative integer. Two numbers in the filling are said to be [i]adjacent[/i] if their cells share a common side. (Note that two numbers in cells that share only a corner are not adjacent). The filling is called a [i]garden[/i] if it satisfies the following two conditions: (i) The difference between any two adjacent numbers is either $0$ or $1$. (ii) If a number is less than or equal to all of its adjacent numbers, then it is equal to $0$. Determine the number of distinct gardens in terms of $m$ and $n$.

Prove that there exist two infinite sequences $ \{a_n\}_{n\ge 1}$ and $ \{b_n\}_{n\ge 1}$ of positive integers such that the following conditions hold simultaneously: $ (i)$ $ 0 < a_1 < a_2 < a_3 < \cdots$; $ (ii)$ $ a_n < b_n < a_n^2$, for all $ n\ge 1$; $ (iii)$ $ a_n \minus{} 1$ divides $ b_n \minus{} 1$, for all $ n\ge 1$ $ (iv)$ $ a_n^2 \minus{} 1$ divides $ b_n^2 \minus{} 1$, for all $ n\ge 1$ [19 points out of 100 for the 6 problems]

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

A function $f_n(x)\ (n=1,\ 2,\ \cdots)$ is defined by $f_1(x)=x$ and \[f_n(x)=x+\frac{e}{2}\int_0^1 f_{n-1}(t)e^{x-t}dt\ (n=2,\ 3,\ \cdots)\]. Find $f_n(x)$.

What is that largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$?

Let $z$ be a complex non-zero number such that $Re(z),Im(z)\in \mathbb{Z}$. Prove that $z$ is uniquely representable as $a_0+a_1(1+i)+a_2(1+i)^2+\dots+a_n(1+i)^n$ where $n\geq 0$ and $a_j \in \{0,1\}$ and $a_n=1$. Time allowed for this problem was 1 hour.

We define a [i]chessboard polygon[/i] to be a polygon whose sides are situated along lines of the form $ x \equal{} a$ or $ y \equal{} b$, where $ a$ and $ b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $ 1 \times 2$ rectangles. Finally, a [i]tasteful tiling[/i] is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $ 3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner. [asy]size(300); pathpen = linewidth(2.5); void chessboard(int a, int b, pair P){ for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle); } chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12)); /* draw lines */ D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3));[/asy] a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully. b) Prove that such a tasteful tiling is unique.

There are 100 apples on the table with total weight of 10 kg. Each apple weighs no less than 25 grams. The apples need to be cut for 100 children so that each of the children gets 100 grams. Prove that you can do it in such a way that each piece weighs no less than 25 grams.

Let $n$ be an positive integer. Find the smallest integer $k$ with the following property; Given any real numbers $a_1 , \cdots , a_d $ such that $a_1 + a_2 + \cdots + a_d = n$ and $0 \le a_i \le 1$ for $i=1,2,\cdots ,d$, it is possible to partition these numbers into $k$ groups (some of which may be empty) such that the sum of the numbers in each group is at most $1$.

Let $D_{1}, D_{2}, . . . , D_{n}$ be rectangular parallelepipeds in space, with edges parallel to the $x, y, z$ axes. For each $D_{i}$, let $x_{i} , y_{i} , z_{i}$ be the lengths of its projections onto the $x, y, z$ axes, respectively. Suppose that for all pairs $D_{i}$ , $D_{j}$, if at least one of $x_{i} < x_{j}$ , $y_{i} < y_{j}$, $z_{i} < z_{j}$ holds, then $x_{i} \leq x_{j}$ , $y_{i} \leq y_{j}$, and $z_{i} < z_{j}$ . If the volume of the region $\bigcup^{n}_{i=1}{D_{i}}$ equals 1997, prove that there is a subset $\{D_{i_{1}}, D_{i_{2}}, . . . , D_{i_{m}}\}$ of the set $\{D_{1}, . . . , D_{n}\}$ such that $(i)$ if $k \not= l $ then $D_{i_{k}} \cap D_{i_{l}} = \emptyset $, and $(ii)$ the volume of $\bigcup^{m}_{k=1}{D_{i_{k}}}$ is at least 73.

What is the greatest common factor of $12345678987654321$ and $12345654321$? [i]Proposed by Evan Chen[/i]

Define a search algorithm called $\texttt{powSearch}$. Throughout, assume $A$ is a 1-indexed sorted array of distinct integers. To search for an integer $b$ in this array, we search the indices $2^0,2^1,\ldots$ until we either reach the end of the array or $A[2^k] > b$. If at any point we get $A[2^k] = b$ we stop and return $2^k$. Once we have $A[2^k] > b > A[2^{k-1}]$, we throw away the first $2^{k-1}$ elements of $A$, and recursively search in the same fashion. For example, for an integer which is at position $3$ we will search the locations $1, 2, 4, 3$. Define $g(x)$ to be a function which returns how many (not necessarily distinct) indices we look at when calling $\texttt{powSearch}$ with an integer $b$ at position $x$ in $A$. For example, $g(3) = 4$. If $A$ has length $64$, find \[g(1) + g(2) + \ldots + g(64).\]

We are given a bag of sugar, a two-pan balance, and a weight of $1$ gram. How do we obtain $1$ kilogram of sugar in the smallest possible number of weighings?

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.

Given a table $m\times n$, in each cell of which a number $+1$ or $-1$ is written. It is known that initially exactly one $-1$ is in the table, all the other numbers being $+1$. During a move, it is allowed to chose any cell containing $-1$, replace this $-1$ by $0$, and simultaneously multiply all the numbers in the neighbouring cells by $-1$ (we say that two cells are neighbouring if they have a common side). Find all $(m,n)$ for which using such moves one can obtain the table containing zeros only, regardless of the cell in which the initial $-1$ stands.

In a blackboard, it's written the following expression $ 1-2-2^2-2^3-2^4-2^5-2^6-2^7-2^8-2^9-2^{10}$ We put parenthesis by different ways and then we calculate the result. For example: $ 1-2-\left(2^2-2^3\right)-2^4-\left(2^5-2^6-2^7\right)-2^8-\left( 2^9-2^{10}\right)= 403$ and $ 1-\left(2-2^2 \left(-2^3-2^4 \right)-\left(2^5-2^6-2^7\right)\right)- \left(2^8- 2^9 \right)-2^{10}= -933$ How many different results can we obtain?

Let $P$ be a regular $2n$-sided polygon. A [b]rhombus-ulation[/b] of $P$ is dividing $P$ into rhombuses such that no two intersect and no vertex of any rhombus is on the edge of other rhombuses or $P$. (a) Prove that number of rhombuses is a function of $n$. Find the value of this function. Also find the number of vertices and edges of the rhombuses as a function of $n$. (b) Prove or disprove that there always exists an edge $e$ of $P$ such that by erasing all the segments parallel to $e$ the remaining rhombuses are connected. (c) Is it true that each two rhombus-ulations can turn into each other using the following algorithm multiple times? Algorithm: Take a hexagon -not necessarily regular- consisting of 3 rhombuses and re-rhombus-ulate the hexagon. (d) Let $f(n)$ be the number of ways to rhombus-ulate $P$. Prove that:\[\Pi_{k=1}^{n-1} ( \binom{k}{2} +1) \leq f(n) \leq \Pi_{k=1}^{n-1} k^{n-k} \]

Evaluate \[ \int_{\minus{}1}^1 \frac{1\plus{}2x^2\plus{}3x^4\plus{}4x^6\plus{}5x^8\plus{}6x^{10}\plus{}7x^{12}}{\sqrt{(1\plus{}x^2)(1\plus{}x^4)(1\plus{}x^6)}}dx.\]