Problem 6. For a permutation σ = (i
1
, i
2
, ..., i
n
) of (1, 2, ..., n) define D(σ) =
n

k=1
|i
k
− k|. Let Q(n, d) be
the number of permutations σ of (1, 2, ..., n) with d = D(σ). Prove that Q(n, d) is even for d ≥ 2n.
Solution. Consider the n × n determinant
∆(x) =









1 x . . . x
n−1
x 1 . . . x
n−2
.
.

1
,...,i
n
)∈S
n
(−1)
inv(i
1
,...,i
n
)
x
D(i
1
,...,i
n
)
where S
n
is the set of all permutations of (1, 2, ..., n) and inv(i
1
, ..., i
n
) denotes the number of inversions in
the sequence (i
1
, ..., i
n
). So Q(n, d) has the same parity as the coefficient of x
d

.
.
.
.
.
.
.
.
.
x
n−2
x
n−3
. . . 1 x
x
n−1
x
n−2
. . . x 1












.
.
.
.
.
.
.
.
.
.
.
0 0 . . . 1 − x
2
x − x
3
0 0 . . . 0 1 − x
2











= (1 − x
2

be a linear map. Suppose that for all f, g ∈ V with P (fg) = 0 we have P (f ) = 0 or P (g) = 0. Prove that
there exist real numbers x
0
, c such that P (f ) = c f(x
0
) for all f ∈ V .
Solution. We can assume that P = 0.
Let f ∈ V be such that P (f) = 0. Then P (f
2
) = 0, and therefore P (f
2
) = aP (f ) for some non-zero
real a. Then 0 = P (f
2
− af) = P (f (f − a)) implies P (f − a) = 0, so we get P (a) = 0. By rescaling, we
can assume that P (1) = 1. Now P (X + b) = 0 for b = −P (X). Replacing P by
ˆ
P given as
ˆ
P (f(X)) = P (f (X + b))
we can assume that P (X) = 0.
Now we are going to prove that P (X
k
) = 0 for all k ≥ 1. Suppose this is true for all k < n. We know
that P (X
n
+ e) = 0 for e = −P (X
n
). From the induction hypothesis we get
P







1
m
−
1
n
, . . . ,
1
m
−
1
n
,
1
m
, . . . ,
1
m

⊤






2
m − n
mn
=
d
2
2

1
n
−
1
m

→ 0, m, n → ∞.
By completeness of H, it follows that there exists a limit
y = lim
n→∞
y
n
∈ H.
We claim that y sastisfies all conditions of the problem. For m > n > p, with n, p fixed, we compute
x
n
− y
m

2
=
d

2
R
m
=
d
2
2

m − 1
m
2
+
(m − 1)
2
m
2

=
d
2
2
m − 1
m
→
d
2
2
, m → ∞,
showing that x
n

⊤
,

−
1
m
, . . . , 1 −
1
m
, . . . ,−
1
m
, . . . ,−
1
m

⊤

R
m
=
d
2
2

m − 2
m
2
−
2

be any two distinct points in S \ T . Then applying the above procedure to the set
T
′
= {x
′
, x
′′
, x
1
, x
2
, . . . , x
n
, . . .}
it follows that
lim
n→∞
x
′
+ x
′′
+ x
1
+ x
2
+ ··· + x
n
n + 2
= lim
n→∞

− y) : n ∈ N

is still an orthonormal system.
This it true for any distinct x
′
, x
′′
∈ S \ T ; it follows that the entire system

√
2
d
(x − y) : x ∈ S

is an orthonormal system of vectors in H, as required.
4
IMC2008, Blagoevgrad, Bulgaria
Day 2, July 28, 2008
Problem 1. Let n, k be positive integers and suppose that the polynomial x
2k
− x
k
+ 1 divides
x
2n
+ x
n
+ 1. Prove that x
2k
+ x

3k
. Since g(x) divides f(x), f(x
1
) = g(x
1
) = 0. So, 0 = x
2n
1
+ x
n
1
+ 1 = (cos(2α) +
i sin(2α)) + (cos α + i sin α) + 1 = 0, and (2 cos α + 1)(cos α + i sin α) = 0. Hence 2 cos α + 1 = 0, i.e.
α = ±
2π
3
+ 2πc, where c ∈ Z.
Let x
2
be a root of the polynomial h(x). Since h(x) =
x
3k
−1
x
k
−1
, the roots of the polynomial h(x)
are distinct and they are x
2
= cos

