International Mathematics Competition
for University Students
2024

IMC2024: Problems on Day 2

Problem 6. Prove that for any function \(\displaystyle f\colon\mathbb Q\to\mathbb Z \), there exist \(\displaystyle a,b,c\in\mathbb Q\) such that \(\displaystyle a < b < c \), \(\displaystyle f(b) \geq f(a) \), and \(\displaystyle f(b) \geq f(c) \).

Mehdi Golafshan & Markus A. Whiteland, University of Liège

  Solution  

Problem 7. Let \(\displaystyle n\) be a positive integer. Suppose that \(\displaystyle A\) and \(\displaystyle B\) are invertible \(\displaystyle n\times n\) matrices with complex entries such that \(\displaystyle A+B=I\) (where \(\displaystyle I\) is the identity matrix) and

\(\displaystyle (A^2 + B^2)(A^4 + B^4) = A^5 + B^5. \)

Find all possible values of \(\displaystyle \det(AB)\) for the given \(\displaystyle n\).

Sergey Bondarev, Sergey Chernov, Belarusian State University, Minsk

  Hint    Solution  

Problem 8. Define the sequence \(\displaystyle x_1,x_2,\ldots\) by the initial terms \(\displaystyle x_1=2\), \(\displaystyle x_2=4\), and the recurrence relation

\(\displaystyle x_{n+2}=3x_{n+1}-2x_n+\frac{2^ n}{x_n}\quad\text{for }n\geq 1.\)

Prove that \(\displaystyle \displaystyle\lim\limits_{n \to \infty}\frac{x_n}{2^ n}\) exists and satisfies

\(\displaystyle \frac{1+\sqrt{3}}{2}\leq\lim\limits_{n \to \infty}\dfrac{x_n}{2^ n}\leq\frac{3}{2}.\)

Karen Keryan, Yerevan State University & American University of Armenia, Armenia

  Hint    Solution  

Problem 9. A matrix \(\displaystyle A=(a_{ij})\) is called nice, if it has the following properties:

(i) the set of all entries of \(\displaystyle A\) is \(\displaystyle \{1,2,\ldots,2t\}\) for some integer \(\displaystyle t\);

(ii) the entries are non-decreasing in every row and in every column: \(\displaystyle a_{i,j}\leq a_{i,j+1}\) and \(\displaystyle a_{i,j}\leq a_{i+1,j}\);

(iii) equal entries can appear only in the same row or the same column: if \(\displaystyle a_{i,j}=a_{k,\ell}\), then either \(\displaystyle i=k\) or \(\displaystyle j=\ell\);

(iv) for each \(\displaystyle s=1,2,\ldots,2t-1\), there exist \(\displaystyle i\ne k\) and \(\displaystyle j\ne \ell\) such that \(\displaystyle a_{i,j}=s\) and \(\displaystyle a_{k,\ell}=s+1\).

Prove that for any positive integers \(\displaystyle m\) and \(\displaystyle n\), the number of nice \(\displaystyle m\times n\) matrices is even.

For example, the only two nice \(\displaystyle 2\times 3\) matrices are \(\displaystyle \begin{pmatrix} 1&1&1\\2&2&2 \end{pmatrix}\) and \(\displaystyle \begin{pmatrix} 1&1&3\\2&4&4 \end{pmatrix}\).

Fedor Petrov, St Petersburg State University

  Solution  

Problem 10. We say that a square-free positive integer \(\displaystyle n\) is almost prime if

\(\displaystyle n \mid x^{d_1}+x^{d_2}+...+x^{d_k}-kx \)

for all integers \(\displaystyle x\), where \(\displaystyle 1=d_1<d_2<...<d_k=n\) are all the positive divisors of \(\displaystyle n\). Suppose that \(\displaystyle r\) is a Fermat prime (i.e., it is a prime of the form \(\displaystyle 2^{2^m}+1\) for an integer \(\displaystyle m\geq 0\)), \(\displaystyle p\) is a prime divisor of an almost prime integer \(\displaystyle n\), and \(\displaystyle p\equiv 1\ (\mathrm{mod}\ r)\). Show that, with the above notation, \(\displaystyle d_i\equiv 1\ (\mathrm{mod}\ r)\) for all \(\displaystyle 1\leq i\leq k\).

(An integer \(\displaystyle n\) is called square-free if it is not divisible by \(\displaystyle d^2\) for any integer \(\displaystyle d>1\).)

Tigran Hakobyan, Yerevan State University, Vanadzor, Armenia

  Solution