IMC 1999

a) Show that for any $m \in \mathbb{N}$ there exists a real $m \times m$ matrix $A$ such that $A^3 = A + I$, where $I$ is the $m \times m$ identity matrix.

b) Show that $\det A > 0$ for every real $m \times m$ matrix satisfying $A^3 = A + I$.

Does there exist a bijective map $\pi : \mathbb{N} \to \mathbb{N}$ such that

Suppose that a function $f : \mathbb{R} \to \mathbb{R}$ satisfies the inequality

for every positive integer $n$ and for all $x, y \in \mathbb{R}$. Prove that $f$ is a constant function.

Find all strictly monotonic functions $f : (0, +\infty) \to (0, +\infty)$ such that $f\left( \dfrac{x^2}{f(x)} \right) \equiv x$.

Suppose that $2n$ points of an $n \times n$ grid are marked. Show that for some $k > 1$ one can select $2k$ distinct marked points, say $a_1, \dots, a_{2k}$, such that $a_1$ and $a_2$ are in the same row, $a_2$ and $a_3$ are in the same column, $\dots$, $a_{2k-1}$ and $a_{2k}$ are in the same row, and $a_{2k}$ and $a_1$ are in the same column.

a) For each $1 < p < \infty$ find a constant $c_p < \infty$ for which the following statement holds: If $f : [-1,1] \to \mathbb{R}$ is a continuously differentiable function satisfying $f(1) > f(-1)$ and $|f'(y)| \le 1$ for all $y \in [-1,1]$, then there is an $x \in [-1,1]$ such that $f'(x) > 0$ and $|f(y) - f(x)| \le c_p \left( f'(x) \right)^{1/p} |y - x|$ for all $y \in [-1,1]$.

b) Does such a constant also exist for $p = 1$?

Suppose that in a not necessarily commutative ring $R$ the square of any element is $0$. Prove that $abc + abc = 0$ for any three elements $a, b, c$.

We throw a dice (which selects one of the numbers $1, 2, \dots, 6$ with equal probability) $n$ times. What is the probability that the sum of the values is divisible by $5$?

Assume that $x_1, \dots, x_n \ge -1$ and $\sum\limits_{i=1}^{n} x_i^3 = 0$. Prove that $\sum\limits_{i=1}^{n} x_i \le \dfrac{n}{3}$.

Prove that there exists no function $f : (0, +\infty) \to (0, +\infty)$ such that $f^2(x) \ge f(x+y)\left( f(x) + y \right)$ for any $x, y > 0$.

Let $S$ be the set of all words consisting of the letters $x$, $y$, $z$, and consider an equivalence relation $\sim$ on $S$ satisfying the following conditions: for arbitrary words $u, v, w \in S$

(i) $uu \sim u$;

(ii) if $v \sim w$, then $uv \sim uw$ and $vu \sim wu$.

Show that every word in $S$ is equivalent to a word of length at most $8$.

Let $A$ be a subset of $\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}$ containing at most $\dfrac{1}{100} \ln n$ elements. Define the $r$th Fourier coefficient of $A$ for $r \in \mathbb{Z}_n$ by

Prove that there exists an $r \ne 0$, such that $|f(r)| \ge \dfrac{|A|}{2}$.