78 2 Algebra
Bk=a 1 Bk+ 1 +a 2 Bk+ 2 +···+an (^2) −kBn 2 ,
whereaj=−ckc+kj. ComputingBk+ 1 =BkX−XBk, we obtain
Bk+ 1 =a 1 Bk+ 2 +a 2 Bk+ 3 +···+an (^2) −kBn (^2) + 1 ,
and inductively
Bk+j=a 1 Bk+j+ 1 +a 2 Bk+j+ 2 +···+an (^2) −kBn (^2) +j, forj≥ 1.
In particular,
Bn 2 =a 1 Bn (^2) + 1 +a 2 Bn (^2) + 2 +···+an (^2) −kBn (^2) +k.
ButBn (^2) + 1 =Bn 2 X−XBn 2 =X^2 −X^2 =On, and henceBn (^2) +j =On, forj≥1.
It follows thatX, which is a linear combination ofBn (^2) + 1 ,Bn (^2) + 2 ,...,Bn (^2) +k, is the zero
matrix. And we are done.
The second example was given at the 67th W.L. Putnam Mathematical Competition
in 2006, and the solution that we present was posted by C. Zara on the Internet.
Example.LetZdenote the set of points inRnwhose coordinates are 0 or 1. (ThusZhas
2 nelements, which are the vertices of a unit hypercube inRn.) Letkbe given, 0≤k≤n.
Find the maximum, over all vector subspacesV⊆Rnof dimensionk, of the number of
points inZ∩V.
Solution.Let us consider the matrix whose rows are the elements ofV∩Z. By construc-
tion it has row rank at mostk. It thus also has column rank at mostk; in particular, there
arekcolumns such that any other column is a linear combination of thesek. It means
that the coordinates of each point ofV∩Zare determined by thekcoordinates that lie
in thesekcolumns. Since each such coordinate can have only two values,V∩Zcan
have at most 2kelements.
This upper bound is reached for the vectors that have all possible choices of 0 and 1
for the firstkentries, and 0 for the remaining entries.
241.Prove that every odd polynomial function of degree equal to 2m−1 can be written as
P(x)=c 1
(
x
1)
+c 2(
x+ 1
3)
+c 3(
x+ 2
5)
+···+cm(
x+m− 1
2 m− 1)
,
where(x
m)
=x(x− 1 )···x−mn!+^1.242.Letnbe a positive integer andP(x)annth-degree polynomial with complex coef-
ficients such thatP( 0 ), P ( 1 ),...,P(n)are all integers. Prove that the polynomial
n!P(x)has integer coefficients.