Ross wants to play solitaire with his deck of $n$ playing cards, but he’s discovered that the deck is “boxed”: some cards are face up, and others are face down. He wants to turn them all face down again, by repeatedly choosing a block of consecutive cards, removing the block from the deck, turning it over, and replacing it back in the deck at the same point. What is the smallest number of such steps Ross needs in order to guarantee that he can turn all the cards face down again, regardless of how they start out?

Let $n>1$ be a positive integer. Find the number of binary strings $(a_1, a_2, \ldots, a_n)$, such that the number of indices $1\leq i \leq n-1$ such that $a_i=a_{i+1}=0$ is equal to the number of indices $1 \leq i \leq n-1$, such that $a_i=a_{i+1}=1$.

Let $n \ge 2$ be an integer. Alex writes the numbers $1, 2, ..., n$ in some order on a circle such that any two neighbours are coprime. Then, for any two numbers that are not comprime, Alex draws a line segment between them. For each such segment $s$ we denote by $d_s$ the difference of the numbers written in its extremities and by $p_s$ the number of all other drawn segments which intersect $s$ in its interior. Find the greatest $n$ for which Alex can write the numbers on the circle such that $p_s \le |d_s|$, for each drawn segment $s$.

Consider the number obtained by writing the numbers $1,2,\ldots,1990$ one after another. In this number every digit on an even position is omitted; in the so obtained number, every digit on an odd position is omitted; then in the new number every digit on an even position is omitted, and so on. What will be the last remaining digit?

Determine the greatest positive integer $k$ that satisfies the following property: The set of positive integers can be partitioned into $k$ subsets $A_1, A_2, \ldots, A_k$ such that for all integers $n \geq 15$ and all $i \in \{1, 2, \ldots, k\}$ there exist two distinct elements of $A_i$ whose sum is $n.$ [i]Proposed by Igor Voronovich, Belarus[/i]

An exam at a university consists of one question randomly selected from the$ n$ possible questions. A student knows only one question, but he can take the exam $n$ times. Express as a function of $n$ the probability $p_n$ that the student will pass the exam. Does $p_n$ increase or decrease as $n$ increases? Compute $lim_{n\to \infty}p_n$. What is the largest lower bound of the probabilities $p_n$?

$2n$ students take part in a math competition. First, each of the students sends its task to the members of the jury, after which each of the students receives from the jury one of proposed tasks (all received tasks are different). Let's call the competition [i]honest[/i], if there are $n$ students who were given the tasks suggested by the remaining $n$ participants. Prove that the number of task distributions in which the competition is honest is a square of natural numbers.

A circular disk is partitioned into $ 2n$ equal sectors by $ n$ straight lines through its center. Then, these $ 2n$ sectors are colored in such a way that exactly $ n$ of the sectors are colored in blue, and the other $ n$ sectors are colored in red. We number the red sectors with numbers from $ 1$ to $ n$ in counter-clockwise direction (starting at some of these red sectors), and then we number the blue sectors with numbers from $ 1$ to $ n$ in clockwise direction (starting at some of these blue sectors). Prove that one can find a half-disk which contains sectors numbered with all the numbers from $ 1$ to $ n$ (in some order). (In other words, prove that one can find $ n$ consecutive sectors which are numbered by all numbers $ 1$, $ 2$, ..., $ n$ in some order.) [hide="Problem 8 from CWMO 2007"]$ n$ white and $ n$ black balls are placed at random on the circumference of a circle.Starting from a certain white ball,number all white balls in a clockwise direction by $ 1,2,\dots,n$. Likewise number all black balls by $ 1,2,\dots,n$ in anti-clockwise direction starting from a certain black ball.Prove that there exists a chain of $ n$ balls whose collection of numbering forms the set $ \{1,2,3\dots,n\}$.[/hide]

In a $9\times9$ board, the squares are labeled from 11 to 99, with the first digit indicating the row and the second digit indicating the column. One would like to paint the squares in black or white in a way that each black square is adjacent to at most one other black square and each white square is adjacent to at most one other white square. Two squares are adjacent if they share a common side. How many ways are there to paint the board such that the squares $44$ and $49$ are both black?

Simultaneously from the same point of a circular route and in the same direction for two hours two bodies move evenly. The first body performs a complete rotation three minutes faster than the second body and exceeds it every $9$ minutes and $20$ seconds. Whenever the first body will overtake the other the second exactly at the starting point?

Let $m,n \geqslant 2$ be integers, let $X$ be a set with $n$ elements, and let $X_1,X_2,\ldots,X_m$ be pairwise distinct non-empty, not necessary disjoint subset of $X$. A function $f \colon X \to \{1,2,\ldots,n+1\}$ is called [i]nice[/i] if there exists an index $k$ such that \[\sum_{x \in X_k} f(x)>\sum_{x \in X_i} f(x) \quad \text{for all } i \ne k.\] Prove that the number of nice functions is at least $n^n$.

