2014 Canadian MO Problems

Problem 1

Let $a_1,a_2,\dots,a_n$ be positive real numbers whose product is $1$. Show that the sum $\textstyle\frac{a_1}{1+a_1}+\frac{a_2}{(1+a_1)(1+a_2)}+\frac{a_3}{(1+a_1)(1+a_2)(1+a_3)}+\cdots+\frac{a_n}{(1+a_1)(1+a_2)\cdots(1+a_n)}$ is greater than or equal to $\frac{2^n-1}{2^n}$.


Problem 2

Let $m$ and $n$ be odd positive integers. Each square of an $m$ by $n$ board is coloured red or blue. A row is said to be red-dominated if there are more red squares than blue squares in the row. A column is said to be blue-dominated if there are more blue squares than red squares in the column. Determine the maximum possible value of the number of red-dominated rows plus the number of blue-dominated columns. Express your answer in terms of $m$ and $n$.


Problem 3

Let $p$ be a fixed odd prime. A $p$-tuple $(a_1,a_2,a_3,\ldots,a_p)$ of integers is said to be good if

(i) $0\le a_i\le p-1$ for all $I$, and (ii) $a_1+a_2+a_3+\cdots+a_p$ is not divisible by $p$, and (iii) $a_1a_2+a_2a_3+a_3a_4+\cdots+a_pa_1$ is divisible by $p$.

Determine the number of good $p$-tuples.


Problem 4

The quadrilateral $ABCD$ is inscribed in a circle. The point $P$ lies in the interior of $ABCD$, and $\angle P AB = \angle P BC = \angle P CD = \angle P DA$. The lines $AD$ and $BC$ meet at $Q$, and the lines $AB$ and $CD$ meet at $R$. Prove that the lines $PQ$ and $PR$ form the same angle as the diagonals of $ABCD$.


Problem 5

Fix positive integers $n$ and $k\ge 2$. A list of n integers is written in a row on a blackboard. You can choose a contiguous block of integers, and I will either add $1$ to all of them or subtract $1$ from all of them. You can repeat this step as often as you like, possibly adapting your selections based on what I do. Prove that after a finite number of steps, you can reach a state where at least $n-k+2$ of the numbers on the blackboard are all simultaneously divisible by $k$.