Let $p$ and $q$ be relatively prime positive integers. A subset $S\subseteq \mathbb{N}_0$ is called ideal if $0 \in S$ and, for each element $n \in S$, the integers $n+p$ and $n+q$ belong to $S$. Determine the number of ideal subsets of $\mathbb{N}_0$.

A polynomial $p(x)$ has remainder three when divided by $x-1$ and remainder five when divided by $x-3$. The remainder when $p(x)$ is divided by $(x-1)(x-3)$ is $\textbf{(A) }x-2\qquad\textbf{(B) }x+2\qquad\textbf{(C) }2\qquad\textbf{(D) }8\qquad \textbf{(E) }15$

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} \]

Let $S$ be a planar region. A $\emph{domino-tiling}$ of $S$ is a partition of $S$ into $1\times2$ rectangles. (For example, a $2\times3$ rectangle has exactly $3$ domino-tilings, as shown below.) [asy] import graph; size(7cm); pen dps = linewidth(0.7); defaultpen(dps); draw((0,0)--(3,0)--(3,2)--(0,2)--cycle, linewidth(2)); draw((4,0)--(4,2)--(7,2)--(7,0)--cycle, linewidth(2)); draw((8,0)--(8,2)--(11,2)--(11,0)--cycle, linewidth(2)); draw((1,0)--(1,2)); draw((2,1)--(3,1)); draw((0,1)--(2,1), linewidth(2)); draw((2,0)--(2,2), linewidth(2)); draw((4,1)--(7,1)); draw((5,0)--(5,2), linewidth(2)); draw((6,0)--(6,2), linewidth(2)); draw((8,1)--(9,1)); draw((10,0)--(10,2)); draw((9,0)--(9,2), linewidth(2)); draw((9,1)--(11,1), linewidth(2)); [/asy] The rectangles in the partition of $S$ are called $\emph{dominoes}$. (a) For any given positive integer $n$, find a region $S_n$ with area at most $2n$ that has exactly $n$ domino-tilings. (b) Find a region $T$ with area less than $50000$ that has exactly $100002013$ domino-tilings.

The area and the perimeter of the triangle with sides $10,8,6$ are equal. Find all the triangles with integral sides whose area and perimeter are equal.

A grandpa has a finite number of boxes in his attic. Each box is a straight rectangular prism with integer edge lengths. For every box its width is greater or equal to its height and its length is greater or equal to its width. A box can be put inside another box if and only if all of its dimensions are respectively smaller than the other one's. You can put two or more boxes in a bigger box only if the smaller boxes are all already inside one of the boxes. The grandpa decided to put the boxes in each other so that there would be a minimal number of visible boxes in the attic (boxes that have not been put inside another). He decided to use the following algorithm: at each step he finds the longest sequence of boxes so that the first can be put in the second, the second can be put in the third, etc., and then he puts them inside each other in the aforementioned order. The grandpa used the algorithm until no box could be put inside another. It is known that at each step the longest sequence of boxes was unique, e.g., at no moment were there two different sequences with the same length. The grandpa now claims that he has the minimal possible number of visible boxes in his attic. Is the claim necessarily true?

The vertices of a connected graph cannot be coloured with less than $n+1$ colours (so that adjacent vertices have different colours). Prove that $\dfrac{n(n-1)}{2}$ edges can be removed from the graph so that it remains connected. [i]V. Dolnikov[/i] [b]EDIT.[/b] It is confirmed by the official solution that the graph is tacitly assumed to be [b]finite[/b].

What is the rightmost nonzero digit of $1000000!$?

Let $ A_0 \equal{} (a_1,\dots,a_n)$ be a finite sequence of real numbers. For each $ k\geq 0$, from the sequence $ A_k \equal{} (x_1,\dots,x_k)$ we construct a new sequence $ A_{k \plus{} 1}$ in the following way. 1. We choose a partition $ \{1,\dots,n\} \equal{} I\cup J$, where $ I$ and $ J$ are two disjoint sets, such that the expression \[ \left|\sum_{i\in I}x_i \minus{} \sum_{j\in J}x_j\right| \] attains the smallest value. (We allow $ I$ or $ J$ to be empty; in this case the corresponding sum is 0.) If there are several such partitions, one is chosen arbitrarily. 2. We set $ A_{k \plus{} 1} \equal{} (y_1,\dots,y_n)$ where $ y_i \equal{} x_i \plus{} 1$ if $ i\in I$, and $ y_i \equal{} x_i \minus{} 1$ if $ i\in J$. Prove that for some $ k$, the sequence $ A_k$ contains an element $ x$ such that $ |x|\geq\frac n2$. [i]Author: Omid Hatami, Iran[/i]

