RU-SPB 2020

What is the maximal number of solutions can the equation have $$\max \{a_1x+b_1, a_2x+b_2, \ldots, a_{10}x+b_{10}\}=0$$ where $a_1,b_1, a_2, b_2, \ldots , a_{10},b_{10}$ are real numbers, all $a_i$ not equal to $0$ .

For the triple $(a,b,c)$ of positive integers we say it is interesting if $c^2+1\mid (a^2+1)(b^2+1)$ but none of the $a^2+1, b^2+1$ are divisible by $c^2+1$ . Let $(a,b,c)$ be an interesting triple, prove that there are positive integers $u,v$ such that $(u,v,c)$ is interesting and $uv<c^3$ .

On a table with $25$ columns and $300$ rows, Kostya painted all its cells in three colors. Then, Lesha, looking at the table, for each row names one of the three colors and marks in that row all cells of that color (if there are no cells of that color in that row, he does nothing). After that, all columns that have at least a marked square will be deleted. Kostya wants to be left as few as possible columns in the table, and Lesha wants there to be as many as possible columns in the table. What is the largest number of columns Lesha can guarantee to leave?

Point $I_a$ is the $A$ -excircle center of $\triangle ABC$ which is tangent to $BC$ at $X$ . Let $A'$ be diametrically opposite point of $A$ with respect to the circumcircle of $\triangle ABC$ . On the segments $I_aX, BA'$ and $CA'$ are chosen respectively points $Y,Z$ and $T$ such that $I_aY=BZ=CT=r$ where $r$ is the inradius of $\triangle ABC$ . Prove that the points $X,Y,Z$ and $T$ are concyclic.

The points $(1,1),(2,3),(4,5)$ and $(999,111)$ are marked in the coordinate system. We continue to mark points in the following way :

• If points $(a,b)$ are marked then $(b,a)$ and $(a-b,a+b)$ can be marked
• If points $(a,b)$ and $(c,d)$ are marked then so can be $(ad+bc, 4ac-4bd)$ .

Can we, after some finite number of these steps, mark a point belonging to the line $y=2x$ .

Let $G$ be a graph with $400$ vertices. For any edge $AB$ we call a cuttlefish the set of all edges from $A$ and $B$ (including $AB$ ). Each edge of the graph is assigned a value of $1$ or $-1$ . It is known that the sum of edges at any cuttlefish is greater than or equal to $1$ . Prove that the sum of the numbers at all edges is at least $-10^4$ .

Andryusha has $100$ stones of different weight and he can distinguish the stones by appearance, but does not know their weight. Every evening, Andryusha can put exactly $10$ stones on the table and at night the brownie will order them in increasing weight. But, if the drum also lives in the house then surely he will in the morning change the places of some $2$ stones.Andryusha knows all about this but does not know if there is a drum in his house. Can he find out?

Find all positive integers $n$ such that the sum of the squares of the five smallest divisors of $n$ is a square.

Let $m$ be a given positive integer. Prove that there exists a positive integer $k$ such that it holds $$1\leq \frac{1^m+2^m+3^m+\ldots +(k-1)^m}{k^m}<2.$$

Rays $\ell, \ell_1, \ell_2$ have the same starting point $O$ , such that the angle between $\ell$ and $\ell_2$ is acute and the ray $\ell_1$ lies inside this angle. The ray $\ell$ contains a fixed point of $F$ and an arbitrary point $L$ . Circles passing through $F$ and $L$ and tangent to $\ell_1$ at $L_1$ , and passing through $F$ and $L$ and tangent to $\ell_2$ at $L_2$ . Prove that the circumcircle of $\triangle FL_1L_2$ passes through a fixed point other than $F$ independent on $L$ .

On a social network, no user has more than ten friends ( the state "friendship" is symmetrical). The network is connected: if, upon learning interesting news a user starts sending it to its friends, and these friends to their own friends and so on, then at the end, all users hear about the news. Prove that the network administration can divide users into groups so that the following conditions are met:

• each user is in exactly one group
• each group is connected in the above sense
• one of the groups contains from $1$ to $100$ members and the remaining from $100$ to $900$ .

The exam has $25$ topics, each of which has $8$ questions. On a test, there are $4$ questions of different topics. Is it possible to make $50$ tests so that each question was asked exactly once, and for any two topics there is a test where are questions of both topics?

A positive integer is called hypotenuse if it can be represented as a sum of two squares of non-negative integers. Prove that any natural number greater than $10$ is the difference of two hypotenuse numbers.

A short-sighted rook is a rook that beats all squares in the same column and in the same row for which he can not go more than $60$ - steps. What is the maximal amount of short-sighted rooks that don't beat each other that can be put on a $100\times 100$ chessboard.

$BB_1$ is the angle bisector of $\triangle ABC$ , and $I$ is its incenter. The perpendicular bisector of segment $AC$ intersects the circumcircle of $\triangle AIC$ at $D$ and $E$ . Point $F$ is on the segment $B_1C$ such that $AB_1=CF$ .Prove that the four points $B, D, E$ and $F$ are concyclic.

The sum $\frac{2}{3\cdot 6} +\frac{2\cdot 5}{3\cdot 6\cdot 9} +\ldots +\frac{2\cdot5\cdot \ldots \cdot 2015}{3\cdot 6\cdot 9\cdot \ldots \cdot 2019}$ is written as a decimal number. Find the first digit after the decimal point.

The altitudes $BB_1$ and $CC_1$ of the acute triangle $\triangle ABC$ intersect at $H$ . The circle centered at $O_b$ passes through points $A,C_1$ , and the midpoint of $BH$ . The circle centered at $O_c$ passes through $A,B_1$ and the midpoint of $CH$ . Prove that $B_1 O_b +C_1O_c > \frac{BC}{4}$

The sequence $a_n$ is given as $$a_1=1, a_2=2 \;\; \text{and} \;\;\; a_{n+2}=a_n(a_{n+1}+1) \forall n\geq 1$$ Prove that $a_{a_n}$ is divisible by $(a_n)^n$ for $n\geq 100$ .

$N$ oligarchs built a country with $N$ cities with each one of them owning one city. In addition, each oligarch built some roads such that the maximal amount of roads an oligarch can build between two cities is $1$ (note that there can be more than $1$ road going through two cities, but they would belong to different oligarchs). A total of $d$ roads were built. Some oligarchs wanted to create a corporation by combining their cities and roads so that from any city of the corporation you can go to any city of the corporation using only corporation roads (roads can go to other cities outside corporation) but it turned out that no group of less than $N$ oligarchs can create a corporation. What is the maximal amount that $d$ can have?