J 29 Solutions 1
J 29 Solutions 1
J 29 Solutions 1
We already know that an and an+1 are positive integers, therefore (an + an+1 )/3 is rational and its square
is an an+1 − 1 is a positive integer. Thus, (an + an+1 )/3 is also a positive integer and an an+1 − 1 is a
square.
The 29th Annual Vojtěch Jarník
International Mathematical Competition
Ostrava, 29th March 2019
Category I
u = x + 2y + 3 , v = y + z + 2, w =x+y+z
smart?
u = x + 2y + 3 , v = y + z + 2, w =x+y−z
smart?
[Artūras Dubickas / Vilnius University]
Solution The answer is: a) no; b) yes.
In case a) the polynomials u, v, w are all equal to zero at x = 2, y = −5/2 and z = 1/2. This leads to
0 = 2019, which is absurd.
In case b) we have u − v − w = 1. Consider the nth power of this identity with some n ≥ 3 · 2018 + 1:
X n!(−1)n2 +n3 n1 n2 n3
(u − v − w)n = u v w = 1.
n1 +n2 +n3 =n
n1 !n2 !n3 !
By the choice of n, in each term of the sum at least one power ni is greater than or equal to 2019. (It can be
several ni with this property.) We can thus rewrite the above identity in the form
with some P, Q, R ∈ Z[x, y, z]. (The choice of P, Q, R is not unique.) Multiplying it by 2019 we conclude that
the triplet (u, v, w) is useful.
The 29th Annual Vojtěch Jarník
International Mathematical Competition
Ostrava, 29th March 2019
Category I
∞
Problem 3 For an invertible n × n matrix M with integer entries we define a sequence SM = {Mi }i=0 by the
recurrence
M0 = M
Mi+1 = (MiT )−1 Mi , i = 0, 1, . . .
Find the smallest integer n ≥ 2 for which there exists a normal n × n matrix M with integer entries such that
its sequence SM is non-constant and has period P = 7, i.e., Mi+7 = Mi for all i = 0, 1, . . .
(M T means the transpose of a matrix M . A square matrix M is called normal if M TM = M M T holds.)
[Martin Niepel / Comenius University, Bratislava]
Solution For a normal square matrix M , we have its Schur decomposition M = U DU ∗ , where U is unitary
and D is diagonal with eigenvalues of M on the diagonal. It follows, that if Mi = U Di U ∗ then Mi+1 =
−1
U (Di∗ ) Di U ∗ . So we can pass to eigenvalues and investigate periodic behavior of complex sequences given by
the recurrence λi+1 = λi /λ̄i . Consequently,
n−1
λ20
λn = 2n−1 .
λ̄0
P
Clearly, |λi | = 1 for i ≥ 1, and if we require λP = λ0 , we arrive at the equation λ0 = λ20 , so every eigenvalue
λ0 of M has to be (2P − 1)st root of unity.
Since all eigenvalues of M satisfy |λ| = 1 and M is normal, M has to be unitary. The matrix M satisfies
P
M 2 −1 = I, as well. Matrix M can not have all eigenvalues equal to 1, it would imply M = I, and the period
would be 1 in that case. Hence, it has at least one primitive (2P − 1)st root of unity as an eigenvalue and 2P − 1
is its multiplicative order.
The only unitary matrices with integer coeficients are signed permutiation matrices (i.e. matrices with
exactly one ±1 in every row and colummn, all other entries being zero). The order of a n×n signed permutatation
matrix equals the order of the underlying permutation matrix or its double, and therefore has to be a divisor
of 2n! – double of the order of a symmetric group Sn . Since 2P − 1 is a prime, it follows that n ≥ 2P − 1.
P
For n = 2P − 1 such matrices, indeed, do exist, take a matrix of an action of a cyclic permutation on R2 −1
given by ei 7→ ei+1 for i = 1, 2, . . . , 2P − 2 and e2P −1 7→ e1 .
The 29th Annual Vojtěch Jarník
International Mathematical Competition
Ostrava, 29th March 2019
Category I