IMC 2020

Let $n$ be a positive integer. Compute the number of words $w$ that satisfy the following three properties.

1. $w$ consists of $n$ letters from the alphabet $\{a,b,c,d\}.$ 2. $w$ contains an even number of $a$ 's

2. $w$ contains an even number of $b$ 's.

For example, for $n=2$ there are $6$ such words: $aa, bb, cc, dd, cd, dc.$

$A, B$ are $n \times n$ matrices such that $\text{rank}(AB-BA+I) = 1.$ Prove that $\text{tr}(ABAB)-\text{tr}(A^2 B^2) = \frac{1}{2}n(n-1).$

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 $$(1-\varepsilon)K \subseteq L \subseteq K.$$

Official definitions: For a real $\alpha,$ a set $T \in \mathbb{R}^d$ is a convex polytope with at most $\alpha$ vertices, if $T$ is a convex hull of a set $X \in \mathbb{R}^d$ of at most $\alpha$ points, i.e. $T = \{\sum\limits_{x\in X} t_x x | t_x \ge 0, \sum\limits_{x \in X} t_x = 1\}.$ Define $\alpha K = \{\alpha x | x \in K\}.$ A set $T \in \mathbb{R}^d$ is symmetric about the origin if $(-1)T = T.$

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

Find all twice continuously differentiable functions $f: \mathbb{R} \to (0, \infty)$ satisfying $f''(x)f(x) \ge 2f'(x)^2.$

Find all prime numbers $p$ such that there exists a unique $a \in \mathbb{Z}_p$ for which $a^3 - 3a + 1 = 0.$

Let $G$ be a group and $n \ge 2$ be an integer. Let $H_1, H_2$ be $2$ subgroups of $G$ that satisfy $$[G: H_1] = [G: H_2] = n \text{ and } [G: (H_1 \cap H_2)] = n(n-1).$$ Prove that $H_1, H_2$ are conjugate in $G.$ Official definitions: $[G:H]$ denotes the index of the subgroup of $H,$ i.e. the number of distinct left cosets $xH$ of $H$ in $G.$ The subgroups $H_1, H_2$ are conjugate if there exists $g \in G$ such that $g^{-1} H_1 g = H_2.$

Compute $\lim\limits_{n \to \infty} \frac{1}{\log \log n} \sum\limits_{k=1}^n (-1)^k \binom{n}{k} \log k.$