CMOQR 2014

Let $f : \mathbb{Z} \rightarrow \mathbb{Z}^+$ be a function, and define $h : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}^+$ by $h(x, y) = \gcd (f(x), f(y))$ . If $h(x, y)$ is a two-variable polynomial in $x$ and $y$ , prove that it must be constant.

Alphonse and Beryl play a game involving $n$ safes. Each safe can be opened by a unique key and each key opens a unique safe. Beryl randomly shuffles the $n$ keys, and after placing one key inside each safe, she locks all of the safes with her master key. Alphonse then selects $m$ of the safes (where $m < n$ ), and Beryl uses her master key to open just the safes that Alphonse selected. Alphonse collects all of the keys inside these $m$ safes and tries to use these keys to open up the other $n - m$ safes. If he can open a safe with one of the $m$ keys, he can then use the key in that safe to try to open any of the remaining safes, repeating the process until Alphonse successfully opens all of the safes, or cannot open any more. Let $P_m(n)$ be the probability that Alphonse can eventually open all $n$ safes starting from his initial selection of $m$ keys.

(a) Show that $P_2(3) = \frac23$ .

(b) Prove that $P_1(n) = \frac1n$ .

(c) For all integers $n \geq 2$ , prove that $$P_2(n) = \frac2n \cdot P_1(n-1) + \frac{n-2}{n} \cdot P_2(n-1).$$ (d) Determine a formula for $P_2 (n)$ .

Let $1000 \leq n = \text{ABCD}_{10} \leq 9999$ be a positive integer whose digits $\text{ABCD}$ satisfy the divisibility condition: $$1111 | (\text{ABCD} + \text{AB} \times \text{CD}).$$ Determine the smallest possible value of $n$ .

In $\triangle ABC$ , the interior sides of which are mirrors, a laser is placed at point $A_1$ on side $BC$ . A laser beam exits the point $A_1$ , hits side $AC$ at point $B_1$ , and then reflects off the side. (Because this is a laser beam, every time it hits a side, the angle of incidence is equal to the angle of reflection). It then hits side $AB$ at point $C_1$ , then side $BC$ at point $A_2$ , then side $AC$ again at point $B_2$ , then side $AB$ again at point $C_2$ , then side $BC$ again at point $A_3$ , and finally, side $AC$ again at point $B_3$ .

(a) Prove that $\angle B_3A_3C = \angle B_1A_1C$ .

(b) Prove that such a laser exists if and only if all the angles in $\triangle ABC$ are less than $90^{\circ}$ .