In how many ways we can choose 3 non empty and non intersecting subsets from $ (1,2,\ldots,2008)$.

A [i]string of parentheses[/i] is any word that can be composed by the following rules. 1) () is a string of parentheses. 2) If $s$ is a string of parentheses then $(s)$ is a string of parentheses. 3) If $s$ and t are strings of parentheses then $st$ is a string of parentheses. The [i]midcode [/i] of a string of parentheses is the tuple of natural numbers obtained by finding, for all pairs of opening and its corresponding closing parenthesis, the number of characters remaining to the left from the medium position between these parentheses, and writing all these numbers in non-decreasing order. For example, the midcode of $(())$ is $(2,2)$ and the midcode of ()() is $(1,3)$. Prove that midcodes of arbitrary two different strings of parentheses are different.

[u]Round 1 [/u] [b]p1.[/b] Pirate Jim had $8$ boxes with gun powder weighing $1, 2, 3, 4, 5, 6, 7$, and $8$ pounds (the weight is printed on top of every box). Pirate Bob hid a $1$-pound gold bar in one of these boxes. Pirate Jim has a balance scale that he can use, but he cannot open any of the boxes. Help him find the box with the gold bar using two weighings on the balance scale. [b]p2.[/b] James Bond will spend one day at Dr. Evil's mansion to try to determine the answers to two questions: a) Is Dr. Evil at home? b) Does Dr. Evil have an army of ninjas? The parlor in Dr. Evil's mansion has three windows. At noon, Mr. Bond will sneak into the parlor and use open or closed windows to signal his answers. When he enters the parlor, some windows may already be opened, and Mr. Bond will only have time to open or close one window (or leave them all as they are). Help Mr. Bond and Moneypenny design a code that will tell Moneypenny the answers to both questions when she drives by later that night and looks at the windows. Note that Moneypenny will not have any way to know which window Mr. Bond opened or closed. [b]p3.[/b] Suppose that you have a triangle in which all three side lengths and all three heights are integers. Prove that if these six lengths are all different, there cannot be four prime numbers among them. p4. Fred and George have designed the Amazing Maze, a $5\times 5$ grid of rooms, with Adorable Doors in each wall between rooms. If you pass through a door in one direction, you gain a gold coin. If you pass through the same door in the opposite direction, you lose a gold coin. The brothers designed the maze so that if you ever come back to the room in which you started, you will find that your money has not changed. Ron entered the northwest corner of the maze with no money. After walking through the maze for a while, he had $8$ shiny gold coins in his pocket, at which point he magically teleported himself out of the maze. Knowing this, can you determine whether you will gain or lose a coin when you leave the central room through the north door? [b]p5.[/b] Bill and Charlie are playing a game on an infinite strip of graph paper. On Bill’s turn, he marks two empty squares of his choice (not necessarily adjacent) with crosses. Charlie, on his turn, can erase any number of crosses, as long as they are all adjacent to each other. Bill wants to create a line of $2013$ crosses in a row. Can Charlie stop him? [u]Round 2 [/u] [b]p6.[/b] $1000$ non-zero numbers are written around a circle and every other number is underlined. It happens that each underlined number is equal to the sum of its two neighbors and that each non-underlined number is equal to the product of its two neighbors. What could the sum of all the numbers written on the circle be? [b]p7.[/b] A grasshopper is sitting at the edge of a circle of radius $3$ inches. He can hop exactly $4$ inches in any direction, as long as he stays within the circle. Which points inside the circle can the grasshopper reach if he can make as many jumps as he likes? [img]https://cdn.artofproblemsolving.com/attachments/1/d/39b34b2b4afe607c1232f4ce9dec040a34b0c8.png[/img] PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $p$ be a prime number and let $a_1,a_2,\dots,a_k$ be distinct integers chosen from $1,2,\dots,p-1$. For $1\le i \le k$, let $f_i^{(n)}$ denote the remainder of the integer $na_1$ upon division by $p$, so $0\le f_i^{(n)}<p$. Define $S=\{n:1\le n \le p-1,f_1^{(n)}<\dots<f_k^{(n)}\}$ Show that $S$ has less than $\frac{2p}{k+1}$ elements.

