MathNet 2016-part-05 — 184 problems (EN–VI)

Show that there are infinitely many positive integers $n$ such that $n$ has at least two prime divisors and $20^{n}+16^{n}$ is divisible by $n^{2}$.

On a checkered square $10 \times 10$ the cells of the upper left $5 \times 5$ square are black and all the other cells are white. What is the maximal $n$ such that the original square can be dissected (along the borders of the cells) into $n$ polygons such that in each of them the number of black cells is three times less than the number of white cells? (The polygons need not be congruent or even equal in area.)

Let $P_{i}(x) = x^{2} + b_{i} x + c_{i}$ for $i = 1, 2, \cdots, n$ be pairwise distinct polynomials of degree $2$ with real coefficients so that for any $0 \leq i \lt j \leq n$; $i, j \in \mathbb{N}$, the polynomial $Q_{i, j}(x) = P_{i}(x) + P_{j}(x)$ has only one real root. Find the greatest possible value of $n$.

A circle with center $O$ passes through points $A$ and $C$ and intersects the sides $AB$ and $BC$ of triangle $ABC$ at points $K$ and $N$, respectively. The circumcircles of triangles $ABC$ and $KBN$ meet at distinct points $B$ and $M$. Prove that $\angle OMB = 90^{\circ}$.

Let $m, n$ be odd integers such that $n^{2}-1$ is divisible by $m^{2}+1-n^{2}$. Prove that $\left|m^{2}+1-n^{2}\right|$ is a perfect square.

How many ways are there to color the vertices of a square with $n$ colors $1, 2, \ldots, n$. (The colorings must be different so that we can't get one from the other by a rotation.)

Let $a \gt b \gt c \gt d$ be positive integers such that $a^{2} + a c - c^{2} = b^{2} + b d - d^{2}$. Prove that $a b + c d$ is a composite number.

Let $ABC$ be a triangle and $I$ its incenter. The point $D$ is on segment $BC$ and the circle $\omega$ is tangent to the circumcircle of triangle $ABC$ but is also tangent to $DC$, $DA$ at $E$, $F$, respectively. Prove that $E$, $F$ and $I$ are collinear.

Does there exist a polynomial $P(x)$ with integral coefficients such that

1. $P(\sqrt[3]{25}+\sqrt[3]{5})=220 \sqrt[3]{25}+284 \sqrt[3]{5}$ ?

2. $P(\sqrt[3]{25}+\sqrt[3]{5})=1184 \sqrt[3]{25}+1210 \sqrt[3]{5}$ ?

On a chessboard $5 \times 9$ squares, the following game is played. Initially, a number of frogs are randomly placed on some of the squares, no square containing more than one frog. A turn consists of moving all of the frogs subject to the following rules:
- Each frog may be moved one square up, down, left, or right;
- If a frog moves up or down on one turn, it must move left or right on the next turn, and vice versa;
- At the end of each turn, no square can contain two or more frogs.
The game stops if it becomes impossible to complete another turn. Prove that if initially 33 frogs are placed on the board, the game must eventually stop. Prove also that it is possible to place 32 frogs on the board so that the game can continue forever.

There are totally $16$ teams participating in a football tournament; each team playing with every other exactly $1$ time. In each match, the winner gains $3$ points, the loser gains $0$ point and each team gains $1$ point for the tie match. Suppose that at the end of the tournament, each team gains the same number of points. Prove that there are at least $4$ teams that have the same number of winning matches, the same number of losing matches and the same number of tie matches.

Let $ABC$ be an acute, non-isosceles triangle with the circumcircle ($O$). Denote $D, E$ as the midpoints of $AB, AC$ respectively. Two circles $(ABE)$ and $(ACD)$ intersect at $K$ differs from $A$. Suppose that the ray $AK$ intersects ($O$) at $L$. The line $LB$ meets $(ABE)$ at the second point $M$ and the line $LC$ meets $(ACD)$ at the second point $N$.
1. Prove that $M, K, N$ collinear and $MN$ perpendicular to $OL$.
2. Prove that $K$ is the midpoint of $MN$.

Let $a, b$ be given two real numbers with $a \neq 0$. Find all polynomials $P$ with real coefficients such that
$$
x P(x-a) = (x-b) P(x) \text{ for all } x \in \mathbb{R}.
$$

In a school, there are totally $n$ students, with $n \geq 2$. The students take part in $m$ clubs and in each club, there are at least $2$ members (a student may take part in more than $1$ club). Eventually, the Principal notices that: If $2$ clubs share at least $2$ common members then they have different numbers of members. Prove that
$$
m \leq (n-1)^2.
$$

Let $ABC$ be an acute, non-isosceles triangle which is inscribed in a circle $(O)$. A point $I$ belongs to the segment $BC$. Denote by $H$ and $K$ the projections of $I$ on $AB$ and $AC$, respectively. Suppose that the line $HK$ intersects $(O)$ at $M, N$ ($H$ is between $M, K$ and $K$ is between $H, N$). Let $X, Y$ be the centers of the circles $(ABK), (ACH)$ respectively. Prove the following assertions:

1. If $I$ is the projection of $A$ on $BC$, then $A$ is the center of circle $(IMN)$.

2. If $XY \parallel BC$, then the orthocenter of $XOY$ is the midpoint of $IO$.

Let $n \geq 1$ be a fixed positive integer. We consider all the sets $S$ which consist of sub-sequences of the sequence $0,1,2, \ldots, n$ satisfying the following conditions:
i) If $\left(a_{i}\right)_{i=0}^{k}$ belongs to $S$, then $a_{0}=0, a_{k}=n$ and $a_{i+1}-a_{i} \leq 2$ for all $0 \leq i \leq k-1$.
ii) If $\left(a_{i}\right)_{i=0}^{k}$ and $\left(b_{j}\right)_{j=0}^{h}$ both belong to $S$, then there exist $0 \leq i_{0} \leq k-1$ and $0 \leq j_{0} \leq h-1$ such that $a_{i_{0}}=b_{j_{0}}$ and $a_{i_{0}+1}=b_{j_{0}+1}$.

Find the maximum value of $|S|$ (among all the above-mentioned sets $S$ ).

Find all polynomials $P, Q \in \mathbb{Z}[x]$ such that every positive integer is a divisor of a certain nonzero term of the sequence $\left(x_{n}\right)_{n=0}^{\infty}$ given by the conditions:
$$
x_{0}=2016,\quad x_{2 n+1}=P\left(x_{2 n}\right),\quad x_{2 n+2}=Q\left(x_{2 n+1}\right) \text{ for all } n \geq 0.
$$

Let $f(x) = x^{2} + a x + b$ be a quadratic function with real coefficients $a, b$. It is given that the equation $f(f(x)) = 0$ has 4 distinct real roots and the sum of 2 roots among these roots is equal to $-1$. Prove that $b \leq \frac{-1}{4}$.

Let $(O_{1})$, $(O_{2})$ be given two circles intersecting at $A$ and $B$. The tangent lines of $(O_{1})$ at $A$, $B$ intersect at $O$. Let $I$ be a point on the circle $(O_{1})$ but outside the circle $(O_{2})$. The lines $IA$, $IB$ intersect circle $(O_{2})$ at $C$, $D$. Denote by $M$ the midpoint of $CD$. Prove that $I$, $M$, $O$ are collinear.

Find all positive integer $n$ such that there exists a permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $\left(1,2,3, \ldots, n\right)$ satisfying the condition:
$$
a_{1}+a_{2}+\cdots+a_{k} \text{ is divisible by } k \text{ for each } k=1,2,3, \ldots, n \text{. }
$$