MathNet 1996 — Part 01

$ABC$ is acute-angled. $D$ is a variable point on the side $BC$. $O_1$ is the circumcenter of $ABD$, $O_2$ is the circumcenter of $ACD$, and $O$ is the circumcenter of $AO_1O_2$. Find the locus of $O$.

Let $f(n)$ be the smallest number of $1$s needed to represent the positive integer $n$ using only $1$s, $+$ signs, $\times$ signs and brackets. For example, you could represent $80$ with $13$ $1$s as follows: $(1+1+1+1+1) \times (1+1+1+1) \times (1+1+1+1)$. Show that $3\log_3 n \le f(n) \le 5\log_3 n$ for $n \gt 1$.

There are $n$ boys $B_1, B_2, \dots, B_n$ and $n$ girls $G_1, G_2, \dots, G_n$. Each boy ranks the girls in order of preference, and each girl ranks the boys in order of preference. Show that we can arrange the boys and girls into $n$ pairs so that we cannot find a boy and a girl who prefer each other to their partners. For example if $(B_1, G_3)$ and $(B_4, G_7)$ are two of the pairs, then it must not be the case that $B_4$ prefers $G_3$ to $G_7$ and $G_3$ prefers $B_4$ to $B_1$.

Let $p(x)$ be the polynomial $x^3 + 14x^2 - 2x + 1$. Let $p^{(n)}(x)$ denote $p(p^{(n-1)}(x))$. Show that there is an integer $N$ such that $p^{(N)}(x) - x$ is divisible by $101$ for all integers $x$.

Does there exist a set of $n \gt 2$ points in the plane such that no three are collinear and the circumcenter of any three points of the set is also in the set?

Show that the equation $x^2 + y^2 + z^2 = 3xyz$ has infinitely many solutions in positive integers.

Let $S$ be a set of integers containing the numbers $0$ and $1996$. Suppose further that any integer root of any non-zero polynomial with coefficients in $S$ also belongs to $S$. Prove that $-2$ belongs to $S$.

Let $\alpha$ be the angle between two lines containing the diagonals of a regular 1996-gon, and let $\beta \neq 0$ be another such angle. Prove that $\alpha / \beta$ is a rational number.

On an infinite checkerboard, two players alternately mark one unmarked cell. One of them uses $\times$, the other $o$. The first who fills a $2 \times 2$ square with his symbols wins. Can the player who starts always win?

The real numbers $x_{1}, x_{2}, \ldots, x_{1996}$ have the following property: for any polynomial $W$ of degree $2$ at least three of the numbers $W\left(x_{1}\right), W\left(x_{2}\right), \ldots, W\left(x_{1996}\right)$ are equal. Prove that at least three of the numbers $x_{1}, x_{2}, \ldots, x_{1996}$ are equal.

For which positive real numbers $a, b$ does the inequality
$$
x_{1} \cdot x_{2}+x_{2} \cdot x_{3}+\cdots+x_{n-1} \cdot x_{n}+x_{n} \cdot x_{1} \geq x_{1}^{a} \cdot x_{2}^{b} \cdot x_{3}^{a}+x_{2}^{a} \cdot x_{3}^{b} \cdot x_{4}^{a}+\cdots+x_{n}^{a} \cdot x_{1}^{b} \cdot x_{2}^{a}
$$
hold for all integers $n\gt 2$ and positive real numbers $x_{1}, x_{2}, \ldots, x_{n}$ ?

Four heaps contain $38$, $45$, $61$, and $70$ matches respectively. Two players take turns choosing any two of the heaps and take some non-zero number of matches from one heap and some non-zero number of matches from the other heap. The player who cannot make a move, loses. Which one of the players has a winning strategy?

Consider the functions $f$ defined on the set of integers such that
$$
f(x) = f\left(x^{2} + x + 1\right),
$$
for all integers $x$. Find

(a) all even functions,

(b) all odd functions of this kind.

$ABCD$ is a trapezium ($AD \parallel BC$). $P$ is the point on the line $AB$ such that $\angle CPD$ is maximal. $Q$ is the point on the line $CD$ such that $\angle BQA$ is maximal. Given that $P$ lies on the segment $AB$, prove that $\angle CPD = \angle BQA$.

Using each of the eight digits $1, 3, 4, 5, 6, 7, 8$ and $9$ exactly once, a three-digit number $A$, two two-digit numbers $B$ and $C$, $B \lt C$, and a one-digit number $D$ are formed. The numbers are such that $A + D = B + C = 143$. In how many ways can this be done?

The jury of an olympiad has 30 members in the beginning. Each member of the jury thinks that some of his colleagues are competent, while all the others are not, and these opinions do not change. At the beginning of every session a voting takes place, and those members who are not competent in the opinion of more than one half of the voters are excluded from the jury for the rest of the olympiad. Prove that after at most 15 sessions there will be no more exclusions. (Note that nobody votes about his own competence.)

Let $ABCD$ be a cyclic convex quadrilateral and let $r_{a}, r_{b}, r_{c}, r_{d}$ be the radii of the circles inscribed in the triangles $BCD$, $ACD$, $ABD$, $ABC$ respectively. Prove that $r_{a} + r_{c} = r_{b} + r_{d}$.

Let $a, b, c, d$ be positive integers such that $a b = c d$. Prove that $a + b + c + d$ is not prime.

The graph of the function $f(x)=x^{n}+a_{n-1} x^{n-1}+\cdots+a_{1} x+a_{0}$ (where $n\gt 1$), intersects the line $y=b$ at the points $B_{1}, B_{2}, \ldots, B_{n}$ (from left to right), and the line $y=c$ ($c \neq b$) at the points $C_{1}, C_{2}, \ldots, C_{n}$ (from left to right). Let $P$ be a point on the line $y=c$, to the right to the point $C_{n}$. Find the sum $\cot \angle B_{1} C_{1} P+\cdots+\cot \angle B_{n} C_{n} P$.

Is it possible to partition all positive integers into disjoint sets $A$ and $B$ such that
(i) no three numbers of $A$ form arithmetic progression,
(ii) no infinite non-constant arithmetic progression can be formed by numbers of $B$?