2018-IMOC

Algebra

A1

Find all functions $f:\mathbb Q\to\mathbb Q$ such that for all $x,y,z,w\in\mathbb Q$, $$f(f(xyzw)+x+y)+f(z)+f(w)=f(f(xyzw)+z+w)+f(x)+f(y).$$

A2

For arbitrary non-constant polynomials $f_1(x),\ldots,f_{2018}(x)\in\mathbb Z[x]$, is it always possible to find a polynomial $g(x)\in\mathbb Z[x]$ such that $$f_1(g(x)),\ldots,f_{2018}(g(x))$$are all reducible.

A3

Find all functions $f:\mathbb R\to\mathbb R$ such that for reals $x,y$, $$f(xf(y)+y)=yf(x)+f(y).$$

A4

Find all functions $f:\mathbb R\to\mathbb R$ such that $$f\left(x^2+f(y)\right)-y=(f(x+y)-y)^2$$holds for all $x,y\in\mathbb R$.

A5

Show that for all reals $x,y,z$, we have $$\left(x^2+3\right)\left(y^2+3\right)\left(z^2+3\right)\ge(xyz+x+y+z+4)^2.$$

A6

Given $ a, b, c > 0$. Prove that: $ (1+a+b+c)(1+ab+bc+ca) \ge 4\sqrt{2}\sqrt{(a+bc)(b+ca)(c+ab)}$

A7

If the reals $a,b,c,d,e,f,g,h,i$ satisfy $$\begin{cases}ab+bc+ca=3\\de+ef+fd=3\\gh+hi+ig=3\\ad+dg+ga=3\\be+eh+hb=3\end{cases}$$show that $cf+fi+ic=3$ holds as well.

Combinatorics

C1

IMOC is a small country without any lake. One day, the king decides to divide IMOC into many regions so that each region borders the sea. Prove that the map is $3$-colorable.

C2

Given an odd $n\in\mathbb N$. In an $n\times n$ chessboard, you may place many $2\times2$ squares. How many grids, at most, are covered by exactly one square?

C3

Given an $a\times b$ chessboard where $a,b\ge3$, alice wants to use only $L$-dominoes (as the figure shows) to cover this chessboard. How many grids, at least, are covered even times?

C4

For a sequence $\{a_i\}_{i\ge1}$ consisting of only positive integers, prove that if for all different positive integers $i$ and $j$, we have $a_i\nmid a_j$, then $$\{p\mid p\text{ is a prime and }p\mid a_i\text{ for some }i\}$$is a infinite set.

C5

Alice and Bob are playing the following game: They have an $8\times8$ chessboard. Initially, all grids are white. Each round, Alice chooses a white grid and paints it black. Then Bob chooses one of the neighbors of that grid and paints it black. Or he does nothing. After that, Alice may decide to continue the game or not. The goal of Alice is to maximize the number of connected components of black grids, on the other hand, Bob wants to minimize that number. If both of them are extremely smart, how many connected components will be in the end of the game?

C6

In a deck of cards, there are $kn$ cards numbered from $1$ to $n$ and there are $k$ cards of each number. Now, divide this deck into $k$ sub-decks with equal sizes. Prove that if $\gcd(k,n)=1$, then one could always pick $n$ cards, one from each sub-deck, such that the sum of those cards is divisible by $n$.

Geometry

G1

Given an integer $n \ge 3$. Find the largest positive integer $k $ with the following property: For $n$ points in general position, there exists $k$ ways to draw a non-intersecting polygon with those $n$ points as it’s vertices. Different wordingGiven $n$, find the maximum $k$ so that for every general position of $n$ points , there are at least $k$ ways of connecting the points to form a polygon.

G2

Given $\vartriangle ABC$ with circumcircle $\Omega$. Assume $\omega_a, \omega_b, \omega_c$ are circles which tangent internally to $\Omega$ at $T_a,T_b, T_c $ and tangent to $BC,CA,AB$ at $P_a, P_b, P_c$, respectively. If $AT_a,BT_b,CT_c$ are collinear, prove that $AP_a,BP_b,CP_c$ are collinear.

G3

Given an acute $\vartriangle ABC$ whose orthocenter is denoted by $H$. A line $\ell$ passes $H$ and intersects $AB,AC$ at $P ,Q$ such that $H$ is the mid-point of $P,Q$. Assume the other intersection of the circumcircle of $\vartriangle ABC$ with the circumcircle of $\vartriangle APQ$ is $X$. Let $C'$ is the symmetric point of $C$ with respect to $X$ and $Y$ is the another intersection of the circumcircle of $\vartriangle ABC$ and $AO$, where O is the circumcenter of $\vartriangle APQ$. Show that $CY$ is tangent to circumcircle of $\vartriangle BCC'$.

G4

Given an acute $\vartriangle ABC$ with incenter $I$. Let $I'$ be the symmetric point $I$ with respect to the midpoint of $B,C$ and $D$ is the foot of $A$. If $DI$ and the circumcircle of vartriangle $BI'C$ intersect at $T$ and $TI' $ intersects the circumcircle of $\vartriangle ATI$ at $X$. Furthermore, $E,F$ are tangent points of the incircle and $AB,AC, P$ is the another intersection of the circumcircles of $\vartriangle ABC, \vartriangle AEF$. Show that $AX \parallel PI$.

G5

Suppose $I,O,H$ are incenter, circumcenter, orthocenter of $\vartriangle ABC$ respectively. Let $D = AI \cap BC$,$E = BI \cap CA$, $F = CI \cap AB$ and $X$ be the orthocenter of $\vartriangle DEF$. Prove that $IX \parallel OH$.

Number Theory

N1

Find all functions $f:\mathbb N\to\mathbb N$ satisfying $$x+f^{f(x)}(y)\mid2(x+y)$$for all $x,y\in\mathbb N$.

N2

Find all functions $f:\mathbb N\to\mathbb N$ satisfying $$\operatorname{lcm}(f(x),y)\gcd(f(x),f(y))=f(x)f(f(y))$$for all $x,y\in\mathbb N$.

N3

Find all pairs of positive integers $(x,y)$ so that $$\frac{(x^2-x+1)(y^2-y+1)}{xy}\in\mathbb N.$$

N4

Let a sequence $\{a_n\}$, $n \in \mathbb{N}^{*}$ given, satisfying the condition \[0 < a_{n+1} - a_n \leq 2001\] for all $n \in \mathbb{N}^{*}$ Show that there are infinitely many pairs of positive integers $(p, q)$ such that $p < q$ and $a_p$ is divisor of $a_q$.

N5

Find all positive integers $k$ such that for every $n\in\mathbb N$, if there are $k$ factors (not necessarily distinct) of $n$ so that the sum of their squares is $n$, then there are $k$ factors (not necessarily distinct) of $n$ so that their sum is exactly $n$.

N6

If $f$ is a polynomial sends $\mathbb Z$ to $\mathbb Z$ and for $n\in\mathbb N_{\ge2}$, there exists $x\in\mathbb Z$ so that $n\nmid f(x)$, show that for every $k\in\mathbb Z$, there is a non-negative integer $t$ and $a_1,\ldots,a_t\in\{-1,1\}$ such that $$a_1f(1)+\ldots+a_tf(t)=k.$$