IMO 2016 (LVII International Mathematical Olympiad)

Concurrent lines in triangle with angle bisectors

Triangle $BCF$ has a right angle at $B$. Let $A$ be the point on line $CF$ such that $FA=FB$ and $F$ lies between $A$ and $C$. Point $D$ is chosen such that $DA=DC$ and $AC$ is the bisector of $\angle DAB$. Point $E$ is chosen such that $EA=ED$ and $AD$ is the bisector of $\angle EAC$. Let $M$ be the midpoint of $CF$. Let $X$ be the point such that $AMXE$ is a parallelogram (where $AM\parallel EX$ and $AE\parallel MX$). Prove that lines $BD$, $FX$, and $ME$ are concurrent.

Topic: Geometria piana Metodo: Coordinate, Trigonometria Abilita: Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Geometria Fonte: apri PDF p.1

Concurrent lines in triangle with angle bisectors

Triangle $BCF$ has a right angle at $B$. Let $A$ be the point on line $CF$ such that $FA=FB$ and $F$ lies between $A$ and $C$. Point $D$ is chosen such that $DA=DC$ and $AC$ is the bisector of $\angle DAB$. Point $E$ is chosen such that $EA=ED$ and $AD$ is the bisector of $\angle EAC$. Let $M$ be the midpoint of $CF$. Let $X$ be the point such that $AMXE$ is a parallelogram (where $AM\parallel EX$ and $AE\parallel MX$). Prove that lines $BD$, $FX$, and $ME$ are concurrent.

src_imho_2016__Q01

Fill n×n table with letters L, M, O under row/column/diagonal conditions

Find all positive integers $n$ for which each cell of an $n\times n$ table can be filled with one of the letters $L$, $M$ and $O$ in such a way that: \begin{itemize} \item in each row and each column, one third of the entries are $L$, one third are $M$ and one third are $O$; and \item in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are $L$, one third are $M$ and one third are $O$. \end{itemize}

\textbf{Note.} The rows and columns of an $n\times n$ table are labelled $1$ to $n$ in a natural order. Thus each cell corresponds to a pair of positive integers $(i,j)$ with $1\le i,j\le n$. For $n>1$, the table has $4n-2$ diagonals of two types. A diagonal of the first type consists of all cells $(i,j)$ for which $i+j$ is a constant, and a diagonal of the second type consists of all cells $(i,j)$ for which $i-j$ is a constant.

Topic: Combinatoria Metodo: Casework, Colorazione, Invarianti Abilita: Conteggio sistematico, Riconoscimento di pattern, Casework accurato Area: Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

Fill n×n table with letters L, M, O under row/column/diagonal conditions

Find all positive integers $n$ for which each cell of an $n\times n$ table can be filled with one of the letters $L$, $M$ and $O$ in such a way that: \begin{itemize} \item in each row and each column, one third of the entries are $L$, one third are $M$ and one third are $O$; and \item in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are $L$, one third are $M$ and one third are $O$. I’m going to tell you.

\textbf{Note.} The rows and columns of an $n\times n$ table are labelled $1$ to $n$ in a natural order. Thus each cell corresponds to a pair of positive integers $(i,j)$ with $1\le i,j\le n$. For $n>1$, the table has $4n-2$ diagonals of two types. A diagonal of the first type consists of all cells $(i,j)$ for which $i+j$ is a constant, and a diagonal of the second type consists of all cells $(i,j)$ for which $i-j$ is a constant.

src_imho_2016__Q02

Convex polygon with integer-coordinate vertices, area S, odd n divides 25S

Let $P=A_1{A}_2\cdots A_k$ be a convex polygon in the plane. The vertices $A_1,A_2,\dots ,A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$. Prove that $25S$ is an integer divisible by $n$.

Topic: Geometria piana, Teoria dei Numeri Metodo: Congruenze, Induzione Abilita: Manipolazione algebrica, Ragionamento geometrico, Lettura attenta Area: Geometria, Aritmetica e Teoria dei Numeri Fonte: apri PDF p.1

Convex polygon with integer-coordinated vertices, area S, odd n divides 25S

Let $P=A_1{A}_2\cdots A_k$ be a convex polygon in the plane. The vertices $A_1,A_2,\dots ,A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$. Prove that $25S$ is an integer divisible by $n$.

src_imho_2016__Q03

Fragrant sets of positive integers with prime factor condition

A set of positive integers is called \textit{fragrant} if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n)=n^2+n+1$. What is the least possible value of the positive integer $b$ such that there exists a non-negative integer $a$ for which the set $\{P(a+1),P(a+2),\dots ,P(a+b)\}$ is fragrant?

Topic: Teoria dei Numeri, Combinatoria Metodo: Fattorizzazione, Casework Abilita: Riconoscimento di pattern, Manipolazione algebrica, Lettura attenta Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

Fragrant sets of positive integers with prime factor condition

A set of positive integers is called \textit{fragrant} if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n)=n^2+n+1$. What is the least possible value of the positive integer $b$ such that there exists a non-negative integer $a$ for which the set $\{P(a+1),P(a+2),\dots ,P(a+b)\}$ is fragrant?

src_imho_2016__Q04

Equation with 2016 linear factors on both sides, minimize k solutions

The equation $(x-1)(x-2)\cdots (x-2016)=(x-1)(x-2)\cdots (x-2016)$ is written on the board, with $2016$ linear factors on each side. What is the least possible value of $k$ for which it is possible to erase exactly $k$ of these $4032$ linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?

Topic: Algebra, Combinatoria Metodo: Casework, Estremalità Abilita: Manipolazione algebrica, Riconoscimento di pattern, Casework accurato, Lettura attenta Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF p.1

Equation with 2016 linear factors on both sides, minimize k solutions

The equation $(x-1)(x-2)\cdots (x-2016)=(x-1)(x-2)\cdots (x-2016)$ is written on the board, with $2016$ linear factors on each side. What is the least possible value of $k$ for which it is possible to erase exactly $k$ of these $4032$ linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?

src_imho_2016__Q05

Frogs on line segments, Geoff controls placement, parity of n

There are $n\ge 2$ line segments in the plane such that every two segments cross, and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it, facing the other endpoint. Then he will clap his hands $n-1$ times. Each time he claps, each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them ever occupy the same intersection point at the same time.

(a) Prove that Geoff can always fulfil his wish if $n$ is odd.

(b) Prove that Geoff can never fulfil his wish if $n$ is even.

Topic: Combinatoria, Geometria piana Metodo: Invarianti, Colorazione, Casework Abilita: Ragionamento geometrico, Riconoscimento di pattern, Modellizzazione, Lettura attenta Area: Combinatoria, Logica e Probabilita, Geometria Fonte: apri PDF p.1

Frogs on line segments, Geoff controls placement, parity of n

There are $n\ge 2$ line segments in the plane such that every two segments cross, and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it, facing the other endpoint. Then he will clap his hands. Each time he claps, each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them ever occupy the same intersection point at the same time.

(a) Prove that Geoff can always fulfill his wish if $n$ is odd.

(b) Prove that Geoff can never fulfill his wish if $n$ is even.

src_imho_2016__Q06