Solution. It is well known that an ellipse might be defined by a focus (a point) and a directrix (a
straight line), as a locus of points such that the distance to the focus divided by the distance to
directrix is equal to a given number e < 1. So, if a point X belongs to both ellipses with the same
focus F and directrices l
1
, l
2
, then e
1
· l
1
X = F X = e
2
· l
2
X (here we denote by l
1
X, l
2
X distances
between the corresponding line and the point X). The equation e
1
· l
1
X = e
2
· l
2
X defines two lines,
whose equations are linear combinations with coefficients e

5

1+
√
5
2

n
−

1−
√
5
2

n

.
Expanding this expression, we obtain that F
n
=
1
2
n−1


n
1

+


n
2k+1

5
k
, which implies that 2
n−1
divides

0≤k<n/2

n
2k+1

5
k
.
Problem 4. Let Z[x] be the ring of polynomials with integer coefficients, and let f(x), g(x) ∈ Z[x] be
nonconstant polynomials such that g(x) divides f (x) in Z[x]. Prove that if the polynomial f (x)−2008
has at least 81 distinct integer roots, then the degree of g(x) is greater than 5.
Solution. Let f(x) = g(x)h(x) where h(x) is a polynomial with integer coefficients.
Let a
1
, . . . , a
81
be distinct integer roots of the polynomial f (x)−2008. Then f(a
i
) = g(a
i

Problem 5. Let n be a positive integer, and consider the matrix A = (a
ij
)
1≤i,j≤n
, where
a
ij
=

1 if i + j is a prime number,
0 otherwise.
Prove that | det A| = k
2
for some integer k.
Solution. Call a square matrix of type (B), if it is of the form









0 b
12
0 . . . b
1,2k−2
0
b

0 b
2k−2,3
. . . 0 b
2k−2,2k−1
0 b
2k−1,2
0 . . . b
2k−1,2k−2
0









.
Note that every matrix of this form has determinant zero, because it has k columns spanning a vector
space of dimension at most k − 1.
Call a square matrix of type (C), if it is of the form
C
′
=






2,k
0
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 c
k,1
0 c
k,2
. . . 0 c
k,k
c





= | det C|
2
,
where C denotes the k × k-matrix with coefficients c
i,j
. Therefore, the determinant of any matrix of
type (C) is a perfect square (up to a sign).
Now let X
′
be the matrix obtained from A by replacing the first row by

1 0 0 . . . 0

, and
let Y be the matrix obtained from A by replacing the entry a
11
by 0. By multi-linearity of the
determinant, det(A) = det(X
′
) + det(Y ). Note that X
′
can be written as
X
′
=


, x
4
∈ S are four distinct points, then
x
2
− x
1
, x
2
− x
1
 = d
2
,
x
2
− x
1
, x
3
− x
1
 =
1
2

x
2
− x
1

2
− x
1
, x
4
− x
1
 − x
2
− x
1
, x
3
− x
1
 =
1
2
d
2
−
1
2
d
2
= 0.
This shows that scalar products among vectors which are finite linear combinations of the form
λ
1
x

them using examples of our choosing, such as the canonical example above in R
n
. In fact this property
trivially follows also when coefficients λ
i
are rational, and hence by continuity any real numbers with
sum 0.
If S = {x
1
, x
2
, . . . , x
n
} is a finite set, we form
x =
1
n
(x
1
+ x
2
+ ··· + x
n
) ,
pick a non-zero vector z ∈ [Span(x
1
− x, x
2
− x, . . . , x
n

− x =
d
2
2


1
n
− 1,
1
n
,
1
n
, . . . ,
1
n

⊤
,

1
n
,
1
n
− 1,
1
n
, . . . ,

d
√
2nz
will make all vectors
√
2
d
(x
i
− y) orthogonal to each other; it is easily
checked as above that they will also be of length one.
Let now S be an infinite set. Pick an infinite sequence T = {x
1
, x
2
, . . . , x
n
, . . .} of distinct points
in S. We claim that the sequence
y
n
=
1
n
(x
1
+ x
2
+ ··· + x
n

1
), p(a
2
)) and gcd(s, t) = 1.
As s, t are relatively prime numbers, there exist m, n ∈ Z such that a
1
+ sn = a
2
+ tm =: b
2
. Obviously
s|p(a
1
+ sn) − p(a
1
) and t|p(a
2
+ tm) − p(a
2
), so st|p(b
2
).
Similarly one obtains b
3
such that p(a
3
)|p(b
3
) and p(b
2

)) is also divisible by every p(a
i
), since the polynomial is nonzero, there exists n such
that p(a + np(a
1
)p(a
2
) . . . p(a
k
)) satisfies the modified thesis.
Problem 4. We say a triple (a
1
, a
2
, a
3
) of nonnegative reals is better than another triple (b
1
, b
2
, b
3
) if two
out of the three following inequalities a
1
> b
1
, a
2
> b

,
2
5
, 0

,

2
15
,
11
15
,
2
15

.
We will prove that any special triple (x, y, z) is worse than one of these (triple a is worse than triple b if
triple b is better than triple a). We suppose that some special triple (x, y, z) is actually not worse than the
first three of the triples from the given set, derive some conditions on x, y, z and prove that, under these
conditions, (x, y, z) is worse than the fourth triple from the set.
Triple (x, y, z) is not worse than

0,
8
15
,
7
15


— x 
3
5
or y 
2
5
. Since
x + y + z = 1, then it is impossible that all inequalities x 
2
5
, y 
2
5
and z 
7
15
are true. Suppose that
x <
2
5
, then y 
2
5
and z 
3
5
. Using x + y + z = 1 and x  0 we get x = 0, y =
2
5
, z =

7
15
and this
is a contradiction to the admissibility of (x, y, z). Suppose that z <
7
15
, then x 
2
5
and y 
8
15
. We get
(by admissibility, again) that z 
1
15
and y 
3
5
. The last inequalities imply that

2
15
,
11
15
,
2
15


1
, y
2
, y
3
), c(S) = min(z
1
, z
2
, z
3
). It is easy to check that S
1
:

