Define $\|x\|_*=(|x|+|x-1|-1)/2$. Find all functions $f:\mathbb N\to\mathbb N$ such that
$$
f^{(\|f(x)-x\|_*)}(x)=x\qquad(x\in\mathbb N).
$$
Here $f^{(0)}(x)=x$, and $f^{(n)}(x)=f(f^{(n-1)}(x))$ for positive integers $n$.
Let $k\le n$ be positive integers. IMO-nation has $n$ villages, some pairs joined by roads. The distance between two villages is the smallest number of roads in a route from one to the other; if no route exists, their distance is infinite.
A newly arrived traveler, called Alice in the English source and Xiaoxun in the Chinese source, is quarantined and cannot see the road network, but knows $n,k$. She wants to decide whether the greatest distance between villages is finite. In each telephone call to the IMO office, she names two villages and asks whether their distance is greater than, equal to, or less than $k$. The office answers truthfully, with infinite distance counted as greater than $k$. Prove that she can decide this in at most $2n^2/k$ calls.
Let $ABCD$ be a rhombus with center $O$, and let $P$ lie on side $AB$. Let $I,J,L$ be the incenters of $PCD,PAD,PBC$, respectively. Let $H,K$ be the orthocenters of $PLB,PJA$, respectively. Prove that $OI\perp HK$.
Let $\alpha_1,\alpha_2,\alpha_3$ be distinct nonzero complex numbers whose points in the complex plane are noncollinear, and suppose $\alpha_1+\alpha_2+\alpha_3=0$. Prove that
$$
\sum_{i=1}^{3}\frac{|\alpha_{i+1}-\alpha_{i+2}|}{\sqrt{|\alpha_i|}}
\left(\frac1{\sqrt{|\alpha_{i+1}|}}+\frac1{\sqrt{|\alpha_{i+2}|}}-\frac2{\sqrt{|\alpha_i|}}\right)\le0.\tag{*}
$$
Here $\alpha_4=\alpha_1$ and $\alpha_5=\alpha_2$. Determine the necessary and sufficient condition for equality.
The Fibonacci sequence $F_0,F_1,F_2,\ldots$ is defined by $F_0=0$, $F_1=1$, and $F_{n+1}=F_n+F_{n-1}$ for every $n\ge1$. Given $n\ge2$, determine the smallest possible size of a set $S$ of integers such that, for each $k=2,3,\ldots,n$, there exist $x,y\in S$ with $x-y=F_k$.
Let $S$ be a nonempty set of positive integers such that for every $a,b\in S$ there exists $c\in S$ satisfying $c^2\mid a(a+b)$. Prove that some $a\in S$ divides every element of $S$.
Source-language clarification: the Chinese statement explicitly says that $S$ is nonempty; the source's English version omits that word. The nonempty hypothesis is retained here. Without it, the empty set would make the existential conclusion false.
For every positive integer $N$, determine the smallest real number $b_N$ such that for every real $x$,
$$
\sqrt[N]{\frac{x^{2N}+1}{2}}\le b_N(x-1)^2+x.
$$
Let $m,n$ be positive integers. Each cell $(r,c)$ of an $m\times n$ table contains a real number $a(r,c)$. Choose a row set $R\subseteq\{1,2,\ldots,m\}$ and a column set $C\subseteq\{1,2,\ldots,n\}$. Call $(R,C)$ a good pair if both conditions hold:
- Condition 1. For every $r'\in\{1,2,\ldots,m\}$, there exists $r\in R$ such that $a(r,c)\ge a(r',c)$ for every $c\in C$.
- Condition 2. For every $c'\in\{1,2,\ldots,n\}$, there exists $c\in C$ such that $a(r,c)\le a(r,c')$ for every $r\in R$.
A good pair $(R,C)$ is minimal if every good pair $(R',C')$ with $R'\subseteq R$ and $C'\subseteq C$ satisfies $R'=R$ and $C'=C$. Prove that the row sets of any two minimal pairs have the same number of elements.
Let $E$ and $F$ be points on the sides $CA$ and $AB$, respectively, of a triangle $ABC$ with circumcircle $\Gamma$. The circumcircle of $AEF$ meets $\Gamma$ again at $X\ne A$. The circumcircles of $ABE$ and $ACF$ meet again at $K\ne A$. Let $AK$ meet $\Gamma$ again at $M\ne A$, and let $N$ be the reflection of $M$ across $BC$. Let $XN$ meet $\Gamma$ again at $S\ne X$. Prove that $SM\parallel BC$.
Source clarification and construction caveat: the English source names $K$ as $Y$ in one sentence; the Chinese source uses $K$ consistently. No nondegeneracy hypothesis is added to the original data. Some allowed choices fail to define a named circle or line, and even otherwise valid intersections may give $S=M$, so $SM$ is undefined. The solution explicitly documents this omission and proves the claim for every configuration in which all the named objects, including $SM$, exist.
For any prime $p$ and any integer $n$, let $d_p(n)\in\{0,1,\ldots,p-1\}$ denote the remainder when $n$ is divided by $p$. A sequence $(a_0,a_1,a_2,\ldots)$ of positive integers is called a $p$-sequence if $a_0$ is coprime to $p$ and
$$
a_{n+1}=a_n+d_p(a_n)\qquad(n\ge0).
$$
Part (a). Are there infinitely many primes $p$ for which there are two $p$-sequences $(a_n)$ and $(b_n)$ such that $a_n\gt b_n$ for infinitely many $n$, and $b_n\gt a_n$ for infinitely many $n$?
Part (b). Are there infinitely many primes $p$ for which there are two $p$-sequences $(a_n)$ and $(b_n)$ such that $a_0\lt b_0$, but $a_n\gt b_n$ for every $n\ge1$?
Source-language clarification: the Chinese statement allows any prime, whereas its English version says “odd prime”. Both readings are addressed in the solution; including $p=2$ does not change either answer.
A city is a point in the plane. There are $n\ge2$ cities. For each city $X$, there is another city $N(X)$ whose distance from $X$ is strictly smaller than the distance from $X$ to any other city. The government builds a road between each city $X$ and $N(X)$, and no other roads. Assume that every city can be reached from any other city by a sequence of roads.
A city $Y$ is called suburban if $Y=N(X)$ for some city $X$. Prove that there are at least $(n-2)/4$ suburban cities.
Let $I$ and $I_A$ be the incenter and $A$-excenter of an acute triangle $ABC$, with $AB\lt AC$. The incircle touches $BC$ at $D$. The line $AD$ meets $BI_A$ and $CI_A$ at $E$ and $F$, respectively. Prove that the circumcircles of triangles $AID$ and $I_AEF$ are tangent.
Notation clarification. The source prints “triangle $IAEF$” and circle $(IAEF)$ although $A,E,F$ are collinear. In both source proofs the circle meant is $(I_AEF)$, through the already defined excenter $I_A$ and the points $E,F$. We explicitly restore that missing subscript here; the original source text is retained in the provenance.
Let $a_1, a_2, a_3, \dots$ be a sequence of positive integers such that $a_1 = 2021$ and
$$
\sqrt{a_{n+1} - a_n} = \lfloor \sqrt{a_n} \rfloor.
$$
Show that there are infinitely many odd numbers and infinitely many even numbers in this sequence.
A magician intends to perform the following trick. She announces a positive integer $n$, along with $2n$ real numbers $x_1 \lt \dots \lt x_{2n}$, to the audience. A member of the audience then secretly chooses a polynomial $P(x)$ of degree $n$ with real coefficients, computes the $2n$ values $P(x_1), \dots, P(x_{2n})$, and writes down these $2n$ values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience.
Determine all $n$ such that the magician can find a strategy to perform such a trick.
There are 2020 points $\{A_i = (x_i, y_i) : i = 1, \dots, 2020\}$ on the plane, satisfying
$$
\begin{aligned}
0 &= x_1 \lt x_2 \lt \dots \lt x_{2020}, \\
0 &= y_{2020} \lt y_{2019} \lt \dots \lt y_1.
\end{aligned}
$$
Denote $O = (0,0)$, the origin. Sequentially construct edges $OA_1, A_1A_2, \dots, A_{2019}A_{2020}, A_{2020}O$ to form a 2021-gon $C$. Tao wants to paint the entire region $C$ in black. On each turn, he chooses a point $(x, y)$, pays $xy$ dollars, and paints the entire region $\{(x', y') : 0 \le x' \le x, 0 \le y' \le y\}$ in black. Prove that Tao can always paint the entire region $C$ in black while spending at most $4|C|$ dollars, where $|C|$ is the area of $C$.
Let $ABC$ be a triangle with $AB \lt AC$, and let $I_a$ be its $A$-excenter. Let $D$ be the projection of $I_a$ to $BC$. Let $X$ be the intersection of $AI_a$ and $BC$, and let $Y, Z$ be the points on $AC, AB$, respectively, such that $X, Y, Z$ are on a line perpendicular to $AI_a$. Let the circumcircle of $AYZ$ intersect $AI_a$ again at $U$. Suppose that the tangent of the circumcircle of $ABC$ at $A$ intersects $BC$ at $T$, and the segment $TU$ intersects the circumcircle of $ABC$ at $V$. Show that $\angle BAV = \angle DAC$.
Let $n$ be a given positive integer. A positive integer $m$ is called $n$-good if at most $2n$ distinct primes $p$ satisfy $p^2\mid m$.
Part (a). Prove that for any two coprime positive integers $a,b$, there exist positive integers $x,y$ such that $ax^n+by^n$ is $n$-good.
Part (b). Prove that for any $k$ positive integers $a_1,\dots,a_k$ with $\gcd(a_1,\dots,a_k)=1$, there exist positive integers $x_1,\dots,x_k$ such that $a_1x_1^n+\cdots+a_kx_k^n$ is $n$-good. The numbers $a_1,\dots,a_k$ need not be pairwise distinct.
Find the largest positive integer $K$ with the following property. For every finite collection of closed intervals $A_1,A_2,\dots,A_N$, each of length $1$, where $N$ is any positive integer, if their union is $[0,2021]$, then $K$ pairwise disjoint intervals can be selected from $A_1,\dots,A_N$.
Find all integers $n=2k+1\gt1$ for which there exists a permutation $a_0,a_1,\dots,a_k$ of $\{0,1,\dots,k\}$ satisfying
$$
a_1^2-a_0^2\equiv a_2^2-a_1^2\equiv\cdots\equiv a_k^2-a_{k-1}^2\pmod n.
$$
Let $n$ be a positive odd integer. At each point of the $2n\times2n$ grid
$$
C=\{(i,j):i,j=0,1,\dots,2n-1\}
$$
there is a guinea pig facing one of the positive or negative $x$- or $y$-directions. Jeff wants to keep $n^2+1$ guinea pigs and remove the rest.
In every round, all remaining guinea pigs simultaneously move one unit in their fixed directions. If the intended destination $(i,j)$ is outside $C$, the animal instead moves to the unique $(p,q)\in C$ with $p\equiv i\pmod{2n}$ and $q\equiv j\pmod{2n}$. For example, a move from $(2,0)$ toward $(2,-1)$ ends at $(2,2n-1)$.
Jeff wants no two retained guinea pigs ever to have the same destination in a round, and no two ever to move to each other's starting points in a round. Prove that he can always achieve this, regardless of the initial directions.