# Maximum Trace over All Permutations

*English translation by SOTA – AI Community of the Russian original. Organisers who would like this translation removed can email sota.ai.community@gmail.com.*

*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](https://vos.olimpiada.ru/upload/files/Arhive_tasks/2025-26/mun/ai/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).*