2018 EGMO Problems

Day 1

Problem 1

Let $ABC$ be a triangle with $CA=CB$ and $\angle{ACB}=120^\circ$, and let $M$ be the midpoint of $AB$. Let $P$ be a variable point of the circumcircle of $ABC$, and let $Q$ be the point on the segment $CP$ such that $QP = 2QC$. It is given that the line through $P$ and perpendicular to $AB$ intersects the line $MQ$ at a unique point $N$. Prove that there exists a fixed circle such that $N$ lies on this circle for all possible positions of $P$.

Solution

Problem 2

Consider the set \[A = \left\{1+\frac{1}{k} : k=1,2,3,4,\cdots \right\}.\]

(a) Prove that every integer $x \geq 2$ can be written as the product of one or more elements of $A$, which are not necessarily different.

(b) For every integer $x \geq 2$ let $f(x)$ denote the minimum integer such that $x$ can be written as the product of $f(x)$ elements of $A$, which are not necessarily different.

Prove that there exist infinitely many pairs $(x,y)$ of integers with $x\geq 2$, $y \geq 2$, and \[f(xy)<f(x)+f(y).\] (Pairs $(x_1,y_1)$ and $(x_2,y_2)$ are different if $x_1 \neq x_2$ or $y_1 \neq y_2$). [/list]

Solution

Problem 3

The $n$ contestant of EGMO are named $C_1, C_2, \cdots C_n$. After the competition, they queue in front of the restaurant according to the following rules.

(i) The Jury chooses the initial order of the contestants in the queue.

(ii) Every minute, the Jury chooses an integer $i$ with $1 \leq i \leq n$.

(iii) If contestant $C_i$ has at least $i$ other contestants in front of her, she pays one euro to the Jury and moves forward in the queue by exactly $i$ positions.

(iv) If contestant $C_i$ has fewer than $i$ other contestants in front of her, the restaurant opens and process ends.

(a) Prove that the process cannot continue indefinitely, regardless of the Jury’s choices.

(b) Determine for every $n$ the maximum number of euros that the Jury can collect by cunningly choosing the initial order and the sequence of moves.

Solution

Day 2

Problem 4

A domino is a $1 \times 2$ or $2 \times 1$ tile. Let $n \ge 3$ be an integer. Dominoes are placed on an $n \times n$ board in such a way that each domino covers exactly two cells of the board, and dominoes do not overlap. The value of a row or column is the number of dominoes that cover at least one cell of this row or column. The configuration is called balanced if there exists some $k \ge 1$ such that each row and each column has a value of $k$. Prove that a balanced configuration exists for every $n \ge 3$, and find the minimum number of dominoes needed in such a configuration.

Solution

Problem 5

Let $\Gamma$ be the circumcircle of triangle $ABC$. A circle $\Omega$ is tangent to the line segment $AB$ and is tangent to $\Gamma$ at a point lying on the same side of the line $AB$ as $C$. The angle bisector of $\angle BCA$ intersects $\Omega$ at two different points $P$ and $Q$. Prove that $\angle ABP = \angle QBC$.

Solution

Problem 6

(a) Prove that for every real number $t$ such that $0 < t < \tfrac{1}{2}$ there exists a positive integer $n$ with the following property: for every set $S$ of $n$ positive integers there exist two different elements $x$ and $y$ of $S$, and a non-negative integer $m$ (i.e. $m \ge 0$), such that \[|x-my|\leq ty.\]

(b) Determine whether for every real number $t$ such that $0 < t < \tfrac{1}{2}$ there exists an infinite set $S$ of positive integers such that \[|x-my| > ty\] for every pair of different elements $x$ and $y$ of $S$ and every positive integer $m$ (i.e. $m > 0$).

Solution