OBM 1987

$p(x_1, x_2, ... , x_n)$ is a polynomial with integer coefficients. For each positive integer $r, k(r)$ is the number of $n$ -tuples $(a_1, a_2,... , a_n)$ such that $0 \le a_i \le r-1$ and $p(a_1, a_2, ... , a_n)$ is prime to $r$ . Show that if $u$ and $v$ are coprime then $k(u\cdot v) = k(u)\cdot k(v)$ , and if p is prime then $k(p^s) = p^{n(s-1)} k(p)$ .

Given a point $p$ inside a convex polyhedron $P$ . Show that there is a face $F$ of $P$ such that the foot of the perpendicular from $p$ to $F$ lies in the interior of $F$ .

Two players play alternately. The first player is given a pair of positive integers $(x_1, y_1)$ . Each player must replace the pair $(x_n, y_n)$ that he is given by a pair of non-negative integers $(x_{n+1}, y_{n+1})$ such that $x_{n+1} = min(x_n, y_n)$ and $y_{n+1} = max(x_n, y_n)- k\cdot x_{n+1}$ for some positive integer $k$ . The first player to pass on a pair with $y_{n+1} = 0$ wins. Find for which values of $x_1/y_1$ the first player has a winning strategy.

Given points $A_1 (x_1, y_1, z_1), A_2 (x_2, y_2, z_2), .., A_n (x_n, y_n, z_n)$ let $P (x, y, z)$ be the point which minimizes $\Sigma ( |x - x_i| + |y -y_i| + |z -z_i| )$ . Give an example (for each $n > 4$ ) of points $A_i$ for which the point $P$ lies outside the convex hull of the points $A_i$ .

$A$ and $B$ wish to divide a cake into two pieces. Each wants the largest piece he can get. The cake is a triangular prism with the triangular faces horizontal. $A$ chooses a point $P$ on the top face. $B$ then chooses a vertical plane through the point $P$ to divide the cake. $B$ chooses which piece to take. Which point $P$ should $A$ choose in order to secure as large a slice as possible?