Let $n$, $k$ be fixed integers. On a $n \times n$ board, label each square $0$ or $1$ such that in each $2k \times 2k$ sub-square of the board, the number of $0$'s and $1$'s written are the same. What is the largest possible sum of numbers written on the $n\times n$ board?

For integers $m,n \ge 3$ we consider a $m \times n$ rectangular frame, consisting of the $2m+2n-4$ boundary squares of a $m \times n$ rectangle. Renate and Erhard play the following game on this frame, with Renate to start the game. In a move, a player colours a rectangular area consisting of a single or several white squares. If there are any more white squares, they have to form a connected region. The player who moves last wins the game. Determine all pairs $(m,n)$ for which Renate has a winning strategy.

Let $n > 1$ be a given integer. An $n \times n \times n$ cube is composed of $n^3$ unit cubes. Each unit cube is painted with one colour. For each $n \times n \times 1$ box consisting of $n^2$ unit cubes (in any of the three possible orientations), we consider the set of colours present in that box (each colour is listed only once). This way, we get $3n$ sets of colours, split into three groups according to the orientation. It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$, the maximal possible number of colours that are present.

The closed broken line $M$ has odd number of vertices -- $A_1,A_2,..., A_{2n+1}$ in sequence. Let us denote with $S(M)$ a new closed broken line with vertices $B_1,B_2,...,B_{2n+1}$ -- the midpoints of the first line links: $B_1$ is the midpoint of $[A_1A_2], ... , B_{2n+1}$ -- of $[A_{2n+1}A_1]$. Prove that in a sequence $M_1=S(M), ... , M_k = S(M_{k-1}), ...$ there is a broken line, homothetic to the $M$.

Each edge of a complete graph on $30$ vertices is coloured either red or blue. It is allowed to choose a non-monochromatic triangle and change the colour of the two edges of the same colour to make the triangle monochromatic. Prove that by using this operation repeatedly it is possible to make the entire graph monochromatic. (A complete graph is a graph where any two vertices are connected by an edge.)

$8$ people participate in a party. (1) Among any $5$ people there are $3$ who pairwise know each other. Prove that there are $4$ people who paiwise know each other. (2) If Among any $6$ people there are $3$ who pairwise know each other, then can we find $4$ people who pairwise know each other?

In the unit squre For the given natural number $n \geq 2$ find the smallest number $k$ that from each set of $k$ unit squares of the $n$x$n$ chessboard one can achoose a subset such that the number of the unit squares contained in this subset an lying in a row or column of the chessboard is even

On an $8\times 8$ chessboard, 6 black rooks and k white rooks are placed on different cells so that each rook only attacks rooks of the opposite color. Compute the maximum possible value of $k$. (Two rooks attack each other if they are in the same row or column and no rooks are between them.)

Let $A$ be a finite set of positive reals, let $B = \{x/y\mid x,y\in A\}$ and let $C = \{xy\mid x,y\in A\}$. Show that $|A|\cdot|B|\le|C|^2$. [i](Proposed by Gerhard Woeginger, Austria)[/i]

Given an $8\times 8$ chess board, in how many ways can we select $56$ squares on the board while satisfying both of the following requirements: (a) All black squares are selected. (b) Exactly seven squares are selected in each column and in each row.

Consider $2009$ cards, each having one gold side and one black side, lying on parallel on a long table. Initially all cards show their gold sides. Two player, standing by the same long side of the table, play a game with alternating moves. Each move consists of choosing a block of $50$ consecutive cards, the leftmost of which is showing gold, and turning them all over, so those which showed gold now show black and vice versa. The last player who can make a legal move wins. (a) Does the game necessarily end? (b) Does there exist a winning strategy for the starting player? [i]Proposed by Michael Albert, Richard Guy, New Zealand[/i]

A five-digit positive integer $abcde_{10}$ ($a\neq 0$) is said to be a [i]range[/i] if its digits satisfy the inequalities $a<b>c<d>e$. For example, $37452$ is a range. How many ranges are there?

Let $S=\{1,2,...,100\}$ . Find number of functions $f: S\to S$ satisfying the following conditions a)$f(1)=1$ b)$f$ is bijective c)$f(n)=f(g(n))f(h(n))\forall n\in S$, where $g(n),h(n)$ are positive integer numbers such that $g(n)\leq h(n),n=g(n)h(n)$ that minimize $h(n)-g(n)$.

Let $ n$ be positive integer, $ A,B\subseteq[0,n]$ are sets of integers satisfying $ \mid A\mid \plus{} \mid B\mid\ge n \plus{} 2.$ Prove that there exist $ a\in A, b\in B$ such that $ a \plus{} b$ is a power of $ 2.$