International Mathematics Competition
for University Students
2020

IMC2020: Problems on Day 1

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

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

   (2) \(\displaystyle w\) contains an even number of letters \(\displaystyle \texttt{a}\);

   (3) \(\displaystyle w\) contains an even number of letters \(\displaystyle \texttt{b}\).

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

Armend Sh. Shabani, University of Prishtina

  Hint    Solution  

Problem 2. Let \(\displaystyle A\) and \(\displaystyle B\) be \(\displaystyle n\times n\) real matrices such that

\(\displaystyle \textrm{rk}(AB-BA+I)=1 \)

where \(\displaystyle I\) is the \(\displaystyle n\times n\) identity matrix.

Prove that

\(\displaystyle \tr(ABAB)-\tr(A^2B^2)=\frac12 n(n-1). \)

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

Rustam Turdibaev, V. I. Romanovskiy Institute of Mathematics

  Hint    Solution  

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

\(\displaystyle (1-\varepsilon)K\subseteq L \subseteq K. \)

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

Fedor Petrov, St. Petersburg State University

  Hint    Solution  

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

Daniil Klyuev, St. Petersburg State University

  Hint    Solution