RU-ALLRUSSIAN 2023

Given are two monic quadratics $f(x), g(x)$ such that $f, g, f+g$ have two distinct real roots. Suppose that the difference of the roots of $f$ is equal to the difference of the roots of $g$ . Prove that the difference of the roots of $f+g$ is not bigger than the above common difference.

Initially, a word of $250$ letters with $125$ letters $A$ and $125$ letters $B$ is written on a blackboard. In each operation, we may choose a contiguous string of any length with equal number of letters $A$ and equal number of letters $B$ , reverse those letters and then swap each $B$ with $A$ and each $A$ with $B$ (Example: $ABABBA$ after the operation becomes $BAABAB$ ). Decide if it possible to choose initial word, so that after some operations, it will become the same as the first word, but in reverse order.

Every positive integer greater than $1000$ is colored in red or blue, such that the product of any two distinct red numbers is blue. Is it possible to happen that no two blue numbers have difference $1$?

Given is a triangle $ABC$ and a point $X$ inside its circumcircle. If $I_B, I_C$ denote the $B, C$ excenters, then prove that $XB \cdot XC <XI_B \cdot XI_C$ .

If there are several heaps of stones on the table, it is said that there are $\textit{many}$ stones on the table, if we can find $50$ piles and number them with the numbers from $1$ to $50$ so that the first pile contains at least one stone, the second - at least two stones,..., the $50$ -th has at least $50$ stones. Let the table be initially contain $100$ piles of $100$ stones each. Find the largest $n \leq 10 000$ such that after removing any $n$ stones, there will still be $\textit{many}$ stones left on the table.

Consider all $100$ -digit numbers divisible by $19$ . Prove that the number of such numbers not containing the digits $4, 5$ , and $6$ is the number of such numbers that do not contain the digits $1, 4$ and $7$ .

Petya has $10, 000$ balls, among them there are no two balls of equal weight. He also has a device, which works as follows: if he puts exactly $10$ balls on it, it will report the sum of the weights of some two of them (but he doesn't know which ones). Prove that Petya can use the device a few times so that after a while he will be able to choose one of the balls and accurately tell its weight.

Sidelines of an acute-angled triangle $T$ are colored in red, green, and blue. These lines were rotated about the circumcenter of $T$ clockwise by $120^\circ$ (we assume that the line has the same color after rotation). Prove that three points of pairs of lines of the same color are the vertices of a triangle which is congruent to $T$ .

A group of $100$ kids has a deck of $101$ cards numbered by $0, 1, 2,\dots, 100$ . The first kid takes the deck, shuffles it, and then takes the cards one by one; when he takes a card (not the last one in the deck), he computes the average of the numbers on the cards he took up to that moment, and writes down this average on the blackboard. Thus, he writes down $100$ numbers, the first of which is the number on the first taken card. Then he passes the deck to the second kid which shuffles the deck and then performs the same procedure, and so on. This way, each of $100$ kids writes down $100$ numbers. Prove that there are two equal numbers among the $10000$ numbers on the blackboard.

Given are positive integers $a, b$ satisfying $a \geq 2b$ . Does there exist a polynomial $P(x)$ of degree at least $1$ with coefficients from the set $\{0, 1, 2, \ldots, b-1 \}$ such that $P(b) \mid P(a)$ ?

There is a queue of $n{}$ girls on one side of a tennis table, and a queue of $n{}$ boys on the other side. Both the girls and the boys are numbered from $1{}$ to $n{}$ in the order they stand. The first game is played by the girl and the boy with the number $1{}$ and then, after each game, the loser goes to the end of their queue, and the winner remains at the table. After a while, it turned out that each girl played exactly one game with each boy. Prove that if $n{}$ is odd, then a girl and a boy with odd numbers played in the last game.

Proposed by A. Gribalko

Find the largest natural number $n$ for which the product of the numbers $n, n+1, n+2, \ldots, n+20$ is divisible by the square of one of them.

A square grid $100 \times 100$ is tiled in two ways - only with dominoes and only with squares $2 \times 2$. What is the least number of dominoes that are entirely inside some square $2 \times 2$?

Given is a real number $a \in (0,1)$ and positive reals $x_0, x_1, \ldots, x_n$ such that $\sum x_i=n+a$ and $\sum \frac{1}{x_i}=n+\frac{1}{a}$ . Find the minimal value of $\sum x_i^2$ .

If $x\in\mathbb{R}$ satisfy $sin$ $x+tan$ $x\in\mathbb{Q}$ , $cos$ $x+cot$ $x\in\mathbb{Q}$ Prove that $sin$ $2x$ is a root of an integral coefficient quadratic function

In every row of a grid $100 \times n$ is written a permutation of the numbers $1,2 \ldots, 100$. In one move you can choose a row and swap two non-adjacent numbers with difference $1$. Find the largest possible $n$, such that at any moment, no matter the operations made, no two rows may have the same permutations.

Let $\omega$ be the circumcircle of triangle $ABC$ with $AB<AC$ . Let $I$ be its incenter and let $M$ be the midpoint of $BC$ . The foot of the perpendicular from $M$ to $AI$ is $H$ . The lines $MH, BI, AB$ form a triangle $T_b$ and the lines $MH, CI, AC$ form a triangle $T_c$ . The circumcircle of $T_b$ meets $\omega$ at $B'$ and the circumcircle of $T_c$ meets $\omega$ at $C'$ . Prove that $B', H, C'$ are collinear.

Initially, $10$ ones are written on a blackboard. Grisha and Gleb are playing game, by taking turns; Grisha goes first. On one move Grisha squares some $5$ numbers on the board. On his move, Gleb picks a few (perhaps none) numbers on the board and increases each of them by $1$ . If in $10,000$ moves on the board a number divisible by $2023$ appears, Gleb wins, otherwise Grisha wins. Which of the players has a winning strategy?

We call a polynomial $P(x)$ good if the numbers $P(k)$ and $P'(k)$ are integers for all integers $k$ . Let $P(x)$ be a good polynomial of degree $d$ , and let $N_d$ be the product of all composite numbers not exceeding $d$ . Prove that the leading coefficient of the polynomial $N_d \cdot P(x)$ is integer.

In a country, there are ${}N{}$ cities and $N(N-1)$ one-way roads: one road from $X{}$ to $Y{}$ for each ordered pair of cities $X \neq Y$ . Every road has a maintenance cost. For each $k = 1,\ldots, N$ let's consider all the ways to select $k{}$ cities and $N - k{}$ roads so that from each city it is possible to get to some selected city, using only selected roads.

We call such a system of cities and roads with the lowest total maintenance cost $k{}$ -optimal. Prove that cities can be numbered from $1{}$ to $N{}$ so that for each $k = 1,\ldots, N$ there is a $k{}$ -optimal system of roads with the selected cities numbered $1,\ldots, k$ .

Proposed by V. Buslov