IMC 2020

Let $n$ be a positive integer. Compute the number of words $w$ (finite sequences of letters) that satisfy all the following three properties:

(1) $w$ consists of $n$ letters, all of them are from the alphabet $\{\mathsf{a}, \mathsf{b}, \mathsf{c}, \mathsf{d}\}$;

(2) $w$ contains an even number of letters $\mathsf{a}$;

(3) $w$ contains an even number of letters $\mathsf{b}$.

(For example, for $n = 2$ there are 6 such words: $\mathsf{aa}$, $\mathsf{bb}$, $\mathsf{cc}$, $\mathsf{dd}$, $\mathsf{cd}$ and $\mathsf{dc}$.)

Let $A$ and $B$ be $n \times n$ real matrices such that

where $I$ is the $n \times n$ identity matrix.

Prove that

($\operatorname{rk}(M)$ denotes the rank of matrix $M$, i.e., the maximum number of linearly independent columns in $M$. $\operatorname{trace}(M)$ denotes the trace of $M$, that is the sum of diagonal elements in $M$.)

Let $d \ge 2$ be an integer. Prove that there exists a constant $C(d)$ such that the following holds: For any convex polytope $K \subset \mathbb{R}^d$, which is symmetric about the origin, and any $\varepsilon \in (0, 1)$, there exists a convex polytope $L \subset \mathbb{R}^d$ with at most $C(d)\varepsilon^{1-d}$ vertices such that

(For a real $\alpha$, a set $T \subset \mathbb{R}^d$ with nonempty interior is a convex polytope with at most $\alpha$ vertices, if $T$ is a convex hull of a set $X \subset \mathbb{R}^d$ of at most $\alpha$ points, i.e., $T = \{\sum_{x \in X} t_x x \mid t_x \ge 0, \sum_{x \in X} t_x = 1\}$. For a real $\lambda$, put $\lambda K = \{\lambda x \mid x \in K\}$. A set $T \subset \mathbb{R}^d$ is symmetric about the origin if $(-1)T = T$.)

A polynomial $p$ with real coefficients satisfies the equation $p(x + 1) - p(x) = x^{100}$ for all $x \in \mathbb{R}$. Prove that $p(1 - t) \geqslant p(t)$ for $0 \leqslant t \leqslant 1/2$.

Find all twice continuously differentiable functions $f \colon \mathbb{R} \to (0, +\infty)$ satisfying

for all $x \in \mathbb{R}$.

Find all prime numbers $p$ for which there exists a unique $a \in \{1, 2, \ldots, p\}$ such that $a^3 - 3a + 1$ is divisible by $p$.

Let $G$ be a group and $n \ge 2$ be an integer. Let $H_1$ and $H_2$ be two subgroups of $G$ that satisfy

Prove that $H_1$ and $H_2$ are conjugate in $G$.

(Here $[G : H]$ denotes the index of the subgroup $H$, i.e. the number of distinct left cosets $xH$ of $H$ in $G$. The subgroups $H_1$ and $H_2$ are conjugate if there exists an element $g \in G$ such that $g^{-1}H_1g = H_2$.)

Compute

(Here $\log$ denotes the natural logarithm.)