We are given a finite number of functions of the form $y = c2^{-|x-d|}$. In each case $c$ and $d$ are parameters with $c > 0$. The function $f(x)$ is defined on the interval $[a, b]$ as follows: For each $x$ in $[a, b]$, $f(x)$ is the maximum value taken by any of the given functions $y$ (defined above) at that point $x$. It is known that $f(a) = f(b)$. Prove that the total length of the intervals in which the function $f$ is increasing is equal to the total length of the intervals in which it is decreasing (that is, both are equal to $(b- a)/2$ ). (NB Vasiliev)

A rectangular array has $ n$ rows and $ 6$ columns, where $ n \geq 2$. In each cell there is written either $ 0$ or $ 1$. All rows in the array are different from each other. For each two rows $ (x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})$ and $ (y_{1},y_{2},y_{3},y_{4},y_{5},y_{6})$, the row $ (x_{1}y_{1},x_{2}y_{2},x_{3}y_{3},x_{4}y_{4},x_{5}y_{5},x_{6}y_{6})$ can be found in the array as well. Prove that there is a column in which at least half of the entries are zeros.

Prove that for each coloring of the points inside or on the boundary of a square with $1391$ colors, there exists a monochromatic regular hexagon.

Determine the smallest positive integer $k{}$ satisfying the following condition: For any configuration of chess queens on a $100 \times 100$ chequered board, the queens can be coloured one of $k$ colours so that no two queens of the same colour attack each other. [i]Russia, Sergei Avgustinovich and Dmitry Khramtsov[/i]

On some planet, there are $2^N$ countries $(N \geq 4).$ Each country has a flag $N$ units wide and one unit high composed of $N$ fields of size $1 \times 1,$ each field being either yellow or blue. No two countries have the same flag. We say that a set of $N$ flags is diverse if these flags can be arranged into an $N \times N$ square so that all $N$ fields on its main diagonal will have the same color. Determine the smallest positive integer $M$ such that among any $M$ distinct flags, there exist $N$ flags forming a diverse set. [i]Proposed by Tonći Kokan, Croatia[/i]

Number $ 0$ is written on the board. Two players alternate writing signs and numbers to the right, where the first player always writes either $ \plus{}$ or $ \minus{}$ sign, while the second player writes one of the numbers $ 1, 2, ... , 1993$,writing each of these numbers exactly once. The game ends after $ 1993$ moves. Then the second player wins the score equal to the absolute value of the expression obtained thereby on the board. What largest score can he always win?

Given a permutation of $1,2,3,\dots,n$, with consecutive elements $a,b,c$ (in that order), we may perform either of the [i]moves[/i]: [list] [*] If $a$ is the median of $a$, $b$, and $c$, we may replace $a,b,c$ with $b,c,a$ (in that order) [*] If $c$ is the median of $a$, $b$, and $c$, we may replace $a,b,c$ with $c,a,b$ (in that order) [/list] What is the least number of sets in a partition of all $n!$ permutations, such that any two permutations in the same set are obtainable from each other by a sequence of moves? [i]Proposed by Milan Haiman[/i]

Let $ F_n$ be a set of all possible connected figures, that consist of $ n$ unit cells. For each element $ f_n$ of this set, let $ S(f_n)$ be the area of that minimal rectangle that covers $ f_n$ and each side of the rectangle is parallel to the corresponding side of the cell. Find $ max(S(f_n))$,where $ f_n\in F_n$? Remark: Two cells are called connected if they have a common edge.

Allison has a coin which comes up heads $\frac23$ of the time. She flips it $5$ times. What is the probability that she sees more heads than tails?

In a blackboard there are $K$ circles in a row such that one of the numbers $1,...,K$ is assigned to each circle from the left to the right. Change of situation of a circle is to write in it or erase the number which is assigned to it.At the beginning no number is written in its own circle. For every positive divisor $d$ of $K$ ,$1\leq d\leq K$ we change the situation of the circles in which their assigned numbers are divisible by $d$,performing for each divisor $d$ $K$ changes of situation. Determine the value of $K$ for which the following holds;when this procedure is applied once for all positive divisors of $K$ ,then all numbers $1,2,3,...,K$ are written in the circles they were assigned in.

