Maximum Trace over All Permutations

Maximum Trace over All Permutations

English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email [email protected].

Task 2 of the municipal stage (Moscow) of the All-Russian School Olympiad (VsOSh) 2025/26 in artificial intelligence, grades 9–11 (variant III). Original: tasks-ai-9-11-mun-msk-25-26.pdf.

An $n \times m$ matrix is what we call a table of numbers consisting of $n$ rows and $m$ columns. Matrices are multiplied by the "row by column" rule. If

$$M = \begin{pmatrix} p & q \\ r & s \end{pmatrix}, \qquad N = \begin{pmatrix} u & v \\ w & x \end{pmatrix},$$

then

$$MN = \begin{pmatrix} pu + qw & pv + qx \\ ru + sw & rv + sx \end{pmatrix}.$$

The sum of the diagonal elements (the trace) of a matrix is the number $tr\begin{pmatrix} p & q \\ r & s \end{pmatrix} = p + s$.

You are given the matrix

$$A = \begin{pmatrix} -1 & 4 \\ 5 & 10 \end{pmatrix}.$$

You are also given the numbers $-4, -5, 20, 25$. Consider all 24 matrices $B$ of the form

$$B = \begin{pmatrix} x & y \\ z & w \end{pmatrix},$$

in which $x, y, z, w$ is some permutation of the numbers $-4, -5, 20, 25$. For each such $B$, consider the products $AB$ and $BA$.

a) Find the largest possible value of $tr(AB)$.

b) Find the largest possible value of $tr(BA)$.

Translator's note: this task's points are not stated in the statement paper (whose total is 600 points); the official answers give a maximum of 100 points, 50 for each part (exact match of the answer).