Each rational number is painted either white or red. Call such a coloring of the rationals [i]sanferminera[/i] if for any distinct rationals numbers $x$ and $y$ satisfying one of the following three conditions: [list=1][*]$xy=1$, [*]$x+y=0$, [*]$x+y=1$,[/list]we have $x$ and $y$ painted different colors. How many sanferminera colorings are there?

A magician intends to perform the following trick. She announces a positive integer $n$, along with $2n$ real numbers $x_1 < \dots < x_{2n}$, to the audience. A member of the audience then secretly chooses a polynomial $P(x)$ of degree $n$ with real coefficients, computes the $2n$ values $P(x_1), \dots , P(x_{2n})$, and writes down these $2n$ values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience. Can the magician find a strategy to perform such a trick?

On a table there are 2004 boxes, and in each box a ball lies. I know that some the balls are white and that the number of white balls is even. In each case I may point to two arbitrary boxes and ask whether in the box contains at least a white ball lies. After which minimum number of questions I can indicate two boxes for sure, in which white balls lie?

A set $A$ of integers is called [i]sum-full[/i] if $A \subseteq A + A$, i.e. each element $a \in A$ is the sum of some pair of (not necessarily different) elements $b,c \in A$. A set $A$ of integers is said to be [i]zero-sum-free[/i] if $0$ is the only integer that cannot be expressed as the sum of the elements of a finite nonempty subset of $A$. Does there exist a sum-full zero-sum-free set of integers? [i]Romania (Dan Schwarz)[/i]

Prove there exists a constant $c$ (independent of $n$) such that for any graph $G$ with $n>2$ vertices, we can split $G$ into a forest and at most $cf(n)$ disjoint cycles, where a) $f(n)=n\ln{n}$; b) $f(n)=n$. [i]David Yang.[/i]

Christian Reiher and Reid Barton want to open a security box, they already managed to discover the algorithm to generate the key codes and they obtained the following information: $i)$ In the screen of the box will appear a sequence of $n+1$ numbers, $C_0 = (a_{0,1},a_{0,2},...,a_{0,n+1})$ $ii)$ If the code $K = (k_1,k_2,...,k_n)$ opens the security box then the following must happen: a) A sequence $C_i = (a_{i,1},a_{i,2},...,a_{i,n+1})$ will be asigned to each $k_i$ defined as follows: $a_{i,1} = 1$ and $a_{i,j} = a_{i-1,j}-k_ia_{i,j-1}$, for $i,j \ge 1$ b) The sequence $(C_n)$ asigned to $k_n$ satisfies that $S_n = \sum_{i=1}^{n+1}|a_i|$ has its least possible value, considering all possible sequences $K$. The sequence $C_0$ that appears in the screen is the following: $a_{0,1} = 1$ and $a_0,i$ is the sum of the products of the elements of each of the subsets with $i-1$ elements of the set $A =$ {$1,2,3,...,n$}, $i\ge 2$, such that $a_{0, n+1} = n!$ Find a sequence $K = (k_1,k_2,...,k_n)$ that satisfies the conditions of the problem and show that there exists at least $n!$ of them.

300 students participate on the international math olympiad. Every student speaks in exactly two of the official languages of the olympiad and every language is spoken by 100 people (it is known that students speak only the official languages). Prove that the students can be sited on a circular table, such that no two neighbors spoke the same language.

Archimedes planned to count all of the prime numbers between $2$ and $1000$ using the Sieve of Eratosthenes as follows: (a) List the integers from $2$ to $1000$. (b) Circle the smallest number in the list and call this $p$. (c) Cross out all multiples of $p$ in the list except for $p$ itself. (d) Let $p$ be the smallest number remaining that is neither circled nor crossed out. Circle $p$. (e) Repeat steps $(c)$ and $(d)$ until each number is either circled or crossed out. At the end of this process, the circled numbers are prime and the crossed out numbers are composite. Unfortunately, while crossing out the multiples of $2$, Archimedes accidentally crossed out two odd primes in addition to crossing out all the even numbers (besides $2$). Otherwise, he executed the algorithm correctly. If the number of circled numbers remaining when Archimedes finished equals the number of primes from $2$ to $1000$ (including $2$), then what is the largest possible prime that Archimedes accidentally crossed out?

Let $n \geq 2$ be a positive integer. A total of $2n$ balls are coloured with $n$ colours so that there are two balls of each colour. These balls are put inside $n$ cylindrical boxes with two balls in each box, one on top of the other. Phoe Wa Lone has an empty cylindrical box and his goal is to sort the balls so that balls of the same colour are grouped together in each box. In a [i]move[/i], Phoe Wa Lone can do one of the following: [list] [*]Select a box containing exactly two balls and reverse the order of the top and the bottom balls. [*]Take a ball $b$ at the top of a non-empty box and either put it in an empty box, or put it in the box only containing the ball of the same colour as $b$. [/list] Find the smallest positive integer $N$ such that for any initial placement of the balls, Phoe Wa Lone can always achieve his goal using at most $N$ moves in total.

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

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

There are $2^n$ words of length $n$ over the alphabet $\{0, 1\}$. Prove that the following algorithm generates the sequence $w_0, w_1, \ldots, w_{2^n-1}$ of all these words such that any two consecutive words differ in exactly one digit. (1) $w_0 = 00 \ldots 0$ ($n$ zeros). (2) Suppose $w_{m-1} = a_1a_2 \ldots a_n,\quad a_i \in \{0, 1\}$. Let $e(m)$ be the exponent of $2$ in the representation of $n$ as a product of primes, and let $j = 1 + e(m)$. Replace the digit $a_j$ in the word $w_{m-1}$ by $1 - a_j$. The obtained word is $w_m$.

Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps $L_0, \ldots, L_{n-1},$ each of of which can either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, $Step_0, Step_1, \ldots .$ If $L_{j-1}$ ($j$ is taken mod $n$) is ON then $Step_j$ changes the state of $L_j$ (it goes from ON to OFF or from OFF to ON) but does not change the state of any of the other lamps. If $L_{j-1}$ is OFF then $Step_j$ does not change anything at all. Show that: (i) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again, (ii) If $n$ has the form $2^k$ then all the lamps are ON after $n^2-1$ steps, (iii) If $n$ has the form $2^k + 1$ then all lamps are ON after $n^2 - n + 1$ steps.

Suppose $a_1, \dots, a_n$ are integers whose greatest common divisor is 1. Let $S$ be a set of integers with the following properties: (a) For $i=1, \dots, n$, $a_i \in S$. (b) For $i,j = 1, \dots, n$ (not necessarily distinct), $a_i - a_j \in S$. (c) For any integers $x,y \in S$, if $x+y \in S$, then $x-y \in S$. Prove that $S$ must be equal to the set of all integers.

A finite set $S$ of unit squares is chosen out of a large grid of unit squares. The squares of $S$ are tiled with isosceles right triangles of hypotenuse $2$ so that the triangles do not overlap each other, do not extend past $S$, and all of $S$ is fully covered by the triangles. Additionally, the hypotenuse of each triangle lies along a grid line, and the vertices of the triangles lie at the corners of the squares. Show that the number of triangles must be a multiple of $4$.