[Solutions] International Zhautykov Mathematical Olympiad 2021

1. Prove that there exists a positive integer $n$, such that the remainder of $3^n$ when divided by $2^n$ is greater than $10^{2021}$.
2. In a convex cyclic hexagon $ABCDEF$, $BC=EF$ and $CD=AF$. Diagonals $AC$ and $BF$ intersect at point $Q,$ and diagonals $EC$ and $DF$ intersect at point $P$. Points $R$ and $S$ are marked on the segments $DF$ and $BF$ respectively so that $FR=PD$ and $BQ=FS.$ The segments $RQ$ and $PS$ intersect at point $T.$ Prove that the line $TC$ bisects the diagonal $DB$.
3. Let $n\ge 2$ be an integer. Elwyn is given an $n\times n$ table filled with real numbers (each cell of the table contains exactly one number). We define a rook set as a set of $n$ cells of the table situated in $n$ distinct rows as well as in n distinct columns. Assume that, for every rook set, the sum of $n$ numbers in the cells forming the set is nonnegative. By a move, Elwyn chooses a row, a column, and a real number $a$, and then he adds $a$ to each number in the chosen row, and subtracts $a$ from each number in the chosen column (thus, the number at the intersection of the chosen row and column does not change). Prove that Elwyn can perform a sequence of moves so that all numbers in the table become nonnegative.
4. Let there be an incircle of triangle $ABC$, and $3$ circles each inscribed between incircle and angles of $ABC$.
5. Let $r$, $r_1$, $r_2$, $r_3$ be radii of these circles $(r_1, r_2, r_3 < r)$. Prove that $$r_1+r_2+r_3 \geq r.$$
6. On a party with $99$ guests, hosts Ann and Bob play a game (the hosts are not regarded as guests). There are $99$ chairs arranged in a circle; initially, all guests hang around those chairs. The hosts take turns alternately. By a turn, a host orders any standing guest to sit on an unoccupied chair $c$. If some chair adjacent to $c$ is already occupied, the same host orders one guest on such chair to stand up (if both chairs adjacent to $c$ are occupied, the host chooses exactly one of them). All orders are carried out immediately. Ann makes the first move; her goal is to fulfill, after some move of hers, that at least $k$ chairs are occupied. Determine the largest $k$ for which Ann can reach the goal, regardless of Bob's play.
7. Let $P(x)$ be a nonconstant polynomial of degree $n$ with rational coefficients which can not be presented as a product of two nonconstant polynomials with rational coefficients. Prove that the number of polynomials $Q(x)$ of degree less than $n$ with rational coefficients such that $P(x)$ divides $P(Q(x))$
   a) is finite
   b) does not exceed $n$.

DOWNLOAD SOLUTIONS