IMO 2019

Problem 1. Let $\mathbb{Z}$ be the set of integers. Determine all functions $f:\mathbb{Z}\to \mathbb{Z}$ such that, for all integers $a$ and $b$,

$f(2a)+2f(b)=f(f(a+b)).$

Problem 2. In triangle $ABC$, point $A_1$ lies on side $BC$ and point $B_1$ lies on side $AC$. Let $P$ and $Q$ be points on segments $A{A}_1$ and $B{B}_1$, respectively, such that $PQ$ is parallel to $AB$. Let $P_1$ be a point on line $P{B}_1$, such that $B_1$ lies strictly between $P$ and $P_1$, and $\angle P{P}_{1}C=\angle BAC$. Similarly, let $Q_1$ be a point on line $Q{A}_1$, such that $A_1$ lies strictly between $Q$ and $Q_1$, and $\angle C{Q}_{1}Q=\angle CBA$.

Prove that points $P$, $Q$, $P_1$, and $Q_1$ are concyclic.

Problem 3. A social network has 2019 users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:

Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.

Initially, 1010 users have 1009 friends each, and 1009 users have 1010 friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Problem 4. Find all pairs $(k,n)$ of positive integers such that

$k!=(2^n-1)(2^n-2)(2^n-4)\cdots (2^n-2^{n-1}).$

Problem 5. The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k>0$ coins showing $H$, then he turns over the $k^{\text{th}}$ coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n=3$ the process starting with the configuration $THT$ would be $THT\to HHT\to HTT\to TTT$, which stops after three operations.

(a) Show that, for each initial configuration, Harry stops after a finite number of operations.

(b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For example, $L(THT)=3$ and $L(TTT)=0$. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$.

Problem 6. Let $I$ be the incentre of acute triangle $ABC$ with $AB\ne AC$. The incircle $\omega$ of $ABC$ is tangent to sides $BC$, $CA$, and $AB$ at $D$, $E$, and $F$, respectively. The line through $D$ perpendicular to $EF$ meets $\omega$ again at $R$. Line $AR$ meets $\omega$ again at $P$. The circumcircles of triangles $PCE$ and $PBF$ meet again at $Q$.

Prove that lines $DI$ and $PQ$ meet on the line through $A$ perpendicular to $AI$.