IMC 2011

Let $f : \mathbb{R} \to \mathbb{R}$ be a continuous function. A point $x$ is called a shadow point if there exists a point $y \in \mathbb{R}$ with $y > x$ such that $f(y) > f(x)$. Let $a < b$ be real numbers and suppose that

• all the points of the open interval $I = (a,b)$ are shadow points;

• $a$ and $b$ are not shadow points.

Prove that

a) $f(x) \le f(b)$ for all $a < x < b$;

b) $f(a) = f(b)$.

Does there exist a real $3 \times 3$ matrix $A$ such that $\operatorname{tr}(A) = 0$ and $A^2 + A^t = I$? ($\operatorname{tr}(A)$ denotes the trace of $A$, $A^t$ is the transpose of $A$, and $I$ is the identity matrix.)

Let $p$ be a prime number. Call a positive integer $n$ interesting if

for some polynomials $f$ and $g$ with integer coefficients.

a) Prove that the number $p^p - 1$ is interesting.

b) For which $p$ is $p^p - 1$ the minimal interesting number?

Let $A_1, A_2, \dots, A_n$ be finite, nonempty sets. Define the function

Prove that $f$ is nondecreasing on $[0,1]$.

($|A|$ denotes the number of elements in $A$.)

Let $n$ be a positive integer and let $V$ be a $(2n-1)$-dimensional vector space over the two-element field. Prove that for arbitrary vectors $v_1, \dots, v_{4n-1} \in V$, there exists a sequence $1 \le i_1 < \dots < i_{2n} \le 4n-1$ of indices such that

Let $(a_n)_{n=0}^{\infty}$ be a sequence with $\frac{1}{2} < a_n < 1$ for all $n \ge 0$. Define the sequence $(x_n)_{n=0}^{\infty}$ by

What are the possible values of $\lim\limits_{n \to \infty} x_n$? Can such a sequence diverge?

An alien race has three genders: male, female, and emale. A married triple consists of three persons, one from each gender, who all like each other. Any person is allowed to belong to at most one married triple. A special feature of this race is that feelings are always mutual – if $x$ likes $y$, then $y$ likes $x$.

The race is sending an expedition to colonize a planet. The expedition has $n$ males, $n$ females, and $n$ emales. It is known that every expedition member likes at least $k$ persons of each of the two other genders. The problem is to create as many married triples as possible to produce healthy offspring so the colony could grow and prosper.

a) Show that if $n$ is even and $k = \dfrac{n}{2}$, then it might be impossible to create even one married triple.

b) Show that if $k \ge \dfrac{3n}{4}$, then it is always possible to create $n$ disjoint married triples, thus marrying all of the expedition members.

Determine the value of

Let $f(x)$ be a polynomial with real coefficients of degree $n$. Suppose that $\dfrac{f(k) - f(m)}{k - m}$ is an integer for all integers $0 \le k < m \le n$. Prove that $a - b$ divides $f(a) - f(b)$ for all pairs of distinct integers $a$ and $b$.

Let $F = A_0A_1 \dots A_n$ be a convex polygon in the plane. Define for all $1 \le k \le n-1$ the operation $f_k$ which replaces $F$ with a new polygon

where $A'_k$ is the point symmetric to $A_k$ with respect to the perpendicular bisector of $A_{k-1}A_{k+1}$. Prove that $(f_1 \circ f_2 \circ \dots \circ f_{n-1})^n(F) = F$. We suppose that all operations are well-defined on the polygons, to which they are applied, i.e. results are convex polygons again. ($A_0, A_1, \dots, A_n$ are the vertices of $F$ in consecutive order.)