TUYMAADA 2023

Prove that for $a, b, c \in [0;1]$ , $$(1-a)(1+ab)(1+ac)(1-abc) \leq (1+a)(1-ab)(1-ac)(1+abc).$$

Serge and Tanya want to show Masha a magic trick. Serge leaves the room. Masha writes down a sequence $(a_1, a_2, \ldots , a_n)$ , where all $a_k$ equal $0$ or $1$ . After that Tanya writes down a sequence $(b_1, b_2, \ldots , b_n)$ , where all $b_k$ also equal $0$ or $1$ . Then Masha either does nothing or says "Mutabor" and replaces both sequences: her own sequence by $(a_n, a_{n-1}, \ldots , a_1)$ , and Tanya's sequence by $(1 - b_n, 1 - b_{n-1}, \ldots , 1 - b_1)$ . Masha's sequence is covered by a napkin, and Serge is invited to the room. Serge should look at Tanya's sequence and tell the sequence covered by the napkin. For what $n$ Serge and Tanya can prepare and show such a trick? Serge does not have to determine whether the word "Mutabor" has been pronounced.

Point $L$ inside triangle $ABC$ is such that $CL = AB$ and $\angle BAC + \angle BLC = 180^{\circ}$ . Point $K$ on the side $AC$ is such that $KL \parallel BC$ . Prove that $AB = BK$

Two players play a game. They have $n > 2$ piles containing $n^{10}+1$ stones each. A move consists of removing all the piles but one and dividing the remaining pile into $n$ nonempty piles. The player that cannot move loses. Who has a winning strategy, the player that moves first or his adversary?

A graph contains $p$ vertices numbered from $1$ to $p$ , and $q$ edges numbered from $p + 1$ to $p + q$ . It turned out that for each edge the sum of the numbers of its ends and of the edge itself equals the same number $s$ . It is also known that the numbers of edges starting in all vertices are equal. Prove that $$s = \dfrac{1}{2} (4p+q+3).$$

An $\textit{Euclidean step}$ transforms a pair $(a, b)$ of positive integers, $a > b$ , to the pair $(b, r)$ , where $r$ is the remainder when a is divided by $b$ . Let us call the $\textit{complexity}$ of a pair $(a, b)$ the number of Euclidean steps needed to transform it to a pair of the form $(s, 0)$ . Prove that if $ad - bc = 1$ , then the complexities of $(a, b)$ and $(c, d)$ differ at most by $2$ .

$3n$ people forming $n$ families of a mother, a father and a child, stand in a circle. Every two neighbours can exchange places except the case when a parent exchanges places with his/her child (this is forbidden). For what $n$ is it possible to obtain every arrangement of those people by such exchanges? The arrangements differing by a circular shift are considered distinct.

Circle $\omega$ lies inside the circle $\Omega$ and touches it internally at point $P$ . Point $S$ is taken on $\omega$ and the tangent to $\omega$ is drawn through it. This tangent meets $\Omega$ at points $A$ and $B$ . Let $I$ be the centre of $\omega$ . Find the locus of circumcentres of triangles $AIB$ .

The numbers $1, 2, 3, \ldots$ are arranged in a spiral in the vertices of an infinite square grid (see figure). Then in the centre of each square the sum of the numbers in its vertices is placed. Prove that for each positive integer n the centres of the squares contain infinitely many multiples of $n$ .

Attachments:

In a graph with $n$ vertices every two vertices are connected by a unique path. For each two vertices $u$ and $v$ , let $d(u, v)$ denote the distance between $u$ and $v$ , i.e. the number of edges in the path connecting these two vertices, and $\deg(u)$ denote the degree of a vertex $u$ . Let $W$ be the sum of pairwise distances between the vertices, and $D$ the sum of weighted pairwise distances: $\sum_{\{u, v\}}(\deg(u)+\deg(v))d(u, v)$ . Prove that $D=4W-n(n-1)$ .

Two points $A$ and $B$ and line $\ell$ are fixed in the plane so that $\ell$ is not perpendicular to $AB$ and does not intersect the segment $AB$ . We consider all circles with a centre $O$ not lying on $\ell$ , passing through $A$ and $B$ and meeting $\ell$ at some points $C$ and $D$ . Prove that all the circumcircles of triangles $OCD$ touch a fixed circle.

A small ship sails on an infinite coordinate sea. At the moment $t$ the ship is at the point with coordinates $(f(t), g(t))$ , where $f$ and $g$ are two polynomials of third degree. Yesterday at $14:00$ the ship was at the same point as at $13:00$ , and at $20:00$ , it was at the same point as at $19:00$ . Prove that the ship sails along a straight line.

In the plane $n$ segments with lengths $a_1, a_2, \dots , a_n$ are drawn. Every ray beginning at the point $O$ meets at least one of the segments. Let $h_i$ be the distance from $O$ to the $i$ -th segment (not the line!) Prove the inequality $$\frac{a_1}{h_1}+\frac{a_2}{h_2} + \ldots + \frac{a_i}{h_i} \geqslant 2 \pi.$$

Hexagonal pieces numbered by positive integers are placed on the cells of a hexagonal board with side $n$ . Two adjacent cells are left empty, and thanks to it some pieces can be moved. Two pieces with common sides exchanged places (see an example in the attachment 2).

Prove that if $n \ge 3$ the second arrangement cannot be obtained from the first one by moving piece

Note. Moving a piece a requires two adjacent empty cells. For instance, if they are on the right of a (attachment 1, left figure), a can be moved right till it touches an angle (attachment 1, middle figure), and then it can be moved upward right or downward right (attachment 1, right figure)

Attachments:

Given is a positive integer $n$ . Let $A$ be the set of points $x \in (0;1)$ such that $|x-\frac{p} {q}|>\frac{1}{n^3}$ for each rational fraction $\frac{p} {q}$ with denominator $q \leq n^2$ . Prove that $A$ is a union of intervals with total length not exceeding $\frac{100}{n}$ .

Proposed by Fedor Petrov