Let $z_{0}\lt z_{1}\lt z_{2}\lt \cdots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n \geqslant 1$ such that
$$
f(x)= \begin{cases}x+\frac{1}{2} & \text { if } x\lt \frac{1}{2} \\ x^{2} & \text { if } x \geqslant \frac{1}{2}\end{cases}
$$
Let $a$ and $b$ be two real numbers such that $0\lt a\lt b\lt 1$. We define the sequences $a_{n}$ and $b_{n}$ by $a_{0}=a, b_{0}=b$, and $a_{n}=f\left(a_{n-1}\right), b_{n}=f\left(b_{n-1}\right)$ for $n\gt 0$. Show that there exists a positive integer $n$ such that
For a sequence $x_{1}, x_{2}, \ldots, x_{n}$ of real numbers, we define its price as
$$
\max _{1 \leqslant i \leqslant n}\left|x_{1}+\cdots+x_{i}\right|
$$
Given $n$ real numbers, Dave and George want to arrange them into a sequence with a low price. Diligent Dave checks all possible ways and finds the minimum possible price $D$. Greedy George, on the other hand, chooses $x_{1}$ such that $\left|x_{1}\right|$ is as small as possible; among the remaining numbers, he chooses $x_{2}$ such that $\left|x_{1}+x_{2}\right|$ is as small as possible, and so on. Thus, in the $i^{\text {th }}$ step he chooses $x_{i}$ among the remaining numbers so as to minimise the value of $\left|x_{1}+x_{2}+\cdots+x_{i}\right|$. In each step, if several numbers provide the same value, George chooses one at random. Finally he gets a sequence with price $G$.
Find the least possible constant $c$ such that for every positive integer $n$, for every collection of $n$ real numbers, and for every possible sequence that George might obtain, the resulting values satisfy the inequality $G \leqslant c D$.
Let $n$ points be given inside a rectangle $R$ such that no two of them lie on a line parallel to one of the sides of $R$. The rectangle $R$ is to be dissected into smaller rectangles with sides parallel to the sides of $R$ in such a way that none of these rectangles contains any of the given points in its interior. Prove that we have to dissect $R$ into at least $n+1$ smaller rectangles.
We have $2^{m}$ sheets of paper, with the number 1 written on each of them. We perform the following operation. In every step we choose two distinct sheets; if the numbers on the two sheets are $a$ and $b$, then we erase these numbers and write the number $a+b$ on both sheets. Prove that after $m 2^{m-1}$ steps, the sum of the numbers on all the sheets is at least $4^{m}$.
Let $n \geqslant 2$ be an integer. Consider an $n \times n$ chessboard divided into $n^{2}$ unit squares. We call a configuration of $n$ rooks on this board happy if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that for every happy configuration of rooks, we can find a $k \times k$ square without a rook on any of its $k^{2}$ unit squares.
Construct a tetromino by attaching two $2 \times 1$ dominoes along their longer sides such that the midpoint of the longer side of one domino is a corner of the other domino. This construction yields two kinds of tetrominoes with opposite orientations. Let us call them S- and Z-tetrominoes, respectively.
Assume that a lattice polygon $P$ can be tiled with S-tetrominoes. Prove than no matter how we tile $P$ using only S - and Z -tetrominoes, we always use an even number of Z -tetrominoes.
Consider $n \geqslant 3$ lines in the plane such that no two lines are parallel and no three have a common point. These lines divide the plane into polygonal regions; let $\mathcal{F}$ be the set of regions having finite area. Prove that it is possible to colour $\lceil\sqrt{n / 2}\rceil$ of the lines blue in such a way that no region in $\mathcal{F}$ has a completely blue boundary. (For a real number $x,\lceil x\rceil$ denotes the least integer which is not smaller than $x$.)
We are given an infinite deck of cards, each with a real number on it. For every real number $x$, there is exactly one card in the deck that has $x$ written on it. Now two players draw disjoint sets $A$ and $B$ of 100 cards each from this deck. We would like to define a rule that declares one of them a winner. This rule should satisfy the following conditions:
1. The winner only depends on the relative order of the 200 cards: if the cards are laid down in increasing order face down and we are told which card belongs to which player, but not what numbers are written on them, we can still decide the winner.
2. If we write the elements of both sets in increasing order as $A=\left\{a_{1}, a_{2}, \ldots, a_{100}\right\}$ and $B=\left\{b_{1}, b_{2}, \ldots, b_{100}\right\}$, and $a_{i}\gt b_{i}$ for all $i$, then $A$ beats $B$.
3. If three players draw three disjoint sets $A, B, C$ from the deck, $A$ beats $B$ and $B$ beats $C$, then $A$ also beats $C$.
How many ways are there to define such a rule? Here, we consider two rules as different if there exist two sets $A$ and $B$ such that $A$ beats $B$ according to one rule, but $B$ beats $A$ according to the other.
Let $M$ be a set of $n \geqslant 4$ points in the plane, no three of which are collinear. Initially these points are connected with $n$ segments so that each point in $M$ is the endpoint of exactly two segments. Then, at each step, one may choose two segments $A B$ and $C D$ sharing a common interior point and replace them by the segments $A C$ and $B D$ if none of them is present at this moment. Prove that it is impossible to perform $n^{3} / 4$ or more such moves.
A card deck consists of 1024 cards. On each card, a set of distinct decimal digits is written in such a way that no two of these sets coincide (thus, one of the cards is empty). Two players alternately take cards from the deck, one card per turn. After the deck is empty, each player checks if he can throw out one of his cards so that each of the ten digits occurs on an even number of his remaining cards. If one player can do this but the other one cannot, the one who can is the winner; otherwise a draw is declared.
Determine all possible first moves of the first player after which he has a winning strategy.
There are $n$ circles drawn on a piece of paper in such a way that any two circles intersect in two points, and no three circles pass through the same point. Turbo the snail slides along the circles in the following fashion. Initially he moves on one of the circles in clockwise direction. Turbo always keeps sliding along the current circle until he reaches an intersection with another circle. Then he continues his journey on this new circle and also changes the direction of moving, i.e. from clockwise to anticlockwise or vice versa.
Suppose that Turbo's path entirely covers all circles. Prove that $n$ must be odd.
The points $P$ and $Q$ are chosen on the side $B C$ of an acute-angled triangle $A B C$ so that $\angle P A B=\angle A C B$ and $\angle Q A C=\angle C B A$. The points $M$ and $N$ are taken on the rays $A P$ and $A Q$, respectively, so that $A P=P M$ and $A Q=Q N$. Prove that the lines $B M$ and $C N$ intersect on the circumcircle of the triangle $A B C$.
Let $A B C$ be a triangle. The points $K, L$, and $M$ lie on the segments $B C, C A$, and $A B$, respectively, such that the lines $A K, B L$, and $C M$ intersect in a common point. Prove that it is possible to choose two of the triangles $A L M, B M K$, and $C K L$ whose inradii sum up to at least the inradius of the triangle $A B C$.
Let $\Omega$ and $O$ be the circumcircle and the circumcentre of an acute-angled triangle $A B C$ with $A B\gt B C$. The angle bisector of $\angle A B C$ intersects $\Omega$ at $M \neq B$. Let $\Gamma$ be the circle with diameter $B M$. The angle bisectors of $\angle A O B$ and $\angle B O C$ intersect $\Gamma$ at points $P$ and $Q$, respectively. The point $R$ is chosen on the line $P Q$ so that $B R=M R$. Prove that $B R \| A C$. (Here we always assume that an angle bisector is a ray.)
Consider a fixed circle $\Gamma$ with three fixed points $A, B$, and $C$ on it. Also, let us fix a real number $\lambda \in(0,1)$. For a variable point $P \notin\{A, B, C\}$ on $\Gamma$, let $M$ be the point on the segment $C P$ such that $C M=\lambda \cdot C P$. Let $Q$ be the second point of intersection of the circumcircles of the triangles $A M P$ and $B M C$. Prove that as $P$ varies, the point $Q$ lies on a fixed circle.
Let $A B C D$ be a convex quadrilateral with $\angle B=\angle D=90^{\circ}$. Point $H$ is the foot of the perpendicular from $A$ to $B D$. The points $S$ and $T$ are chosen on the sides $A B$ and $A D$, respectively, in such a way that $H$ lies inside triangle $S C T$ and
$$
\angle S H C-\angle B S C=90^{\circ}, \quad \angle T H C-\angle D T C=90^{\circ} .
$$
Prove that the circumcircle of triangle $S H T$ is tangent to the line $B D$.