x
1
− a
1 − a − b − c
,
y
1
− b
1 − a − b − c
,
z
1
− c
1 − a − b − c


1 − a − b − c

2
is a set of three special triples also (we may suppose that a + b + c < 1, because otherwise all three triples
are equal and our statement is trivial).
If there is a special triple (x, y, z) which is not worse than any triple from S
1
, then the triple
((1 − a − b − c)x + a, (1 − a − b − c)y + b, (1 − a − b − c)z + c)
is special and not worse than any triple from S. We also have a(S
1
) = b(S
1
) = c(S
1
) = 0, so we may
suppose that the same holds for our starting set S.
Suppose that one element of S has two entries equal to 0.
Note that one of the two remaining triples from S is not worse than the other. This triple is also not
worse than all triples from S because any special triple is not worse than itself and the triple with two
zeroes.
So we have a = b = c = 0 but we may suppose that all triples from S contain at most one zero. By
transposing triples and elements in triples (elements in all triples must be transposed simultaneously) we
may achieve the following situation x
1
= y
2
= z
3
= 0 and x

; z
1
, x
3
; y
3
, z
2
. The sum of all these numbers is three and consequently the
sum of the numbers in one of the pairs is less than or equal to one. If it is the first pair then the triple
(x
2
, 1 − x
2
, 0) is not worse than all triples from S, for the second we may take (1 − z
1
, 0, z
1
) and for the
third — (0, y
3
, 1 − y
3
). So we found a desirable special triple for any given S.
Problem 5. Does there exist a finite group G with a normal subgroup H such that |Aut H| > |Aut G|?
Solution. Yes. Let H be the commutative group H = F
3
2
, where F
2

τ
T . In other words, G is the group of 24 elements
G = {ba
i
: b ∈ H, i ∈ (Z/3Z)}, ab = φ(b)a.
G has one element e of order 1 and seven elements b, b ∈ H, b = e of order 2.
If g = ba, we find that g
2
= baba = bφ(b)a
2
= e, and that
g
3
= bφ(b)a
2
ba = bφ(b)aφ(b)a
2
= bφ(b)φ
2
(b)a
3
= ψ(b),
where the homomorphism ψ : H → H is defined as ψ : (x
1
, x
2
, x
3
) → (x
1

, namely as H = (12), (34), (56) and
G = (135)(246), (12).
3