IMC 2016

Let $f \colon [a, b] \to \mathbb{R}$ be continuous on $[a, b]$ and differentiable on $(a, b)$. Suppose that $f$ has infinitely many zeros, but there is no $x \in (a, b)$ with $f(x) = f'(x) = 0$.

(a) Prove that $f(a)f(b) = 0$.

(b) Give an example of such a function on $[0, 1]$.

Let $k$ and $n$ be positive integers. A sequence $(A_1, \ldots, A_k)$ of $n \times n$ real matrices is preferred by Ivan the Confessor if $A_i^2 \ne 0$ for $1 \le i \le k$, but $A_iA_j = 0$ for $1 \le i, j \le k$ with $i \ne j$. Show that $k \le n$ in all preferred sequences, and give an example of a preferred sequence with $k = n$ for each $n$.

Let $n$ be a positive integer. Also let $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$ be real numbers such that $a_i + b_i > 0$ for $i = 1, 2, \ldots, n$. Prove that

Let $n \ge k$ be positive integers, and let $\mathcal{F}$ be a family of finite sets with the following properties:

(i) $\mathcal{F}$ contains at least $\binom{n}{k} + 1$ distinct sets containing exactly $k$ elements;

(ii) for any two sets $A, B \in \mathcal{F}$, their union $A \cup B$ also belongs to $\mathcal{F}$.

Prove that $\mathcal{F}$ contains at least three sets with at least $n$ elements.

Let $S_n$ denote the set of permutations of the sequence $(1, 2, \ldots, n)$. For every permutation $\pi = (\pi_1, \ldots, \pi_n) \in S_n$, let $\operatorname{inv}(\pi)$ be the number of pairs $1 \le i < j \le n$ with $\pi_i > \pi_j$; i.e. the number of inversions in $\pi$. Denote by $f(n)$ the number of permutations $\pi \in S_n$ for which $\operatorname{inv}(\pi)$ is divisible by $n + 1$.

Prove that there exist infinitely many primes $p$ such that $f(p - 1) > \dfrac{(p-1)!}{p}$, and infinitely many primes $p$ such that $f(p - 1) < \dfrac{(p-1)!}{p}$.

Let $(x_1, x_2, \ldots)$ be a sequence of positive real numbers satisfying $\sum\limits_{n=1}^{\infty} \dfrac{x_n}{2n - 1} = 1$. Prove that

Today, Ivan the Confessor prefers continuous functions $f \colon [0, 1] \to \mathbb{R}$ satisfying $f(x) + f(y) \ge |x - y|$ for all pairs $x, y \in [0, 1]$. Find the minimum of $\int_0^1 f$ over all preferred functions.

Let $n$ be a positive integer, and denote by $\mathbb{Z}_n$ the ring of integers modulo $n$. Suppose that there exists a function $f \colon \mathbb{Z}_n \to \mathbb{Z}_n$ satisfying the following three properties:

(i) $f(x) \ne x$,

(ii) $f(f(x)) = x$,

(iii) $f(f(f(x + 1) + 1) + 1) = x$ for all $x \in \mathbb{Z}_n$.

Prove that $n \equiv 2 \pmod 4$.

Let $k$ be a positive integer. For each nonnegative integer $n$, let $f(n)$ be the number of solutions $(x_1, \ldots, x_k) \in \mathbb{Z}^k$ of the inequality $|x_1| + \ldots + |x_k| \le n$. Prove that for every $n \ge 1$, we have $f(n - 1)f(n + 1) \le f(n)^2$.

Let $A$ be a $n \times n$ complex matrix whose eigenvalues have absolute value at most $1$. Prove that

(Here $\|B\| = \sup\limits_{\|x\| \le 1} \|Bx\|$ for every $n \times n$ matrix $B$ and $\|x\| = \sqrt{\sum\limits_{i=1}^{n} |x_i|^2}$ for every complex vector $x \in \mathbb{C}^n$.)