In a set $X$ of n people, some know each other and others do not, where the relationship to know is symmetric; that is, if $ A$ knows $ B$. then $ B$ knows $ A$. On the other hand, given any$ 4$ people: $A, B, C$ and $D$: if $A$ knows $B$, $B$ knows $C$ and $C$ knows $D$, then it happens at least one of the following three: $A$ knows $C, B$ knows $D$ or $A$ knows $D$. Prove that $X$ can be partition into two sets $Y$ and $Z$ so that all elements of $Y$ know all those of $Z$ or no element in $Y$ knows any in $Z$.

There are $n$ distinct points on a circumference. Choose one of the points. Connect this point and the $m$th point from the chosen point counterclockwise with a segment. Connect this $m$th point and the $m$th point from this $m$th point counterclockwise with a segment. Repeat such steps until no new segment is constructed. From the intersections of the segments, let the number of the intersections - which are in the circle - be $I$. Answer the following questions ($m$ and $n$ are positive integers that are relatively prime and they satisfy $6 \leq 2m < n$). 1) When the $n$ points take different positions, express the maximum value of $I$ in terms of $m$ and $n$. 2) Prove that $I \geq n$. Prove that there is a case, which is $I=n$, when $m=3$ and $n$ is arbitrary even number that satisfies the condition.

In year $2525$ the QED has $3n + 1$ members, of which $n$ are identical robots and $2n + 1$ (uncloned and therefore distinguishable) people. For the $263^{th}$ board election in Wurzburg there will be exactly $n$ members. Find out how many distinguishable compositions are conceivable for this.

At a circular track, $2n$ cyclists started from some point at the same time in the same direction with different constant speeds. If any two cyclists are at some point at the same time again, we say that they meet. No three or more of them have met at the same time. Prove that by the time every two cyclists have met at least once, each cyclist has had at least $n^2$ meetings.

Two players play a game on a pile of $n$ beans. On each player's turn, they may take exactly $1$, $4$, or $7$ beans from the pile. One player goes first, and then the players alternate until somebody wins. A player wins when they take the last bean from the pile. For how many $n$ between $2014$ and $2050$ (inclusive) does the second player win?

$a$ and $b$ are natural numbers such that $b > a > 1$, and $a$ does not divide $b$. The sequence of natural numbers $\{b_n\}_{n=1}^\infty$ satisfies $b_{n + 1} \geq 2b_n \forall n \in \mathbb{N}$. Does there exist a sequence $\{a_n\}_{n=1}^\infty$ of natural numbers such that for all $n \in \mathbb{N}$, $a_{n + 1} - a_n \in \{a, b\}$, and for all $m, l \in \mathbb{N}$ ($m$ may be equal to $l$), $a_m + a_l \not\in \{b_n\}_{n=1}^\infty$?

There are $24$ different pencils, $4$ different colors, and $6$ pencils of each color. They were given to $6$ children in such a way that each got $4$ pencils. What is the least number of children that you can randomly choose so that you can guarantee that you have pencils of all colors. P.S. for 10 grade gives same problem with $40$ pencils, $10$ of each color and $10$ children.

Show that there is a set of $2002$ consecutive positive integers containing exactly $150$ primes. (You may use the fact that there are $168$ primes less than $1000$)

There are $2025$ people living on the island, each of whom is either a knight, i.e. always tells the truth, or a liar, which means they always lie. Some of the inhabitants of the island know each other, and everyone has at least one acquaintance, but no more than three. Each inhabitant of the island claims that there are exactly two liars among his acquaintances. a) What is the smallest possible number of knights among the inhabitants of the island? b) What is the largest possible number of knights among the inhabitants of the island? [i]Proposed by Oleksii Masalitin[/i]

Show that there exist (at least) a rearrangement $a_0, a_1, a_2,..., a_{63}$ of the numbers $0,1, 2,..., 63$, such that $a_i - a_j \ne a_j - a_k$, for any $i < j < k \in \{0,1, 2,..., 63\}$.

On each of the 2006 cards a natural number is written. Cards are placed arbitrarily in a row. 2 players take in turns a card from any end of the row until all the cards are taken. After that each player calculates sum of the numbers written of his cards. If the sum of the first player is not less then the sum of the second one then the first player wins. Show that there's a winning strategy for the first player.