SIMON-MARAIS 2025

A function $f: [0, \infty) \to [0, \infty)$ is max-poly if there exist finitely many polynomials with real coefficients $p_1(x), p_2(x), \ldots, p_n(x)$ such that

• $p_i(x) \geq 0$ for all $x \geq 0$ and $1 \leq i \leq n$, and
• $f(x) = \max(p_1(x), p_2(x), \ldots, p_n(x))$ for all $x \geq 0$.

Determine whether the function $f(x) = \min(x, x^2)$ is max-poly.

Let $p$ be a prime number. Given a square matrix $M$ with entries in $\mathbb{Z}/p\mathbb{Z}$, an eigenvector of $M$ is a non-zero vector $\mathbf{v}$ with entries in $\mathbb{Z}/p\mathbb{Z}$ such that $M\mathbf{v} = \lambda\mathbf{v}$ for some $\lambda \in \mathbb{Z}/p\mathbb{Z}$.

For each positive integer $n$, determine the average number of eigenvectors of an $n \times n$ matrix with entries in $\mathbb{Z}/p\mathbb{Z}$.

(Here $\mathbb{Z}/p\mathbb{Z}$ refers to the integers modulo $p$.)

Consider the matrix

$$M = \begin{bmatrix} t + 1 & t \\ 1 & 1 \end{bmatrix},$$

whose entries are polynomials in the variable $t$. Let $a(t)$ denote the polynomial in the first row and first column of $M^{2025}$ and let $b(t)$ denote the polynomial in the first row and second column of $M^{2025}$.

Prove that $a(t)$ has 2025 distinct real roots $\alpha_1, \alpha_2, \ldots, \alpha_{2025}$ and that $b(t)$ has 2025 distinct real roots $\beta_1, \beta_2, \ldots, \beta_{2025}$ satisfying

$$\alpha_1 < \beta_1 < \alpha_2 < \beta_2 < \cdots < \alpha_{2025} < \beta_{2025}.$$

Let $V$ be a finite-dimensional subspace of the real vector space of $C^\infty$ functions from $\mathbb{R}$ to $\mathbb{R}$. Suppose that for all functions $g(x) \in V$, we have $g(2x) \in V$.

Prove that every function in $V$ is a polynomial.

(A function from $\mathbb{R}$ to $\mathbb{R}$ is $C^\infty$ if its $k$-th derivative exists at every point, for all positive integers $k$.)

A function $f: \{1, 2, \ldots, n\} \rightarrow \{m+1, m+2, \ldots, m+n\}$, where $m$ and $n$ are positive integers, is said to be beautiful if

• $a$ divides $f(a)$ for all $a \in \{1, 2, \ldots, n\}$, and
• $f(a) \neq f(b)$ for all distinct elements $a$ and $b$ of $\{1, 2, \ldots, n\}$ with $\gcd(a, b) \neq 1$.

Determine all positive integers $n$ such that, for every positive integer $m$, there exists a beautiful function $f: \{1, 2, \ldots, n\} \rightarrow \{m+1, m+2, \ldots, m+n\}$.

Let $W$ be the interior of a convex quadrilateral in $\mathbb{R}^2$ which has no two sides parallel. Prove that there exist two triangles in $\mathbb{R}^2$ whose interiors $S$ and $T$ satisfy

$$W = \{s + t \mid s \in S, t \in T\}.$$

Let $n$ be a positive integer and let $\omega = e^{\frac{2\pi i}{n}}$. Suppose $z_1, z_2, \ldots, z_n$ are distinct complex numbers. Define $A$ to be the $n \times n$ matrix whose $(j, k)$-th entry is $(z_j - \omega^k)^n$, for $1 \leq j, k \leq n$.

Given that $\det A = 0$, prove that $z_1z_2 \cdots z_n = 1$.

The following problem is open in the sense that the answer to part (b) is not currently known. A solution to part (a) will be awarded 7 points. Up to 7 additional points may be awarded for progress on part (b).

(a) Determine all triples of integers $(x, y, q)$ that satisfy the equation

$$x^3 + x^2 + x + 1 = y^q,$$

where $q \geq 3$ is odd.

(b) Determine all quadruples of integers $(x, y, n, q)$ that satisfy the equation

$$x^n + x^{n-1} + \cdots + x + 1 = y^q,$$

where $n, q \geq 2$.