On a blackboard there are $ n \geq 2, n \in \mathbb{Z}^{\plus{}}$ numbers. In each step we select two numbers from the blackboard and replace both of them by their sum. Determine all numbers $ n$ for which it is possible to yield $ n$ identical number after a finite number of steps.

Let $S$ be a set of $n$ points in the coordinate plane. Say that a pair of points is [i]aligned[/i] if the two points have the same $x$-coordinate or $y$-coordinate. Prove that $S$ can be partitioned into disjoint subsets such that (a) each of these subsets is a collinear set of points, and (b) at most $n^{3/2}$ unordered pairs of distinct points in $S$ are aligned but not in the same subset.

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.

a.) There are $2n+1$ ($n>2$) batteries. We don't know which batteries are good and which are bad but we know that the number of good batteries is greater by $1$ than the number of bad batteries. A lamp uses two batteries, and it works only if both of them are good. What is the least number of attempts sufficient to make the lamp work? b.) The same problem but the total number of batteries is $2n$ ($n>2$) and the numbers of good and bad batteries are equal. [i]Proposed by Alexander Shapovalov[/i]

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.

A set of three nonnegative integers $\{x, y, z \}$ with $x<y<z$ is called historic if $\{z-y, y-x\}=\{1776,2001\}$. Show that the set of all nonnegative integers can be written as the union of pairwise disjoint historic sets.

Given a function $f$ for which \[f(x)=f(398-x)=f(2158-x)=f(3214-x) \]holds for all real $x,$ what is the largest number of different values that can appear in the list $f(0),f(1),f(2),\ldots,f(999)?$

Two teams, $ A$ and $ B$, fight for a territory limited by a circumference. $ A$ has $ n$ blue flags and $ B$ has $ n$ white flags ($ n\geq 2$, fixed). They play alternatively and $ A$ begins the game. Each team, in its turn, places one of his flags in a point of the circumference that has not been used in a previous play. Each flag, once placed, cannot be moved. Once all $ 2n$ flags have been placed, territory is divided between the two teams. A point of the territory belongs to $ A$ if the closest flag to it is blue, and it belongs to $ B$ if the closest flag to it is white. If the closest blue flag to a point is at the same distance than the closest white flag to that point, the point is neutral (not from $ A$ nor from $ B$). A team wins the game is their points cover a greater area that that covered by the points of the other team. There is a draw if both cover equal areas. Prove that, for every $ n$, team $ B$ has a winning strategy.

The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge). [i]Proposed by Norman Do, Australia[/i]

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

A finite number of coins are placed on an infinite row of squares. A sequence of moves is performed as follows: at each stage a square containing more than one coin is chosen. Two coins are taken from this square; one of them is placed on the square immediately to the left while the other is placed on the square immediately to the right of the chosen square. The sequence terminates if at some point there is at most one coin on each square. Given some initial configuration, show that any legal sequence of moves will terminate after the same number of steps and with the same final configuration.

Prove that in a plane, arbitrary $ n$ points can be overlapped by discs that the sum of all the diameters is less than $ n$, and the distances between arbitrary two are greater than $ 1$. (where the distances between two discs that have no common points are defined as that the distances between its centers subtract the sum of its radii; the distances between two discs that have common points are zero)

If the Highest Common Divisor of $ 6432$ and $ 132$ is diminished by $ 8$, it will equal: $ \textbf{(A)}\ \minus{}6 \qquad \textbf{(B)}\ 6 \qquad \textbf{(C)}\ \minus{}2 \qquad \textbf{(D)}\ 3 \qquad \textbf{(E)}\ 4$

Determine all positive integers $n$ such that $5^n - 1$ can be written as a product of an even number of consecutive integers.

Let $ \theta$ be an angle in the interval $ (0,\pi/2)$. Given that $ \cos \theta$ is irrational, and that $ \cos k \theta$ and $ \cos[(k \plus{} 1)\theta ]$ are both rational for some positive integer $ k$, show that $ \theta \equal{} \pi/6$.

Suppose that $n$ people $A_1$, $A_2$, $\ldots$, $A_n$, ($n \geq 3$) are seated in a circle and that $A_i$ has $a_i$ objects such that \[ a_1 + a_2 + \cdots + a_n = nN \] where $N$ is a positive integer. In order that each person has the same number of objects, each person $A_i$ is to give or to receive a certain number of objects to or from its two neighbours $A_{i-1}$ and $A_{i+1}$. (Here $A_{n+1}$ means $A_1$ and $A_n$ means $A_0$.) How should this redistribution be performed so that the total number of objects transferred is minimum?